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....