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:
Link to discussion

Problem  E still trying to solve....