182B - Vasya's Calendar

Straightforward implementation.

182C - Optimal Sum

Let us first try to find some “insight” to this problem. Suppose that the optimal set of positions at which we should reverse the sign of the integer, is (i₁, i₂, ..., i_m). One can observe that i_m - i₁ ≤ len must hold, i.e., the leftmost and rightmost reversed positions must fall into some interval of length len. The reason is that there must exist one (maybe multiple) interval of length len that gives the optimal answer, and thus any reversed position that falls out of this interval makes no sense. Therefore, it is safe to modify k as k = min(k, len).

Another observation is that if we are going to reverse k signs, we will either reverse k negative integers or k positive integers. The reason is obvious since a positive integer and a negative integer “cancel” each other. Moreover, we must select the k integers with the maximum absolute values and reverse them.

Based on the above arguments, we can simply enumerate every interval of length len (like a sliding window), and try to obtain a larger value by reversing not more than k signs. For simplicity, we only consider reversing k maximum negative integers (“maximum” means maximum absolute value), since reversing k maximum positive integers is similar.

We can treat every interval of length equal to len as a query. By using “query square root decomposition”, the complexity can be reduced to O(N^1.5) from trivial O(N²). There are a large number of materials talking about this on the internet.

The left work is how to store and update the maximum k integers. I read some of the accepted codes and learned the following technique. We maintain two “set”s maxk and candidatek. The first one stores the maximum k integers while the second stores the other integers that are not the maximum k ones but belong to the current interval. Whenever the sliding window is moved one step further, we should deal with inserting and deleting elements in maxk and candidatek. One should carefully deal with the details involved here.

182D - Common Divisors

Recall that even for integer up to 10⁶, the number of its divisors is only about several hundreds. Therefore, we can calculate all the divisors for each string length in previous, and check which divisors are “string divisor”s. Next, we find the longest common prefix string of the two strings, and denote the length as len. Finally, we find all the common “string divisor”s that is not larger than len.

182E - Wooden Fence

We extend each board to two new boards if it is not a square, by swapping its length and width, while they still have the same “index” (it is required that no neighboring boards should have the same index). In other words, we create two new boards but eliminate the old one. Then, we use dp[i][j] to denote the number of ways to build a fence of length j and the last board has index i. As you may see, the idea is dp but we compute it in a forward manner. From dp[i][j], we should find out all the feasible boards that can be built next to the board with index i, and then move to some dp[k][j + a[k]], where a[k] is the length of board k.