Read the problem first!
It’s a problem from yesterday’s contest Honour Code.
Many seemed to be confused regarding the approach to this problem. So, I will try to make things lucid for you!
Focus on basics. No need to mess up with unnecessary stuff.
Any cp problem(easy to hard) can be solved with simple logic. No need to fear those daunting terms and algo’s which scare us while solving problems. Just think of it as simple logic game.
After all algo’s are again result of logical thinking of (people) only.
See, a move is defined as dividing operation of (only one pile, in one move) into two non-empty piles, that is at least 1 should be present in both divided piles.
So basically if you have >1 notes in one pile, that’s good for a move on that pile, otherwise not.
Consider the case with two piles, one with one note and other with x notes, its common sense if the nim addition of (1-1) and (x-1) is 1 , you have a winning strategy, otherwise zero.
How?
If nim on your turn is 1, you can turn it to zero for other player. And at some point that zero nim for other player will be equivalent to 1 note in all piles and hence him losing.
But how you will turn it to zero nim for other player, if you have nim 1 on your turn.
To be clear, nim addition is xor. Or luckily found out to be exactly same and making our lives easier.
Now back to question, how you will make nim to zero for other player if you have nim 1 on your turn, with respect to move defined in this particular problem.
How? How? How?
Again, read the move description:
At each move, a player can choose a pile, remove as many notes as he wishes or remove no notes from the pile, and he has to split the remaining pile into two new piles (not necessarily equal), each with a non-zero number of notes.
So, you have the courtesy to remove notes as well as split remaining notes.
If you have nim 1 on your turn, you can always turn nim to zero for other player by choosing suitable pile and splitting in a particular manner.
For example, consider 3 piles with 4, 5, 6 notes. Nim piles 3,4,5 (I have already explained, why -1, because 1 note pile is not a valid pile for a move).
3^4^5 = 2
So, non-zero nim for player 1, but now he has to convert it to nim zero for other player,
So, he can transform original piles like 4,5,6 to 3,5,6(removing one) then splitting 1, 2,5,6 .
And nim piles are 0, 1, 4, 5 .
Now nim addition is 0^1^4^5 = 0. Voila!
So, this way, he will always win getting non-zero nim on each turn, because there is no way player 2 getting nim 0 can leave it to nim zero for other player.
Hence, solution is simply, xor all (notes-1).
If nim initially is non-zero, player 1 wins, else player 2 wins.
Sweet and Simple! 