Matrix.code's blog

Game with Nim

By Matrix.code, 9 years ago, In English

The problem statement as follows :

I have total N coins & I have to make K piles . I have to distribute the coins into the piles so that each piles contain >=1 coins . 
Output a permutation of K number (Which denotes the number of coins in each piles ) that the first player to move lose in **Normal Nim Game**
More specefic : two condition :
1. n1 + n2 + n3 +... ... + nk = N
2. n1 ^ n2 ^ n3 ^ ... ... ^nk = 0

Here n <= 10^8 , k <=N Time : 3s

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

»
9 years ago, # |
← Rev. 7   Vote: I like it +2 Vote: I do not like it

An O(k + logN) solution:

1) Set to 1 the first bit in numbers. If then set to 1 the second bit of the last 2 numbers. Subtract all considered bits from n.

2) Now we do not need to care about the condition ni > 0 anymore. Pick the biggest and set to 1 (z - 1)-th bits of the first 2 numbers. If thay are already set then assign them 0 and try to put 1 on z-th bit and so on. Subtract 2z from n and repeat.

For some n there will be no solution.

The only problem will be with k = 3, z ≤ 1.
I believe you are able to deal with this case :)

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

    bitwise xor of k bits will be zero if there is even number of 1 .. That's the first observation I have made .. But how this will all sum up to N ?

    I don't understand .. PavelSavchenkov Can you explain more . please ?

    → Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

My different approach: Let's decompose n to his binary notation b1b2... We take every bit of n — adding ith bit as two i - 1th bits to next two nl numbers. For example N = 23, we add 8 to 1th and 2nd number, we add 4 to 3rd and 4th number and so on (modk).
It can happen that we used all k number and our job is done.
But if we didn't?
We have to make "push" operations:
Let's take ai and ai + 1 — the two smallest used numbers. They have j-th bit turned on. We move this bit one forward (»1) and add 2j - 1 to ai + 2 and ai + 3 (sum stays the same and xor = 0). We keep doing these until we can or we used k numbers. If we didn't, there is no solution.

Complexity: O(k + logn) — at most k / 2 push operations.

→ Reply