CHEFCCYL - Editorial

PROBLEM LINK

Practice

Contest

Author: Dmytro Berezin

Tester: Alexey Zayakin

Editorialist: Jakub Safin

DIFFICULTY

MEDIUM

PREREQUISITIES

prefix sums

PROBLEM

You’re given a weighted graph formed by disjoint cycles connected cyclically by N edges. Answer Q queries; in each query, compute the length of the shortest path between two vertices.

QUICK EXPLANATION

Use prefix sums to compute min. distances in cycles. Precompute distances between vertices connected to neighboring cycles and their prefix sums. Compute the distances for each possible direction in the outer cycle using that.

EXPLANATION

Yo dawg, I heard you like cycles so I put cycles in a cycle…

Our graph is formed by taking the “outer” cycle and replacing each of its vertices by one of the “inner” cycles. Any path between two vertices in different inner cycles then corresponds to a path in the outer cycle.

If we forget about moving through edges of the inner cycles, then there are just 2 possible paths in the outer cycle. We can compute the minimum distance (including the inner cycles’ edges, of course) for both of them and take the minimum.

Computing distances in a cycle

Let’s take a cycle with N vertices and edges, where the edge between i and i\%N+1 has length w_i. The fastest way to compute the two distances between vertices v_1,v_2 (when moving clockwise and counter-clockwise) uses prefix sums. Let’s take v_1 \le v_2 and compute the prefix sums W_i=\sum_{j=1}^i w_i (with usual w_0=0); one distance between v_1 and v_2 is d_1=\sum_{j=v_1}^{v_2-1} w_j = W_{v_2-1}-W_{v_1-1} and the other must be d_2=W_N-d_1, since the two paths between v_1 and v_2 together cover all N edges.

The prefix sums can be precomputed in O(N) and then we can compute the distances for any pair of vertices in O(1).

Distances in inner cycles

When we compute the prefix sums of the outer cycle, it’s easy to find the distances between vertices in cycles c_1 and c_2 (since distances don’t depend on vertices’ order, c_1 < c_2) that comes from the outer edges. For the path from (c_1,u_1) to (c_2,u_2) with distance denoted above as d_1, we need to cross inner cycles numbered c_1..c_2, so the path will move from u_1 to vertex v_1 (in the notation used for the outer edges in the input) of cycle c_1, then to vertex v_2 of cycle c_1+1, then to vertex v_1 of c_1+1, etc., until vertex v_2 of c_2 and from there to u_2.

That means we need to add to the distance d_1 from the outer cycle the minimum distances between u_1 and v_1(c_1), between v_2(j) and v_1(j) for every cycle c_1 < j < c_2, and between v_2(c_2) and u_2.

If we do the same thing with prefix sums for each inner cycle, we can compute first and last of these min. distances easily. The other min. distances are a problem, since there’s a lot of them. However, they don’t depend on u_1 or u_2, just c_1 and c_2, so we can use some more precomputation.

Let’s denote by X_i the minimum distance between v_1(i) and v_2(i) in the i-th inner cycle; we can compute these N numbers easily either by brute force or using the same prefix sums we’ve built for inner cycles. Now we need to compute \sum_{i=c_1+1}^{c_2-1} X_i - but that can be done exactly the same way as the distances in cycles! We just need to build the array of prefix sums of X_{1..N}; if the i-th prefix sum is S_i (with S_0=0 again), then our sum is S_{c_2-1}-S_{c_1}.

The other path in the outer cycle (denoted above as d_2) can be computed in a similar way. We’re moving from u_1 through v_2(c_1), v_1(c_1-1), v_2(c_1-1)v_2(1), v_1(N)v_1(c_2) to u_2. Again, the paths u_1 to v_2(c_1) and v_1(c_2) to u_2 can be found easily; the rest corresponds to \sum_{i=1}^{c_1-1} X_i + \sum_{i=c_2+1}^N X_i, which can be rewritten using prefix sums as S_N-S_{c_2}+S_{c_1-1}.

The time and memory complexity of this algorithm is linear in input size, since precomputing prefix sums is linear and each query can be processed in O(1).

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution

Tester’s solution

Editorialist’s solution

3 Likes

can anyone please tell me whats missing in my code…
doesn’t pass the first test case of all sections and passes rest of every section. Have tried everything from my side.
link text

Could be anything, I forgot to write a large part of my code at first and still passed everything except the first tests.

Same happens with me too … Doesn’t pass the first test case in all sections ans passes rest of every section .

@manii_bi you can try to delete[] the dynamically allocated vector or array which made passed all three test cases of third section but gave same WA in remaining sections . You can check here link text

But when I don’t use it is same condition as your’s but with an error SIGABRT for that check here link text

– Still can’t figure out why this is happening –

You are right i guess.I tried around 15 submissions but the problem persisted. Wish we could see the some test cases.

I have the same issue. First task of each subtask failed.


[1]


  [1]: https://www.codechef.com/viewsolution/15871097

I used Sparse Table, is it an Overkill? link

Yes, defintely XD.

Here what does this mean “inner cycle” and “outer cycle” ? @admin @berezin

There are N cycles(inner cycles) in the graph. Let us enumerate them cycle number 1 to N. If you look at these N cycles as N nodes…you will get another cycle(outer cycle) formed.

ohh…Thanks!

Here is a video editorial for the problem.

Cheers!

1 Like

Can anyone give hard and tricky test case?

Acc to constraints given in the question N can be equal to 1. Can anyone please give an example test case where N=1 and what should be the output for such a case.