Codeforces Round #1109

very dp heavy contest, i think there was something of a theme running there under dp as well.

Problem A

We can think of each line segment as an independent problem. In particular, if a line segment has length l, then it takes ceil(l/2) operations to clear. Hence, max_i(ceil(li/2)) is the answer.

Problem B

The greediest strategy is to try to conform the list to 1, 2, 3, 4, .... In particular, any books which are extra to this pattern can be bumped to later stacks. As long as there are sufficient books to form the pattern, the answer is yes, otherwise no.

Problem C

We can form a partition over the elements over the array based on which are reachable from each other. We know that this forms a partition because reachability forms an equivalent class, in particular

• Reflexive: any element is reachable from itself
• Symmetric: if element A is reachable from element B, then element B is reachable from element A (by using the same jumps)
• Transitive: if element A is reachable from element B, and element B is reachable from element C, then element A is reachable from element C

Hence, we perform disjoint set unions to join each element at index i, with elements at index i + x and i + y. (this also joins elements j to elements j - x and j-y)

Problem D

This problem requires bashing a few sums, so bear with me.

Suppose there was a post with impact value $b_1$. The total productivity is $$\sum_{0\le i<n} a_i$$ However, by taking the post with impact value $b_1$, the total productivity is $$\sum_{0\le i\le b_1} -a_i + \sum_{b_1< i<n} a_i =-\sum_{0\le i\le b_1} a_i + \sum_{b_1< i<n} a_i$$ This shows that the negative sign carries to the outside of the sum (linearity of mult by -1).

Now, let's suppose we also want to take post $b_2$ with $b_1 < b_2$. The total productivity is $$+\sum_{0\le i\le b_1} a_i - \sum_{b_1< i\le b_2} a_i + \sum_{b_2< i<n} a_i$$ We can visualize this as the range $[0,b_1]$ getting double flipped. In general, we can imagine partitioning $[0, n)$ into ranges $[0,b_1], (b_1, b_2], (b_2, b_3], ..., (b_{m-1}, b_m], (b_m, n)$. These ranges can be arbitrarily flipped through taking some motivational posts.

The best strategy is to take the posts which makes each of the ranges maximal. In particular, the sum of the range can either be $$\sum_{i=b_i}^{b_{i+1}} a_i, -\sum_{i=b_i}^{b_{i+1}} a_i$$ for which $$\max\left\{\sum_{i=b_i}^{b_{i+1}} a_i, -\sum_{i=b_i}^{b_{i+1}} a_i\right\} = \left|\sum_{i=b_i}^{b_{i+1}} a_i\right|$$ A key insight is that we actually don't need to determine which posts to take, we can simply reason about the impact of taking the optimal set of posts. Also note that the last range is always as is.

Problem E

This problem builds on many of the ideas in Problem D.

In order for the final string to be alternating,

A key insight is that flipping a given range does not affect the alternating nature of that range. Hence, a flip of a range is only used to modify the alternating nature of the ranges immediately adjacent (before and after) to it. Note that each range flip can be used to modify two seperate locations where the string is not alternating. It can also be used to modify a single location by flipping a range from 1 to the location. Hence, we can use a prefix sum array to keep track of for each range (between the given $l, r$) how many non-alternating locations exist ($x$), then using $\lceil \frac{x}{2} \rceil$ flips to fix the non-alternating locations.

Problem F

The key to solving this problem is effectively visualizing the rotation operation.

Note that

• Relative order is preserved in rotation
• Rotating parents do not affect the relative order of their children

Hence, the only way to have a valid ordering is if

• The children of a node can be made to be ordered
• The ranges of the higher nodes are disjoint and ordered (specifically if one node has, for example, children 1, 4 and the other has children 2, 5 this is not sortable)

Hence, a simple DFS, while keeping track of the ranges of the children, is sufficient to solve this problem.

Problem G

This is a DP problem, with dp transition as $$dp[i] = \left(\max_{j < i - a[i]\text{ and }j + a[j] < i} dp[j]\right) + a[i]$$ In particular, $dp[i]$ is the maximum number of books which can be collected if we take index $i$ (and end there). This might at first look like an $O(n^2)$ dp. Two mechanisms allow this to be $O(n)$.

First, we need some mechanism to query $$max_{0 \leq j < i - a[i]} dp[j]$$ This is achiveable with a max fenwick tree.

Next, we need some mechanism to introduce values into the fenwick tree when they are allowed to be queried. Specifically, this is to achieve the $j+a[j]<i$ part of the max constraints. We need to introduce $dp[i]$ into the fenwick tree at index $i + a[i] + 1$. This is achiveable with a priority queue. While traversing through the array, we can pop from the priority queue all elements which are allowed to be queried, and introduce them into the fenwick tree.