arun_prasad's blog

How to model this problem as a Nim problem?
By arun_prasad, history, 8 years ago, In English

Im trying to solve this problem on hackerrank. I am unable to understand the editorial. If someone could explain the editorial part with proof it would be of great help. Click for problem

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

The original problem states, that you have coins on the squares [0, 1, ...], and in each turn you move a coin from a square to a square with a lower number.

Now we interpret the statement differently: Instead of coin on a square with number x, think of a piles (heaps) with x stones.

For example: if you have two coins on square 1, two coins on square 2 and one coin on square 4, then you can think of two piles with each 1 stone, two piles with each 2 stones and one pile with 4 stones.

Now a move is defined of putting a coin from square x to square y (x>y). In our stone-pile analogy: you take a pile with x stones and transform it into a pile with y stones. So you are basically removing stones.

Now you can see, why this is equivalent to the nim-game. You have piles of stone, and in each step you remove a few stones from one pile.

The classical nim-solution is: if the xor of all piles is != 0, then the first player wins, otherwise the second. So in the example the xor of all piles would be: 1 xor 1 xor 2 xor 2 xor 4 = 4. Therefore the first player wins.

And at the end you can do one final optimization, because there will be a lot of piles with equal sizes: for each number z the following equation holds: z xor z = 0. Therefore if you have even many piles of size z, you already know the answer: z xor z xor z xor ... xor z = (z xor z) ... xor (z xor z) = 0 xor ... xor 0 = 0. And if you have odd number of piles you get: z xor z xor z xor ... xor z = (z xor z) ... xor (z xor z) xor z = 0 xor ... xor 0 xor z = z.

So we only have to xor the sizes, of which there are an odd number of piles. Or translated back to the original statement. Xor all square indices i, where ci is odd.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey thanks for replying , I had one doubt. "Now a move is defined of putting a coin from square x to square y (x>y). In our stone-pile analogy: you take a pile with x stones and transform it into a pile with y stones. So you are basically removing stones." Here you take a pile with X stones and transform it into a pile with Y stones.In this the pile with X stones gets decreased to a pile of Y stones.But those stones may increase the value of the previous index piles right. How are you accounting for that? I hope you understand my doubt.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      No the stones don't increase any other piles.

      Lets say you have the following squares: [0, 2, 2, 0, 1] (same board as before), than this is equalent to the piles 1, 1, 2, 2, 4.

      Lets take the coin from square 4 and move it to square 1, this results in the square configuration [0, 3, 2, 0, 0], or equivalent in the piles 1, 1, 1, 2, 2.

      Here you can see, that moving one coin only affects the one pile (4 -> 1). Nothing else happens. Putting the coin from square 4 to square 1 is the same thing as removing 3 stones from the pile with 4 stones.

      → Reply