GAME THEORY IN COMPETITIVE PROGRAMMING
Game Theory in Competitive Programming Series: Part 3
Part 3 of Game Theory in CP —Ticket Game(Codeforces)
Welcome to part 3 of this series, in case you have missed part 2, here is the link: https://medium.com/intellectually-yours/game-theory-in-competitive-programming-series-part-1-7be1d8d6d159
PROBLEM STATEMENT
Monocarp and Bicarp live in Berland, where every bus ticket consists of n digits (n is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even.
Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first n/2 digits of this ticket is equal to the sum of the last n/2 digits.
Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from 0 to 9. The game ends when there are no erased digits in the ticket.
If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.
Input
The first line contains one even integer n(2≤n≤2⋅10⁵) — the number of digits in the ticket.
The second line contains a string of n digits and “?” characters — the ticket which Monocarp and Bicarp have found. If the i-th character is “?”, then the i-th digit is erased. Note that there may be leading zeroes. The number of “?” characters is even.
Output
If Monocarp wins, print “Monocarp” (without quotes). Otherwise print “Bicarp” (without quotes).
Examples
Input
4
0523
Output
Bicarp
Input
2
??
Output
Bicarp
Input
8
?054??0?
Output
Bicarp
Input
6
???00?
Output
Monocarp
HINT 1:
First try to look for a pattern in the sequence of optimal moves by both the players, a player will always try to replace a ‘?’ from the other half with the same number the previous player chose.
HINT 2:
Now when the sum of numbers in next moves make both the sums equal then Bicarp will win.
SOLUTION
Let’s go through all the optimal choices a player can choose. Firstly Monocarp can make a move by replacing the ? in any of the two halves where at least a ? is present. Let’s look at the next move, Bicarp will now perform in order to make the two sums equal. He can choose any of the two optimal strategies mentioned below:
- Replace a ? from the same half which the previous player chose.
- Replace a ? from the other half
From the above-mentioned choices, Bicarp can choose any but now we have to look for some pattern to make the implementation easier. To create a pattern we have to make Bicarp always use the second option, also Bicarp will prefer to replace a ? by the same number which Monocarp used in the previous chance, as a result, the difference between two sums will always be the same as it was before the game started. Hence this is an optimal strategy which both players will use till every ‘?’ from at least one half gets replaced.
Now there is a subsequence of ‘?’ in at most one of the halves(if there were the same number of ‘?’ in both the halves then there will be no ‘?’ left). Let’s call the number of ‘?’ left as L.
Bicarp has some chances to win when the sequence of ‘?’s is in the part with a smaller sum but will always lose if it was in the other half as one of the sums will always exceed the other. After the above operations, it is the chance of Monocarp as we have replaced even numbers of ‘?’ from the sequence. Now Monocarp will prefer not to add anything to the sum or add the greatest digit,i.e., 9 to make the sum of that half less than or greater than the sum of the other half respectively, but as Bicarp will have the same number of chances left(L/2) as that of Monocarp, he will try to make the sums equal. Now if adding L/2 times 9 to the smaller sum makes the two sums equal then Bicarp will win at the end, because if Monocarp chooses a number say x then Bicarp in the next turn will choose 9-x as the replacement for a ?. So here in this only case, Monocarp is unable to win according to the strategy.
Hence, Bicarp can only win if the left sequence of ‘?’ is in the part which has the smaller sum, and adding L/2 times 9 to it makes the two sums equal. In all the other cases Monocarp will surely win as there is an optimal strategy favoring him.
CODE
C++: https://codeforces.com/contest/1215/submission/95656201
That’s all for today! Stay tuned for Part 4of Game Theory in CP.
