CHEFCCYL - Editorial

r_64 · August 22, 2017, 8:25pm

Ah, I could have used the [hid e][/h ide] function if I knew it earlier. This would make editorials clearer, I think.

PROBLEM LINK:

Practice

Contest

Author: Full name

Tester: Full name

Editorialist: Full name

DIFFICULTY:

CAKEWALK, SIMPLE, EASY, MEDIUM or HARD.
Intermediate levels like SIMPLE-EASY, EASY-MEDIUM, MEDIUM-HARD are also possible.

PREREQUISITES:

Greedy, DP, Math etc. Ideally with the links to Wikipedia

PROBLEM:

Click to view

There are N cycles(some kind of weighted undirected graphs) and N additional edges. The i-th additional edge connects some node on the i-th cycle and some node on the (i+1)-th cycle. Specially, the N-th additional edge connects some node on the N-th cycle and som node on the 1-st cycle. Every edge has a weight. You need to answer Q queries, each query asks you the length of the shortest path between some two nodes.

QUICK EXPLANATION:

Let’s call the endpoints of additional edges "keypoint"s. The topology of keypoints form a cycle, so we can handle distance queries of keypoints quickly. For a general query, let’s say it’s from vertex v_1 on cycle c_1 to vertex v_2 on cycle c_2. The path goes through some keypoint k_1 on cycle c_1 and some k_2 on cycle c_2. Since every cycle has at most 2 keypoints, we enumerate k_1 and k_2, and thus answer queries on constant time.

EXPLANATION:

Subtask 1

This is a shortest path problem on a graph with M=A_1+A_2+\dots+A_N vertices and M+1 edges. We can run Dijkstra’s Algorithm for each query. The time complexity for heap-optimized Dijkstra’s Algorithm is O(M\log M). So total complexity is O(QM\log M).

Subtask 2

Querying on one cycle

Consider the easier problem: you have one cycle and you want to answer distance queries. Let’s number the vertices 1,2,\dots,N, and suppose the cycle is 1-2-3-\dots-N-1. For any i,j(i < j), the only simple paths between i,j are:

i\to (i+1)\to(i+2)\to\dots\to j, length l_1;
i\to (i-1)\to\dots\to 1\to N\to (N-1)\to\dots\to (j+1)\to j, length l_2.

The two paths

Let’s precompute d_i as the length of path 1\to 2\to\dots\to i. Then l_1=d_j-d_i. Since l_2+l_1 is the length of the whole cycle, l_2 can be easily calculated, too. We return the smaller number between l_1 and l_2, and answer the query in O(1) time.

Querying on keypoints

Let’s call the endpoints of additional edges "keypoint"s. Consider how to answer distance queries between keypoints. We construct a new graph C whose vertices are only the keypoints. For two keypoints:

if they are connected by an additional edge, we add this edge to C;
if they are in the same cycle, we query that cycle and get their distance d in the cycle, then connect them with an edge of weight d.

Cycle graph

The resulting graph C is a cycle: every vertex has degree 2 and C is connected. Thus we can easily handle distance queries on C. Also, C preserves distances on the original graph. So we can answer distance queries about endpoints in O(1) time.

The final solution

First, using the above algorithms we can support distance queries on one cycle and on keypoints.

Suppose there is a query (V_1,C_1,V_2,C_2). Since C_1\ne C_2, their shortest path must pass through some keypoint in cycle C_1, suppose it’s k_1; it also passes through some keypoint in cycle C_2, say k_2. Then the shortest path has length dis(V_1,k_1)+dis(k_1,k_2)+dis(k_2,V_2), and the smallest this value among all (k_1,k_2)'s is the answer. The three dis()'s can be obtained in O(1) time. Each cycle has at most 2 keypoints, so there are at most 4 pairs of (k_1,k_2) that we need to enumerate.

The time complexity is O(Q+M), where M=A_1+A_2+\dots+A_N.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found [here][333].
Tester’s solution can be found [here][444].