Connection Status:
Competition Arena > BunnyExam

BunnyExam

SRM 487 · 2010-03-12 · by lyrically

SRM 487 · 2010-03-12 · by lyrically · Brute Force, Graph Theory, Simple Math
Class Name: BunnyExam
Return Type: double
Method Name: getExpected
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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
0)
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.

1)
4
2
{ 1, 4 }
Returns: -1.0

This is impossible.

2)
2
8
{ }
Returns: 0.25

linkage may be empty.

3)
1000000000
1
{ 11, 13, 2010, 487 }
Returns: -1.0
4)
128
64
{ 32, 16, 8, 4, 2, 1 }
Returns: -1.0

Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BunnyExam with a public method double getExpected(int m, int k, vector<int> linkage) · 150 test cases · 2 s / 256 MB per case

Submitting as anonymous