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, gets TLE for the 5th subtask and even

*O*(*NK*) has trouble fitting within the TL; 60ptsshortcut: I knew that there's binsearch (from a similar TC problem); afterwards, finding an solution isn't hard, but improving it enough to get more points is; 93pts

railroad: mfw — 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·2

^{7}with*N*= 2^{7}, so it has to be D&C; full scorepaint, 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 ≤ *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 ≤ *D*, the largest *j* = *j*_{2}(*i*) such that all distances between vertices from the cycle and vertices to the left of *i* are ≤ *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 ≤ *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*) ≤ *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 and ? 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 ≤ *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.com/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* ≥ *j*_{0} / *i* ≤ *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 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 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.

Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).