Shortest path between any two cities is either shortest path around the circle or shortest path from A to the center plus shortest path from B to the center. Shortest paths to/from the center can be calculated with Dijkstra's algorithm.

Then — bunch of binary searches. For each starting city A remaining cities are separated in three groups based on what is the best way to reach them: go right, go left, go to the center. I find three borders for each starting city: when it becomes better to go through the center than go left, similar for right, and when it becomes better to go right than to go left. Turns out that all these functions are monotonous and we can use binary search. After that — a bunch of prefix sums.

First of all, run dijkstra from center and relax r_i. Now we may notice, that we either go throught center or without going to center. From vertex i, we always go clockwise to some range of vertices [i + 1, i + r], counterclockwise for some range [i — l, i + r] and otherwise throught center. Now use 2 bin.searches in each vertex

Edit: I was too slow :|

First, set R[i] = min cost from i to center (also take into consideration of going around the circle).

For each i, find left[i] = farthest point on the left where you should go around the circle from left[i] to i.

Find right[i] which has similar meaning but to the right.

Array left[i] and right[i] can be calculated in O(N) using 2 pointers.

Then for each i, there are 3 types of vertices:

• left[i] to i
• i to right[i]
• the other vertices

Each type can be calculated in O(1).

So there is no runtime error or anything in your code when you try and read an integer that is not there?

Let's call a pair "splitting" if the friends are in different queues. Let's find the first splitting pair (in lexicographical order). If something "crosses" it, we need to delete these two pairs, solve the problem recursively (for everything before and after it) and returned the doubled product (we can choose the order of deletion of these 2 pairs). Otherwise, we have to delete this pair alone and solve two smaller subproblems again. The base case is when there're no "splitting" pairs (the answer is some binomial coefficient).

Some sketch:

We can see that not too many different configuratons of pair is allowed. So call group in one line "good" if it's of form "aa" or "abab" — it may be processed without going to other line.

Now, while we not finished, calculate and skip good groups. Now in the start you see one of not-so-many configuration of two-line divided groups (or answer is zero). So we can process good groups in any order (it is binomial coefficient) and multiply answer by that number and maybe by 2 if we can process "bad group" in two ways.

Let's try to model the process described in the problem statement.

Suppose, we've already processed first p1 items from the first queue and first p2 items from the second queue. We may either proceed with the operation that depends only on one of the queues or with the operation that depends on both of queues.

Operations that depend only on one queue look as following (operations of the first type):

• aa
• abab

Operations that depend on both of the queues(operations of the second type):

1 way to perform:

• a a

2 ways to perform:

• ab ba
• aba b

Consider, that we made c1 operations of the first type with the first queue and c2 operations of the first type with the second queue before we have to make the operation of the second type. We can arrange them in C(c1 + c2, c1) ways (C is a binomial coefficient), so we should multiply the result by this value. Then we have to perform the operation of the second type (and possibly multiply the result by 2).

If in any step we are unable to perform any of the operations — the answer is 0

http://cepc08.ii.uni.wroc.pl/problems.html G

Why? You note that at a glance when you look at the first sample. Anyway, there was no reason to do so, I don't justify the authors.

what's the difference considering you need both of them?

Will you release screencast of your win, or are you not doing those anymore? It has been nearly a year now :(

One of the reasons I wrote a wrapper class that handles modulus for me. It's used for example in this submission 24049890