652A - Габриел и гусеница
The problem was suggested by unprost.
Let's consider three cases.
h1 + 8a ≥ h2 — in this case the caterpillar will get the apple on the same day, so the answer is 0.
The first condition is false and a ≤ b — in this case the caterpillar will never get the apple, because it can't do that on the first day and after each night it will be lower than one day before.
If the first two conditions are false easy to see that the answer equals to
.
Also this problem can be solved by simple modelling, because the heights and speeds are small.
Complexity: O(1).
652B - z-сортировка
The problem was suggested by Smaug.
Easy to see that we can z-sort any array a. Let 
be the number of even positions in a. We can assign to those positions k maximal elements and distribute other n - k elements to odd positions. Obviously the resulting array is z-sorted.
Complexity: O(nlogn).
652C - Враждебные пары
This is one of the problems suggested by Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A.
Let's precompute for each value x its position in permutation posx. It's easy to do in linear time. Consider some foe pair (a, b) (we may assume posa < posb). Let's store for each value a the leftmost position posb such that (a, b) is a foe pair. Denote that value as za. Now let's iterate over the array a from right to left and maintain the position rg of the maximal correct interval with the left end in the current position lf. To maintain the value rg we should simply take the minimum with the value z[lf]: rg = min(rg, z[lf]). And finally we should increment the answer by the value rg - lf + 1.
Complexity: O(n).
652D - Вложенные отрезки
The problem was suggested by Alexey Dergunov dalex.
This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each i we should count the number of indices j so that the following conditions are hold: ai < aj and bj < aj. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment.
So the condition ai < aj is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition bj < bj is hold by taking the prefix sum in data structure (the second dimension).
Complexity: O(nlogn).
652E - В погоне за артефактами
The problem was suggested by Alexey Dergunov dalex.
Edge biconnected component in an undirected graph is a maximal by inclusion set of vertices so that there are two edge disjoint paths between any pair of vertices. Consider the graph with biconnected components as vertices. Easy to see that it's a tree (if it contains some cycle then the whole cycle is a biconnected component). All edges are destroying when we passing over them so we can't returnto the same vertex (in the tree) after leaving it by some edge.
Consider the biconncted components that contains the vertices a and b. Let's denote them A and B. Statement: the answer is YES if and only if on the path in the tree from the vertex A to the vertex B there are an edge with an artifact or there are a biconnected component that contains some edge with an artifact. Easy to see that the statement is true: if there are such edge then we can pass over it in the tree on the path from A to B or we can pass over it in biconnected component. The converse also easy to check.
Here is one of the ways to find edge biconnected components:
Let's orient all edges to direction that depth first search passed it for the first time.
Let's find in new directed graph strongly connected components.
Statement: the strongly connected components in the new graph coincide with the biconnected components in old undirected graph.
Also you can notice that the edges in tree is the bridges of the graph (bridges in terms of graph theory). So you can simply find the edges in the graph.
Complexity: O(n + m).
652F - Муравьи на круге
The problem was suggested by Lewin Gan Lewin.
The first observation: if all the ants are indistinguishable we can consider that there are no collisions and all the ants are passing one through another. So we can easily determine the final positions of all the ants, but we can't say which ant will be in which position.
The second observation: the relative order of the ants will be the same all the time.
So to solve the problem we should only find the position of one ant after t seconds.
Let's solve that problem in the following way:
Consider the positions of all the ants after m time units. Easy to see that by the first observation all the positions of the ants will left the same, but the order will be different (we will have some cyclic shift of the ants). If we find that cyclic shift sh we can apply it
times.After that we will have only t ± od m time units.
So the problem now is to model the process for the one ant with m and r ± od m time units. Note that in that time interval the fixed ant will have no more than two collisions with each other ant. So if we model the process with ignoring all collisions except the ones that include the fixed ant, we will have no more than 2n collisions.
Let's model that process with two queues for the ants going to the left and to the right. Each time we should take the first ant in the queue with opposite direction, process the collision and add that ant to the end of the other queue.
Hint: you will have a problem when the fixed ant can be in two different positions at the end, but it's easy to fix with doing the same with the next ant.
Complexity: O(nlogn).
