TRAVELLING - Editorial

From the sample input

5 4
3 2
1 4
5 3
4 2

Can anyone help me understand how the output is 0 and not 1, there is no direct path and we’ll need to create a new edge either between 1-2 or 4-5

Note that edges are bidirectional. Path : 1 \to 4 \to 2 \to 3 \to 5

2 Likes

Hello, there is only two simple observations.

  1. We can move from one node to the other freely within connected component without any cost.
  2. Instead of directly going from a to b, we would like to go via a+1 or a-1.

I check out your solution and found that you are just using the second observation. E.g. if you reached to a then we can reach should approach a-1 or a+1.

Suppose, a+1 is the part of connected component is C. Once reached to a+1, can reach out to any node in C without any cost (considering the first observation). So, you should assign the same level as a+1 to all the node in connected component C.

Hope it helps.

Following is one test case

1
30
2
1 10 
7 30

Here your code outputs 6 which comes from 7 \to 1. Your code doesn’t consider 7 \to 10. Just adding this case to the code is not the way to solve.

We observe first that there is no reason to join some two nodes x, y with an edge such that |x - y| > 1. After that, possibilities have reduced significantly and we must stop and think if we can leverage that. Which is what editorial does.

In your attempt, you treated the mx and mn1 value nodes differently. Also, you chose to iterate towards 1 in case of mn1 and towards n in case of mx. These choices seemed very greedy. Aim for correctness first.