Editorial : Bucket Game
Here’s a very simple way to naturally arrive at the solution to “Bucket Game” from today’s Starter, the reasoning of which you can also reuse in future Game theory problems.
There exists a concept of mirroring which is useful in these problems. Moves can be mirrored if the number of entities in the game is even (whether or not mirroring is useful depends on the particular problem, but you should think about mirroring at least once, and then discard it if it’s not relevant).
If you have a single pile, then you can keep mirroring your opponent’s move to win that pile. Winning is only possible if the number of elements in the pile are even. Even if you have infinite piles with even number of stones, you can just mirror the moves on the pile that the opponent chose. Hence, the first player on a set of even piles will lose each pile. Therefore, it is never optimal for the first player to pick an even pile, unless no option’s remaining. Hence, let’s keep all the even piles in one area. And all the odd piles in another area. It’s obvious that no one will touch the even pile until the very end.
The first player will of course make a move on the odd pile, which would then become even, and it would be shifted to the even section. After which, no one will use them till the very end. The second player will also do the same, i.e, pick an odd pile.
So, each player will keep alternating between odd, odd, odd, odd, etc. Notice that there’s no strategy involved for the remaining even piles, i.e, the player who gets those remaining even piles is already decided based on the alternate sequence above. So if you can’t control who gets to walk away with the big chunk of even pile, what is the next best thing that you could do? Of course, you should greedily maximize your score, by taking a pile with 1 immediately (the opponent would do the same).
Hence, you can just simulate the entire process. Sort the array so that the pile with 1 stones are at the front. Then, in each move, each person will greedily take the available 1, once the 1s are consumed, the game is fixed, i.e, everyone has to blindly select one odd pile untill none remain, and one person takes the chunk of even piles accumulated.