(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Dmytro Berezin
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
EASY
PREREQUISITES:
prefix sums
PROBLEM:
Find the minimum cost walk between given vertices on a cycle with weighted edges that doesn’t cross any edge more than twice.
QUICK EXPLANATION:
Such a walk between a and b is made up of a path between a and b (there are two of them), a double-path away from a and back, and another double-path from b and back. The minimum cost of the double-paths can be computed in O(N) using suffix/prefix sums and their suffix/prefix minima.
EXPLANATION:
Terminology note: a path in a graph visits each vertex at most once; a walk can visit any vertex or edge any number of times.
Let’s start our walk by moving along the cycle in one direction from a to b. If we never turn around and move through the last visited edge, we can only stop at b or go around the cycle once more afterwards (but that’s just a special case of the general form of the walk which we’ll get to). If we do turn around and it happens after visiting (and leaving) b, then the walk can only go back to b and then stop, since if we go further beyond b, then both edges adjacent to b have been visited twice and we can’t get to b anymore.
If we turn around before or when visiting b, then we have to go to b without changing direction - if we turned around again, there are twice visited edges separating us from b on both sides. After visiting b, we can go further in the same direction, but then, we have to turn around and return to b; this way, we can’t encounter any edge that has been visited exactly once before (but mustn’t cross edges visited twice). Going further back beyond b is forbidden again for the same reason.
This whole casework always yields a specific form for our walk: one path from a to b (either clockwise or anti-clockwise) and two double-paths from a to x and back from to a / from b to y and back to b. Those three parts obviously can’t intersect and any such walk is possible.
So how do we find the minimum cost? Let’s try both choices for the path a-b, compute the minimum cost for each and pick the smaller one. For each of them, the edges that can be in the double-paths can be viewed as an array C[1..M], with the double-paths corresponding to a prefix and a suffix of the array with doubled edge costs. We just need to find the minimum cost of a non-overlapping (but possibly empty) prefix+suffix. Note that edge costs can be negative.
Let’s compute the prefix and suffix sums of costs for convenience. Then, let’s try all lengths of the suffix from M to 0; for each such length l, we need to know the smallest prefix cost among prefixes of length \le M-l. Of course, we can compute those easily from the prefix sums. Finally, we can just take the minimum (suffix cost + minimum prefix cost). This whole procedure takes O(N) time; computing the cost of the path a-b also takes O(N) time and there are just 2 cases, so the time & memory complexities are O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.