StringRings | Topcoder Archive

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.

Definition

Class:: StringRings
Method:: expectedRings
Parameters:: int, int
Returns:: double
Method signature:: double expectedRings(int A, int B)
(be sure your method is public)

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.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.