RainbowSocks
TCO17 Austin · 2017-03-31 · by Nickolas
Problem Statement
You have a collection of socks of various colors.
You are given a
In the morning you will choose two different socks from your collection uniformly at random. Compute and return the probability that the two random socks will form an acceptable pair.
Notes
- Each sock from your collection can be used on either foot.
- Your return value must have an absolute or a relative error smaller than 1e-9.
Constraints
- socks will contain between 2 and 50 elements, inclusive.
- Each element of socks will be between 1 and 50, inclusive.
- colorDiff will be between 0 and 49, inclusive.
{1, 2, 3, 4, 5, 6, 7}
7
Returns: 1.0
You are not particularly picky, so any pair of socks is acceptable.
{1, 50, 50, 1}
0
Returns: 0.3333333333333333
There are 6 ways to pick a pair of socks from this collection: one pair (1, 1), one pair (50, 50) and four different pairs (1, 50). Only the first two pairs are acceptable.
{44, 14, 24, 31, 30, 32, 46, 23, 27, 2}
24
Returns: 0.8222222222222222
{18, 3, 47, 34, 15, 29, 26, 6, 11, 13, 48, 49, 27, 31, 16, 42, 24, 17, 32, 12, 22, 9, 28, 36, 40, 10, 19, 38, 21, 1, 5, 33, 43, 30, 7, 45, 44, 23, 20, 39, 4, 2, 46, 25, 14, 35, 1, 41, 8, 37}
0
Returns: 8.163265306122449E-4
Two 1 socks, the rest are all different
{19, 4, 48, 35, 16, 30, 27, 7, 12, 14, 49, 38, 28, 32, 17, 43, 25, 18, 33, 13, 23, 10, 29, 37, 41, 11, 20, 39, 22, 2, 6, 34, 44, 31, 8, 46, 45, 24, 21, 40, 5, 3, 47, 26, 15, 36, 1, 42, 9}
0
Returns: 0.0
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RainbowSocks with a public method double getPairProb(vector<int> socks, int colorDiff) · 51 test cases · 2 s / 256 MB per case