Problem Link:
Setter: Alei Reyes
Tester: Triveni Mahatha
Editorialist: Triveni Mahatha
Difficulty:
Easy
Prerequisites:
Combinatorial Game, Greedy
Problem:
Dee and Dum play modified nim game on N stacks of stones. Each stone can be of two types - 0 or 1. Dee can remove stones from a stack whose topmost element is 0. And Dum can only remove from stack with 1 at the top. If both play optimally who will win?
Explanation:
Note that to win the game, every player will try to pick stones such that number of moves for him is as large as possible before the end of the game. And, number of moves for the other player is as little as possible. This way he can make the other player run out of moves and can win.
How to achieve that?
Consider Dee. He can pick stones from stacks with top element as 0. So in every step, he will have to remove at least one 0-stones. How about picking exactly one 0-stone in each step? This way we see that he will waste no stones which are useful to him. Also, he can try to waste some of the stones of the other player by removing all consecutive 1-stones just below the top 0-stone. This gives him multiple advantages.
First, he picks no more than one 0-stone. Second, after removal of those stones, the top stone in the stack is still 0-stone. This means in future moves he can use this stack. Third, he wastes some 1-stones which are useful for the other person.
Using this strategy, he can make sure that all stacks whose top element is 0-stone will be used only by Dee, similarly other stacks will be used by Dum.
How many total moves Dee can make? It is number of 0-stones in all the stacks with top stone as 0-stone. Call this number stoneCountDee . Similary, let’s define stoneCountDum as number of 1-stones in the stacks with top element as 1-stone.
If Dee moves first, he can win iff stoneCountDee > stoneCountDum.
If Dum moves first, he can win iff stoneCountDum > stoneCountDee.
SOLUTION:
Time Complexity:
Let’s denote S be total number of stones in all N stacks. Then,
Time complexity is O(S) per test case.
Space Complexity:
O(S)
