Friday, November 7, 2014

Codeforces Round #276 (Div. 1)

Very challenging problems..

Problem A:
484A - Bits

Solution:
Let me describe a greedy strategy to solve this problem. We can represent the left number L and the right number R as binary strings, and let A be the smallest binary string that maximizes the number of ON bits such that L <= A <= R. This means that L and R are valid candidates for A. Now, construct a binary string M by modifying R as follows:
From the most significant bit of R to the least significant bit, we want to find the first ON bit in R such that if we turn this bit OFF and turn the rest of the bits after that bit ON, we get a number that is still higher or equal to L. For example, if R = 1000101 and L = 0100101, then by turning the MSB OFF and the rest of the bits after MSB ON, we get M = 0111111 which is still $$\geq$$ L. Stop when we find such bit.

Now M has potentially more ON bits than R and L, and M is the smallest possible number such that we can possibly have more ON bits than R. "Potentially", because we need to check which ones are actually has bigger popcount. Hence a final check is needed to decide which of L, R, and M that has the biggest popcount.

Problem B:
484B - Maximum Value

Solution:
This problem requires some insight and some knowledge on harmonic series to confidently solve. Firstly notice that for each $$a_j$$, rather than checking each $$a_i \bmod{a_j}$$ one by one which requires $$O(N)$$ complexity, we are better off checking the maximum $$a_i$$ that is smaller than multiples of $$a_j$$. This can be done using binary search, but a better way is to store the value of such information on an array beforehand, i.e. an array where cell i contains the biggest $$a_i$$ that is smaller than i. Then the number of checks we need for each $$a_i$$ will be $$O(\frac{M}{a_i})$$ for $$M$$ an upper bound which can be chosen as twice the biggest $$a_i$$. In total, we have a running time complexity of (after sorting) $$\sum_i O(\frac{M}{a_i})$$. Here we note that the sum is less than $$M(\sum_{k=1}^{M} \frac{1}{k})$$, which is a harmonic series. And here is a good knowledge about harmonic series to keep in mind: its sum is $$O(\lg{M})$$. So with that we are sure that the running time is $$O(M\lg{M})$$ which is still quite good under the given constraints.

Problem C:
The problem is too awesome to merit its own post: Codeforces #276 (Div. 1) Problem C - Strange Sorting

Problem D: