Zombies
Contest: Educational Codeforces Round 148 (Rated for Div. 2)
Difficulty rating: 3200
Tags: binary search, dp

Polycarp plays a computer game in a post-apocalyptic setting. The zombies have taken over the world, and Polycarp with a small team of survivors is defending against hordes trying to invade their base. The zombies are invading for $$$x$$$ minutes starting from minute $$$0$$$. There are $$$n$$$ entrances to the base, and every minute one zombie attempts to enter through every entrance.

The survivors can defend the entrances against the zombies. There are two options:

- manually — shoot the zombies coming through a certain entrance;
- automatically — set up an electric fence on a certain entrance to fry the zombies.

If an entrance is defended either or both ways during some minute, no zombie goes through.

Every entrance is defended by a single dedicated survivor. The $$$i$$$-th entrance is defended manually from minute $$$l_i$$$ until minute $$$r_i$$$, non-inclusive — $$$[l_i, r_i)$$$.

There are $$$k$$$ generators that can be used to defend the entrances automatically. Every entrance should be connected to exactly one generator, but a generator can be connected to multiple entrances (or even none of them). Each generator will work for exactly $$$m$$$ consecutive minutes. Polycarp can choose when to power on each generator independently of each other, the $$$m$$$ minute long interval should be fully inside the $$$[0, x)$$$ time interval.

Polycarp is a weird gamer. He wants the game to be as difficult as possible for him. So he wants to connect each entrance to a generator and choose the time for each generator in such a way that as many zombies as possible enter the base. Please, help him to achieve that!

Input format:
The first line contains four integers $$$n, k, x$$$ and $$$m$$$ ($$$1 \le k \le n \le 2000$$$; $$$1 \le m \le x \le 10^9$$$) — the number of entrances, the number of generators, the duration of the zombie invasion and the duration of all generators.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i < r_i \le x$$$) — the time interval the $$$i$$$-th entrance is defended manually.

Output format:
Print a single integer — the largest number of zombies that can enter the base after Polycarp connects each entrance to some generator and chooses the time for each generator.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
3 3 10 3
0 2
1 7
4 7

Example output:
18

Example input:
3 2 10 3
0 2
1 7
4 7

Example output:
18

