BunnyExam | Topcoder Archive

Problem Statement

Bunnies like programming and they sometimes make useful devices.

One group of bunnies made a device called RandomAnswerer for their final exam. They cannot solve any of the problems, so they will try to answer the questions randomly.

There are m problems numbered 1 through m. The answer for each problem will be one of the integers between 1 and k, inclusive. We also know the following:

The answer to problem x is different from that of problem x + 1, where 1 <= x < m.
We have a int[] linkage containing N * 2 elements. For each i, where 0 <= i < N, the answer to problem linkage[i * 2] is the same as that of linkage[i * 2 + 1]. Note that all elements in linkage are distinct.

RandomAnswerer makes a sequence of m answers and shows it to the bunnies. Both the sequence produced by RandomAnswerer and the sequence of correct answers are chosen among all possible sequences of m answers that agree with the information above, randomly (all of them have the same probability of being chosen) and independently. Return the expected number of correct answers bunnies get. If there is any contradiction in the information, i.e., there are no sequences of answers that agree with all of it, return -1.0 instead.

Definition

Class:: BunnyExam
Method:: getExpected
Parameters:: int, int, int[]
Returns:: double
Method signature:: double getExpected(int m, int k, int[] linkage)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

m and k will each be between 1 and 1,000,000,000, inclusive.
linkage will contain between 0 and 20 elements, inclusive.
linkage will contain an even number of elements.
Each element of linkage will be between 1 and m, inclusive.
All elements of linkage will be distinct.

Examples

```
3
```
```
2
```
```
{ 1, 3 }
```
```
Returns: 1.5
```
Here problems 1 and 2 have different answers, problems 2 and 3 have different answers and problems 1 and 3 have the same answer. The answers will be either (1, 2, 1) or (2, 1, 2), so the number of correct answers bunnies get will be 3 or 0 with equal probability.
```
4
```
```
2
```
```
{ 1, 4 }
```
```
Returns: -1.0
```
This is impossible.
```
2
```
```
8
```
```
{ }
```
```
Returns: 0.25
```
linkage may be empty.

1000000000

{ 11, 13, 2010, 487 }

Returns: -1.0

{ 32, 16, 8, 4, 2, 1 }

Returns: -1.0

{ 1, 3, 7, 9, 13, 10, 6, 2  }

Returns: 4.333333333333333

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.