PROBLEM LINK:
Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
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
- Bob can only win, if, after removing empty piles from the input, both tables have exactly the same composition of piles.
EXPLANATION
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.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 