StringRings
SRM 776 · 2020-01-23 · by misof
Problem Statement
We have N = 2*A + B pieces of string. Each end of each piece has a color, as follows:
- A pieces of rope have both ends red.
- A pieces of rope have both ends green.
- B pieces of rope have one end red and one end green.
All strings are jumbled up. We have found all 2*N ends of our strings. Note that N of them are red and N are green. We are going to create N red-green pairs at random, with each of the N! possible pairings being equally likely. Then, we will make N knots, each tying one pair of ends together.
Clearly, the above process will produce some disjoint string rings. Calculate and return the expected number of those rings.
Notes
- The return value must have an absolute or a relative error up to 1e-9.
Constraints
- A will be between 0 and 10^6, inclusive.
- B will be between 0 and 10^6, inclusive.
0 1 Returns: 1.0
We have one piece of string. One of its ends is green and the other is red. We will pair up the two ends and tie them together, thereby forming a single string ring.
1 0 Returns: 1.0
We have one red-red piece and one green-green piece. There are two possible ways how to pair up their ends, but both of them lead to exactly one string ring containing both strings.
1 2 Returns: 1.5833333333333333
There are four pieces of strings. Together, they have four red and four green ends. There are 4! = 24 ways to create four disjoint pairs of ends, each containing a red and a green end. Out of those 24 ways, in 12 of them we will obtain a single string ring, in 10 of them we will obtain two, and two ways produce three string rings each. Thus, the expected number of string rings is (12*1 + 10*2 + 2*3) / 24.
0 0 Returns: 0.0
A boring special case: no strings means no rings.
2 3 Returns: 1.8428571428571427
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StringRings with a public method double expectedRings(int A, int B) · 43 test cases · 2 s / 256 MB per case