RIPPLE - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

First, let f(i) denote the number of flipped bits to count from 0 to 2^i. This can be easily shown to be 2^{i+1}-1. Now, the number of bits flipped to count from 0 to n is simply the sum of f(i) over those i for which the i’th bit is 1. Finally, the number of bits flipped when counting from a to b is just the number of bits flipped couting from 0 to b minus the number flipped when counting from 0 to a. This is all standard fare and seems easier than most “easy” problems on CodeChef.

The interesting part of the question that takes some minor insight is in how to actually compute the sum of the f(i) values. The numbers are up to 100,000 bits long and each f(i) is about i bits long as well. Doing this naively results in a time limit error. The trick is that f(i) is simply represented by a string of i+1 1 bits (e.g. f(2) = 111 in binary). We can add all of the f(i) “at the same time” in one linear time algorithm in the following manner.

Say the number we are counting to is B. Let K be the number of 1-bits in the binary representation of B = b _ {n-1}b_{n-2}…b _ 1b _ 0. Then, we know that the least significant bit of the answer will just be the parity of K since K bits are added to this position. The carry of the K bits is just floor(K/2). If b _ 0 was originally 1, then subtract 1 from K since f(0) will not contribute to future positions in the answer. The number of 1-bits to be added to the second least significant bit of the answer is then the carry plus this new value K. Continue this process of adding the carry plus the current K value to the next bit position and update the carry to be the floor of half of this value. Subtract 1 from K if the position i had b _ i = 1 since f(i) will not contribute to higher-order bits.

For illustration, say B = 110101 so the answer is f(0) + f(2) + f(4) + f(5) = 1 + 111 + 11111 + 111111. The final answer is 1100110.
Writing these f(i) values in binary on top of each other we see:

111111
011111
000111
000001

The least significant bit has 4 1s contributing to it. The carry from adding these 4 is 2 so the second least significant bit has 3 1s plus the carry of 2 contributing to it. Since the total contribution to this position is 5 (which is odd), then the second bit of the answer is 1. The carry from this is floor(5/2) = 2. Carrying this to the third position yields an answer of 1 with a carry of 2 again…

Hi,
I implemented the above method in python and still getting time limit exceeded .
is this something to do with slowness of python compared to C/C++ ?
http://www.codechef.com/viewsolution/2055185