[JOISC 2015] Walls

Difficulty Ratings

Idea Creativity: 2/5
Techniques Used: 3/5
Implementation : 3/5

Link

Simplified Chinese Japansese by semiexp

Statement

Imagine you have a range $[A,B]$. An operation is moving to left into $[A-1,B-1]$ using 1 cost, or moving to right into $[A+1,B+1]$ using 1 cost. You can do any operations at any number of times and each operation takes 0 time. Then, there will be $N$ events happening, in event $i$ you have to move your range to cover a point $x_i$. Let $f([A,B])$ be the minimal cost to handle the $N$ events. Given $Q$ queries of $[A_j,B_j]$, find out $f([A_j,B_j])$ for each of them.
$N,Q \le 2e5$.

Solution

So I assume you realise that moving greedily (move towards the point you have to cover if you haven't) is optimal.
Firstly, lets compare $f(0,B-A)$ and $f(A,B)$. Let's find the first position $i$ such that there exist $j < i$ that $|x_i-x_j|>B-A$.
Two observations are to be made:
1) You will end up at the same position after the first $i$ events no matter you start with $[0,B-A]$ or $[A,B]$.
2) You will only move in at most one direction during the first $i-1$ events no matter you start with $[0,B-A]$ or $[A,B]$.
With these observations you can easily compute $f(0,B-A)-f(A,B)$. Therefore, from now on we assume all queries are of the form $f(0,C)$.

Call an event $i$ critical to $[0,X]$ if you start with [0,X] and handle the first $i-1$ events the resulting range does not cover $x_i$.
Let's make more observations
1a. If event $i$ is critical to $[0,X]$ and $x_{i-1} \lt x_i$ then $[0,X]$ will end up at $[x_i-X,x_i]$ after the first $i$ events.
1b. otherwise it would end up at $[x_i,x_i+X]$.
2. If event $i$ is critical to $[0,X]$ it is critical to $[0,X-1]$ too.
If we know the set of critical points for $X$, by maintaining the set of neighbouring pairs of critical points, you can compute $f(0,X)$ easily. So, you just have to find out for each event, what is the largest $X$ such that it is critical to $[0,X]$. You can determine an event is critical or not for $[0,X]$ with the information of the latest event that is critical to it. By some care in implementation you can solve using parallel binary search in $O(NlgM)$.

Comments

Maybe this is the type of data-structure problems that has a chance of appearing in AGC..?