PROBLEM LINK:Setter: Bogdan Ciobanu DIFFICULTY:Easy PREREQUISITES:Greedy and Game Theory. PROBLEM:Given $N$ piles on table 1 and $M$ piles on table 2, Three players Alice, Bob, and Charlie play a game, with moves in order Charlie, Alice, and Bob respectively. Charlie assign both of them to one table exactly, Alice first removes a stone from one or more stones from one of the pile at her table, then Bob removes one or more stones from one pile on his table. The player unable to make a move loses. SUPER QUICK EXPLANATION
EXPLANATIONFirst of all, remove the empty piles from both tables. (Constraints mention $A_i, B_i \geq 0$, which may include piles of size 0) Suppose Only Alice and Bob are playing this game, with Alice removing stones from the first table while Bob removing stones from the second table. We can see, that the winning strategy is to remove exactly one stone at every turn. Winner will be Alice if she has strictly more stones than Bob Since Alice plays first. But, with Charlie, the strategies change. See, if at any point of Charlie's turn, if one table contains more stones than the other, Charlie will always assign Alice to that table, and Alice will always remove only one stone, thereby, can play moves equal to the number of stones at the table having more stones. Due to lack of stones, Bob loses, since his table always contain fewer stones than that of Alice. So, Initial observation is that Bob can win only when both tables have the same number of stones. Since Bob plays second, He will always remove the same number of stones as Alice removes in the same turn. But the question is, can he always remove the same number of stones as Alice. There's still a catch. What happens, even if both tables have the same number of stones but in the different composition. It turns out, Alice can win in that case too. Consider an example, Table 1 has 1,2,4 piles while table 2 has piles 2,5 Total number of stones is same, yet Alice can win. Charlie can assign Alice to the second table and Alice removes all stones from the pile with size 5. But Bob cannot remove 5 stones in any way. The number of coins at table 1 will be greater than that at table 2, hence, Alice will be assigned the first table after that always, and thus, will win. So, in order to be able to remove the same number of coins as Alice, Bob needs all the piles to be exactly the same. The proof is, that if tables have different compositions, the Charlie will repetitively assign Alice to the table having largest pile and Alice will remove the largest pile, till the number of stones at both tables is equal, or there is only one pile left on both tables. Hence, If after removing all empty piles from the input, all remaining piles are same, the Bob can repeat the same moves as Alice, irrespective of Charlie's superpowers, and will win. This can be easily checked using multiset or even an array or frequency array or whatever idea you may think of. Time ComplexityTime complexity is $O(N*logN+M*logM)$ per test case. Log factors due to multiset operations. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 03 Nov '18, 16:35

Random observation about the test data: I misread statement (and thought that Charlie only acts for first time after first round of moves by Alice and Bob) and because of that the problem became somewhat more tricky. Here are some interesting cases:
My solution has a few more "if X then Bob wins" compared to the model solution, yet it passes :) answered 15 Nov '18, 21:25
Lucky I guess. xD I believe it is simply not possible for the tester to anticipate every unique solution coming up in the contest, so that might be the reason for not getting WA. Like, Assuming Charlie can assign table only at first move, He will not assign Alice the table with the lesser number of stones, so, Alice shall lose if and only if Number of stones on both tables is same. Even if we assume that Charlie can assign table only at first move, Your solution https://www.codechef.com/viewsolution/21410139 fails on the case 1
(17 Nov '18, 07:53)