Editorial:
First of all, let's rephrase the problem a bit. For each entrance, we will have two time segments: the segment when it is guarded, and the segment when the corresponding generator works. The zombies will arrive through that entrance at every moment not belonging to these two segments; so, if we want to maximize the number of zombies, we want to minimize the length of the unions of these pairs of segments for the entrances; and since the lengths of the segments are fixed, minimizing the union means maximizing the intersection. So, we need to choose the time segments for the generators and assign entrances to generators so that the sum of intersections of segment pairs for each entrance is the maximum possible.
Okay, now we work with the sum of intersections. Suppose there are multiple generators (for which we have already chosen their time segments) and an entrance; is there an easy method how to choose the optimal generator for the entrance? In fact, there is. We need to look at the centers of all segments (both for the generators and the entrance), and choose the generator for which the distance from the center of the entrance-segment to the center of the segment from that generator is the minimum possible (this only works because all generators have the same working time). Mathematically, if the segments for the generators are denoted as $$$[L_j, R_j)$$$, and the segment borders for the entrance are $$$[l_j, r_j)$$$, we need to choose the generator that minimizes the value of $$$|(L_j + R_j) - (l_j + r_j)|$$$, since it also minimizes the distance between the centers of the segments.
Do you see where this is going? In fact, this observation allows us to use exchange argument DP. Suppose the segments for the generators are already chosen; we can sort the entrances according to the values $$$(l_j + r_j)$$$ for each entrance, and then split the sorted order of entrances into several groups: all entrances in the first group are optimal to hook up to the first generator, all entrances in the second group are optimal to hook up to the second generator, and so on. But since the segments of the generators are not fixed, we will instead split the sorted order of the entrances into $$$k$$$ groups, and for each group, optimally choose the segment for the respective generator. So, this leads us to the following dynamic programming: $$$dp_{i,j}$$$ — the maximum possible sum of intersections if we have split the first $$$i$$$ entrances in sorted order into $$$j$$$ groups. The transitions in this dynamic programming are quite simple: we can just iterate on the next group, transitioning from $$$dp_{i,j}$$$ to $$$dp_{i',j+1}$$$.
Unfortunately, there are still two issues with this solution:
• How to reduce the number of transitions from $$$O(n^3)$$$ to something like $$$O(n^2 \log n)$$$ or $$$O(n^2)$$$?
• How to choose the best generator placement for a group of entrances, preferably either in $$$O(1)$$$ or $$$O(\log n)$$$ per one segment of entrances?
Okay, the solution to the first issue is not that difficult. Intuitively, it looks like the running time of this dynamic programming can be improved with some of the well-known DP optimizations. The two that probably come to mind first are divide-and-conquer optimization and aliens trick. Both of them seem to work, but unfortunately, we can prove only one of them (the proof is in the paragraph below). You can choose any of these two optimizations.
Proof that D&C optimization works
We can prove this via quadrangle inequality: let $$$cost[l..r]$$$ be the total intersection for the entrances from $$$l$$$ to $$$r$$$ if the generator for them is chosen optimally, and $$$opt[l..r]$$$ be the optimal starting moment of the generator for entrances from $$$l$$$ to $$$r$$$. We have to show that $$$cost[a..c] + cost[b..d] \ge cost[a..d] + cost[b..c]$$$, where $$$a \le b \le c \le d$$$.
Suppose $$$opt[a..d] = opt[b..c]$$$. Then, if we take all entrances $$$[c+1..d]$$$ from the first group and add them to the second group, then choosing $$$opt[a..d]$$$ as the starting point for these two groups gives us the total intersection equal to exactly $$$cost[a..d] + cost[b..c]$$$. So, in this case, $$$cost[a..c] + cost[b..d] \ge cost[a..d] + cost[b..c]$$$.
Now suppose $$$opt[a..d] < opt[b..c]$$$ (the case $$$opt[a..d] > opt[b..c]$$$ is similar). Let's again try to move all entrances $$$[c+1..d]$$$ from the first group to the second group. If the resulting sum of intersections (without shifting the starting points for the generators) did not decrease, we have shown that $$$cost[a..c] + cost[b..d] \ge cost[a..d] + cost[b..c]$$$. Otherwise, at least one entrance from $$$[c+1..d]$$$ is closer to $$$opt[a..d]$$$ than to $$$opt[b..c]$$$ (in terms of distance between the segment centers). This means that since the centers of the segments in $$$[b..c]$$$ are not greater than the center of the segments in $$$[c+1..d]$$$, then the segments from $$$[b..c]$$$ are also closer to $$$opt[a..d]$$$ than to $$$opt[b..c]$$$. So, the optimal starting moment for $$$[b..c]$$$ can be shifted to $$$opt[a..d]$$$, and we arrive at the case we analyzed in the previous paragraph.
End of proof
The solution to the second issue is a bit more complex. First of all, notice that the only possible starting moments for generators we are interested in are of the form $$$l_i$$$ and $$$r_i - m$$$, so there are only $$$2n$$$ of them. Then let's try to understand how to evaluate the sum of intersections for the generator starting at some fixed moment and a segment of entrances. The model solution does some very scary stuff with logarithmic data structures, but the participants of the round showed us a much easier way: create a $$$2n \times n$$$ matrix, where the number in the cell $$$(i, j)$$$ is the intersection of the segment for the $$$i$$$-th starting moment of the generator, and the segment when the $$$j$$$-th entrance (in sorted order) is guarded; then, for a segment of entrances and a fixed starting moment of the generator, the total intersection can be calculated in $$$O(1)$$$ using prefix sums on this matrix.
Unfortunately, trying each starting moment for every group of segments is still $$$O(n^3)$$$. But it can be improved using something like Knuth optimization: let $$$opt_{l,r}$$$ be the optimal starting point of the generator for the group of entrances $$$[l..r]$$$; then $$$opt_{l,r}$$$ is between $$$opt_{l,r-1}$$$ and $$$opt_{l+1,r}$$$, so calculating these optimal starting points in the style of Knuth optimization gives us $$$O(n^2)$$$. However, there's one last nasty surprise waiting for us: if we are not careful about choosing optimal starting moments, it's possible that $$$opt_{l,l} > opt_{l+1,l+1}$$$ (for example, if the segment for the entrance $$$l$$$ includes the segment for the generator $$$l+1$$$), which breaks the initialization of Knuth optimization. To resolve this issue, we can initialize the values of $$$opt_{l,l}$$$ in a monotonic way, choosing $$$opt_{l+1,l+1}$$$ only from values not less than $$$opt_{l,l}$$$.
Implementing all of this results in a solution that works in $$$O(n^2 \log n)$$$.