LiteratureOptimal
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 an arbitrary one of the 2*N cards they don't have, and makes a true statement "I don't have the card number X."
You are given the
Teja remembers everything that was said during the game. Compute and return the smallest nonnegative X such that it is possible that after X more turns Teja will know the exact distribution of all cards.
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.
2
{1,4}
{}
Returns: 5
Here, history is empty, so we are at the beginning of the game. The most optimistic scenario is that Teja will learn everything in five turns. Here is one possible way how that can happen: Turn 0: Teja announces that he does not have card 6. Turn 1: Vinay announces that he also does not have card 6. (At this moment, Teja knows that Sohail must have card 6.) Turn 2: Sohail announces that he does not have card 2. Turn 3: Teja announces that he does not have card 3. Turn 4: Vinay announces that he does not have card 5. After these five turns Teja can conclude that Vinay must have cards 2 and 3, while Sohail has cards 5 and 6.
2
{1,4}
{6,6,2,3,5,1,5,6}
Returns: 0
This time the players already took eight turns of the game. The first five turns are the same as in Example #0. Teja already knows everything, so he does not need any additional turns.
2
{3,6}
{1,3,3,1,3,3,1,3,6,1}
Returns: 4
Here, the other two people did not give Teja any useful information because they always mentioned his cards. Thus, the answer is almost the same as in Example #0. Only one thing is different: In this game, Teja took the last turn, so the next turn will be taken by Vinay. Therefore, only four extra turns (Vinay, Sohail, Teja, and Vinay again) are needed in this case.
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: 0
2
{6,2}
{}
Returns: 5
Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LiteratureOptimal with a public method int minTurns(int N, vector<int> Teja, vector<int> history) · 60 test cases · 2 s / 256 MB per case