HekpoMaH's blog

NEED HELP
By HekpoMaH, 11 years ago, In English

Recently I attended YANDEX qualification round and i solved 2 problems. When the solution came out, i realized that there is no tutorial, so i didn't manage to understand problem C by just viewing the source. Can you explain this task particularly and probebly some other too? A LOT OF THANKS!!!

UPD. What about the rest of the tasks. Can you give any hints?

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

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

you have to count the number of winning moves in the game of Nim, it is well known problem http://en.wikipedia.org/wiki/Nim

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

    Unfortunately, the heaps are 2*10^9 so a straight algo wont work :(

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

      You can calculate nim-sum bit by bit. Suppose, n = 5:

      numberbits
      0000
      1100
      2010
      3110
      4001
      5101
      nim100

      Now consider the nim. Obviously, the bit in nim is 1 iff the number of corresponding 1-bits in all piles is odd. So, all you have to do is to count the number of 1-bits in all the piles for the given nim bit. An easy task to do once you notice that bit pattern is periodic (01 for 0th bit, 0011 for the 1st, 00001111 for the 2nd, etc.)

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

        Good, but how can you compare whether the nim is smaller than the heap fast.

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

          What you actually need to do is:
          1. Find the nim-sum of all the numbers from 1 to N (using the approach described)
          2. Find the most significant bit of that nim-sum
          3. Find the number of piles with this bit set to 1. (Using the very same approach. You can even use the results from the first step.)
          UPD. It's just occurred to me. Why even bother and find actual nim-sum? Combine 3 steps into one: just find the highest bit for which the number of piles with this bit set is odd. That odd number is your answer (0 if there's no such bit). I've just accepted this idea.

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

            UPD. It's just occurred to me. Why even bother and find actual nim-sum? Combine 3 steps into one: just find the highest bit for which the number of piles with this bit set is odd. That odd number is your answer (0 if there's no such bit). I've just accepted this idea.

            Can you give an example? I still dont understand it. :(

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

      it is easy to google direct formula for : s(N) = N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) )

      → Reply