Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh




Greedy and Game Theory.


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.


  • Bob can only win, if, after removing empty piles from the input, both tables have exactly the same composition of piles.


First 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 Complexity

Time complexity is O(N*logN+M*logM) per test case. Log factors due to multiset operations.


Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

The second test case is wrong, Bob will win no matter how chalie and Alice play.

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:

  1. Initially Alice has no move at all - she loses.
  2. Alice only has one stone to remove, and Bob has single non-zero pile, so after first round there are no more stones and Charlie can’t save Alice.

My solution has a few more “if X then Bob wins” compared to the model solution, yet it passes :slight_smile:

Charlie will always assign Alice to 2nd table, while Alice will remove one stone at each step.

How can Bob win then?

1 Like

I’ll play Charlie and Alice, you play Bob. Here goes:

Initial state: A:(1,2,4); B:(7)

Charlie: “Switch!”
state: A:(7); B:(1,2,4)
Alice: “So many stones, they’re gone”
state: A:(); B:(1,2,4)

Your turn, Bob. Warning: Charlie’s going to call out “Switch” again.

1 Like

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 CodeChef: Practical coding for everyone fails on the case

1 1

Also this solution got accepted:
If the all the three values of ( sum \ of\ piles , xor\ of\ piles , number\ of\ nonempty\ piles ) are same for both table, then “Bob wins” Else “Alice wins”