Serh.kry's blog

Bit solution of the problem
By Serh.kry, 8 years ago, In English

There was the problem on the last contest which was solved with bit approach by some of top participants: one, two. I just can't understand how it works. Can someone explain?

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

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

Oh, I did it that way! Observe the following pattern (bi represents the ith lower bit of n (1-based)):

Suppose that n has exactly one bit: then, your array will be b1.

If n has two bits, the final array will be b2, b1, b2.

If n has three bits, the final array will be b3, b2, b3, b1, b3, b2, b3.

If n has four bits, the final array will be b4, b3, b4, b2, b4, b3, b4, b1, b4, b3, b4, b2, b4, b3, b4.

You can see that in general, if the lowest significant bit of i is the k th one (1-based), then, the bit in the i th position (1-based) in the array of bits you get is bm + 1 - k, where m is the number of bits n has. This can be formally proved with induction. (Hint: notice that the way the array is built is symmetrical).

Then, for this solution, you only need to iterate from l to r and find those bits. My submission: 24858226

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

    in your code , i & -i ,i dont understand this ,

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

      i& - i gives you the least significant bit of number i. It is the same as (i & (i-1)). The least significant bit of a number is the rightmost bit that is not 0.

      → Reply