Literature
TCO19 SRM 752 · 2019-03-04 · by teja349
Problem Statement
Teja's college is organizing a tournament in the card game Literature. Teja wanted to take part in the tournament, so he formed a team with Vinay and Sohail. They wanted to practice for the tournament, but no other team wanted to play them - the teams didn't want to leak their strategies before the tournament. But Teja did not give up. He decided that they will practice on their own, and he came up with a game that will help them train their memory.
The practice game is played with 3*N cards. The cards are numbered from 1 to 3*N, inclusive. At the beginning of the game, the cards are shuffled and each player takes N of them.
The game is played in turns. The turns are numbered starting from 0. The players take the turns in the cyclic order "Teja, Vinay, Sohail". That is, Teja takes turn 0, Vinay takes turn 1, Sohail takes turn 2, Teja takes turn 3, and so on.
In each turn, the player selects a random element X from the set of the 2*N cards they don't have, and makes a true statement "I don't have the card number X."
Teja remembers everything that was said during the game. Vinay and Sohail are really bad at the game. They can take valid turns, but they never remember anything the other players said.
You are given the
Compute and return the expected number of turns from the beginning of the game to the moment when Teja knew the exact distribution of all cards.
Notes
- All random choices are made with uniform probabilities. All random events are mutually independent.
- Your return value must have an absolute or a relative error at most 1e-9.
Constraints
- N will be between 1 and 1000, inclusive.
- Teja will contain exactly N elements.
- Each element of Teja will be between 1 and 3*N, inclusive.
- All elements of Teja will be distinct.
- history will contain between 0 and 200 elements, inclusive.
- Each element of history will be between 1 and 3*N, inclusive.
- Elements of history will correspond to a valid game.
- In particular, for each valid i, history[3*i] will never be one of Teja's cards.
10
{5,29,12,16,25,17,18,30,27,10}
{4,6,5,23,22,29,20,8,12,3,13,16,1,15,25,4,6,17,23,22,18,20,8,30,3,13,27,1,15,10,4,6,5,23,22,29,20,8,12,3,13,16,1,15,25,4,6,17,22,29,26,8,12,19,13,16,14,15,25,9,6,5,4,22,29,23,8,12,20,13,16,3,15,25,1,6,5,24,22,29,26,8,12,19,13,16,14,15,25,9,6,5,4,22,29,23,8,12,20,13,16,3,15,25,1,6,5,24,22,29,26,8,12,19,13,16,14,15,25,9,6,5,4,22,29,23,8,12,20,13,16,3,15,25,1,6,5,24,22,29,26,8,12,19,13,16,14,15,25,9,6,5,4,22,29,23,8,12,20,13,16,3,15,25,1,6,5}
Returns: 78.0
2
{6,2}
{}
Returns: 11.676190476190474
2
{3,6}
{1}
Returns: 11.676190476190474
1
{3}
{1}
Returns: 3.333333333333333
There has already been one turn. With probability 1/2 there will be exactly one more turn. This happens if the number announced by Vinay in the next turn is not 3, and the probability of that event is exactly 1/2, because Vinay is announcing one of two cards he does not have (chosen uniformly at random). In other scenarios the game will take more than one turn. The final answer is the sum over all possible scenarios of (the probability of that particular scenario) times (the number of turns it took Teja to learn everything in that particular scenario).
1
{3}
{2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,3,2}
Returns: 2.0
2
{1,4}
{3,1,6,6,2,5,2,4,1}
Returns: 6.0
Teja has cards 1 and 4. There have already been nine turn of the game. The first few of them look as follows: Turn 0: Teja announced that he does not have card 3. Turn 1: Vinay announced that he does not have card 1. (Teja already knew this, as this is one of his cards.) Turn 2: Sohail announced that he does not have card 6. (Teja can deduce that Vinay has card 6.) Turn 3: Teja announced that he does not have card 6. Turn 4: Vinay announced that he does not have card 2. Turn 5: Sohail announced that he does not have card 5. After this turn, Teja already knows everything: Vinay's cards are {5, 6} and Sohail's cards are {2, 3}. Thus, the expected number of turns from the beginning of the game to the moment when Teja knew the exact distribution of all cards is always exactly 6. The future rounds do not matter in this case.
Submissions are judged against all 58 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Literature with a public method double expectation(int n, vector<int> Teja, vector<int> history) · 58 test cases · 2 s / 256 MB per case