I got to IOI solving — and upsolving — a bit late and I just recently finished it (with help of various comments). One thing I didn't really see there was: how would you have done?↵
↵
Here are my comments about the problems:↵
↵
- aliens: a common DP + convex hull trick; apparently, $O(NK\log)$ gets TLE for the 5th subtask and even $O(NK)$ has trouble fitting within the TL; 60pts↵
↵
- shortcut: I knew that there's binsearch (from a similar TC problem); afterwards, finding an $O(N\log^2)$ solution isn't hard, but improving it enough to get more points is; 93pts↵
↵
- railroad: [mfw](http://knowyourmeme.com/photos/993875-nick-young) — I didn't move beyond a bitset DP; even though I had a lot of ideas including what turned out to be the correct one (finding a flow), I thought it'd be some kind of greedy, but those are numerous and hard to check in this case; the last subtask was very easy after solving the 3rd; 34pts↵
↵
- messy: the bounds are $7\cdot2^7$ with $N=2^7$, so it has to be D&C; full score↵
↵
- paint, molecules: easy 100pt problems↵
↵
So that'd give me 7th place.↵
↵
The first solution I got 93pts for in shortcut was this: when checking if the diameter is $\le D$ and considering $i$ to be the left endpoint, find the largest $j=j_1(i)$ such that a shortcut between $i$ and $j$ gives all distances within the created cycle $\le D$, the largest $j=j_2(i)$ such that all distances between vertices from the cycle and vertices to the left of $i$ are $\le D$, then symmetrically for each $j$ the smallest $i=i_3(j)$ such that all distances between vertices from the cycle and those to the right of $j$ are $\le D$. There are also distances between pairs of vertices not on the cycle, but those are easy. ↵
↵
For $j_2(i)$, we can find the leftmost vertex $k_2(i)$ to the right of $i$ such that it's farther from some vertex to the left of $i$ without a shortcut; then, all other vertices on the cycle must be reachable using the shortcut, so $pos(j_2)-pos(a)+d(a)+C+lft(i) \le D$ for all vertices $a$ between $k_2$ and $j_2$; here, $pos$ is the position of each vertex on the main line (prefix sum of $l$) and $lft(i)$ is the maximum distance to the left from $i$; we can extend it to all vertices $a$ to the right of $k_2$, which gives us a bound on $pos(j_2)$; we can find $j_2$ by binsearching. Also, $k_2$ can be found using an RMQ table for max(pos+d) and an RMQ-like search.↵
↵
With $j_1(i)$, we can do something similar to finding $j_2$ for each vertex, but only for distances to $i$ exactly, not to the left of $i$ (so there's $d(i)$ instead of $lft(i)$); $j_1(i)$ can be computed as their suffix minima.↵
↵
We're left with this problem: there's an interval $I_l(i)$ and $I_r(i)$ for each $i$; are there some $i,j$ such that $j \in I_l(i)$ and $i \in I_r(j)$? This can be solved e.g. using another RMQ table, in which we'll store the minimum left ends of $I_r$ in ranges of $j$; the right ends of $I_r$ aren't important. Then, for each $i$, we can find out if the minimum in $I_l(i)$ is $\le i$. (Alternatively, we can use a sweepline algorithm and store opened $I_r$-s in a set<>.)↵
↵
How simple. /sarcasm↵
↵
I tried to optimise this, but there was no way to squeeze it even into 97 points — surprisingly, since I didn't really need to optimise to get 93pts.↵
↵
I got full score on shortcut using an approach based on [http://codeforces.me/blog/entry/46518?#comment-310338](http://codeforces.me/blog/entry/46518?#comment-310338) (note: extending to all pairs $i,j$ is probably unnecessary and wrong — if $i=j$, we get a non-path which can be longer than $D$). The hardest part is computing the smallest $j_0=j > i$ and largest $i_0=i < j$ such that $u[i]+v[j] > D$, since $u[i]$ and $v[j]$ don't have to be monotonous; afterwards, we can find the smallest/largest sum/difference of $x_1,x_2$ by considering all $j \ge j_0$ / $i \le i_0$, for which we only need prefix/suffix maxima of $u[]$ and $v[]$ and check if the answer exists using 2x 2 pointers in $O(N)$.↵
↵
To compute $j_0$, let's move from $i=N-1$ to $i=0$ and recompute the sequence of closest increasing $v[j]$-s using the well-known stack algorithm. Obviously, we can find $j_0$ by binsearching among them, but that gives $O(N\log^2)$ time complexity. However, if $j_0(i) < j_0(i')$ for $i > i'$, then we can decrease $j_0(i')$ to $j_0(i)$ without affecting the bounds on the sum/difference of $x_1,x_2$; that means we can keep a pointer on the element in the stack (actually an array in the implementation) corresponding to $v[j_0]$ and only move this pointer in one direction and it's $O(N\log)$ in total.↵
↵
This got 97 points instantly, but I still needed some optimisations to get to 100. That time limit was really tight. Other than that, the problems were pretty good and difficult (as expected from Russia); I just missed problems with non-binary scoring per subtask.↵
↵
My codes: [molecules](https://ideone.com/iKi2zr) [railroad](https://ideone.com/tSkR7h) [shortcut](https://ideone.com/ypN9Um) [paint](https://ideone.com/SPXtQh) [messy](https://ideone.com/CwyzEx) [ayyliens](https://ideone.com/H320PF)
↵
Here are my comments about the problems:↵
↵
- aliens: a common DP + convex hull trick; apparently, $O(NK\log)$ gets TLE for the 5th subtask and even $O(NK)$ has trouble fitting within the TL; 60pts↵
↵
- shortcut: I knew that there's binsearch (from a similar TC problem); afterwards, finding an $O(N\log^2)$ solution isn't hard, but improving it enough to get more points is; 93pts↵
↵
- railroad: [mfw](http://knowyourmeme.com/photos/993875-nick-young) — I didn't move beyond a bitset DP; even though I had a lot of ideas including what turned out to be the correct one (finding a flow), I thought it'd be some kind of greedy, but those are numerous and hard to check in this case; the last subtask was very easy after solving the 3rd; 34pts↵
↵
- messy: the bounds are $7\cdot2^7$ with $N=2^7$, so it has to be D&C; full score↵
↵
- paint, molecules: easy 100pt problems↵
↵
So that'd give me 7th place.↵
↵
The first solution I got 93pts for in shortcut was this: when checking if the diameter is $\le D$ and considering $i$ to be the left endpoint, find the largest $j=j_1(i)$ such that a shortcut between $i$ and $j$ gives all distances within the created cycle $\le D$, the largest $j=j_2(i)$ such that all distances between vertices from the cycle and vertices to the left of $i$ are $\le D$, then symmetrically for each $j$ the smallest $i=i_3(j)$ such that all distances between vertices from the cycle and those to the right of $j$ are $\le D$. There are also distances between pairs of vertices not on the cycle, but those are easy. ↵
↵
For $j_2(i)$, we can find the leftmost vertex $k_2(i)$ to the right of $i$ such that it's farther from some vertex to the left of $i$ without a shortcut; then, all other vertices on the cycle must be reachable using the shortcut, so $pos(j_2)-pos(a)+d(a)+C+lft(i) \le D$ for all vertices $a$ between $k_2$ and $j_2$; here, $pos$ is the position of each vertex on the main line (prefix sum of $l$) and $lft(i)$ is the maximum distance to the left from $i$; we can extend it to all vertices $a$ to the right of $k_2$, which gives us a bound on $pos(j_2)$; we can find $j_2$ by binsearching. Also, $k_2$ can be found using an RMQ table for max(pos+d) and an RMQ-like search.↵
↵
With $j_1(i)$, we can do something similar to finding $j_2$ for each vertex, but only for distances to $i$ exactly, not to the left of $i$ (so there's $d(i)$ instead of $lft(i)$); $j_1(i)$ can be computed as their suffix minima.↵
↵
We're left with this problem: there's an interval $I_l(i)$ and $I_r(i)$ for each $i$; are there some $i,j$ such that $j \in I_l(i)$ and $i \in I_r(j)$? This can be solved e.g. using another RMQ table, in which we'll store the minimum left ends of $I_r$ in ranges of $j$; the right ends of $I_r$ aren't important. Then, for each $i$, we can find out if the minimum in $I_l(i)$ is $\le i$. (Alternatively, we can use a sweepline algorithm and store opened $I_r$-s in a set<>.)↵
↵
How simple. /sarcasm↵
↵
I tried to optimise this, but there was no way to squeeze it even into 97 points — surprisingly, since I didn't really need to optimise to get 93pts.↵
↵
I got full score on shortcut using an approach based on [http://codeforces.me/blog/entry/46518?#comment-310338](http://codeforces.me/blog/entry/46518?#comment-310338) (note: extending to all pairs $i,j$ is probably unnecessary and wrong — if $i=j$, we get a non-path which can be longer than $D$). The hardest part is computing the smallest $j_0=j > i$ and largest $i_0=i < j$ such that $u[i]+v[j] > D$, since $u[i]$ and $v[j]$ don't have to be monotonous; afterwards, we can find the smallest/largest sum/difference of $x_1,x_2$ by considering all $j \ge j_0$ / $i \le i_0$, for which we only need prefix/suffix maxima of $u[]$ and $v[]$ and check if the answer exists using 2x 2 pointers in $O(N)$.↵
↵
To compute $j_0$, let's move from $i=N-1$ to $i=0$ and recompute the sequence of closest increasing $v[j]$-s using the well-known stack algorithm. Obviously, we can find $j_0$ by binsearching among them, but that gives $O(N\log^2)$ time complexity. However, if $j_0(i) < j_0(i')$ for $i > i'$, then we can decrease $j_0(i')$ to $j_0(i)$ without affecting the bounds on the sum/difference of $x_1,x_2$; that means we can keep a pointer on the element in the stack (actually an array in the implementation) corresponding to $v[j_0]$ and only move this pointer in one direction and it's $O(N\log)$ in total.↵
↵
This got 97 points instantly, but I still needed some optimisations to get to 100. That time limit was really tight. Other than that, the problems were pretty good and difficult (as expected from Russia); I just missed problems with non-binary scoring per subtask.↵
↵
My codes: [molecules](https://ideone.com/iKi2zr) [railroad](https://ideone.com/tSkR7h) [shortcut](https://ideone.com/ypN9Um) [paint](https://ideone.com/SPXtQh) [messy](https://ideone.com/CwyzEx) [ayyliens](https://ideone.com/H320PF)
