TRAVELLING - Editorial

editorial
, , , ,
19

people upload code on youtube during contest and as soon as the code is uploaded, u can see a sudden surge in successful submissions.

8 Likes
20

https://www.codechef.com/viewsolution/59525255

My approach to the problem is that first we will find the vertices connected to 1, and mark all their distances as 0, and push these vertices into a queue, and mark them visited, next we will pop the vertices one by one into the queue and mark distance of previous index or next index as 1 if they are not visited, and push them into the queue. This will give the minimum steps required to reach vertex N.

21

what is wrong ??

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)

void dfs(int node,vector&vis,vectoradj[]){
vis[node]=1;
for(auto it:adj[node]){
if(!vis[it]){
dfs(it,vis,adj);
}
}
}

signed main() {
int t;
cin>>t;
while(t–){
int n,m;cin>>n>>m;
vectoradj[n+1];
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}

    vector<int>vis(n+1,0);
    dfs(1,vis,adj);
    if(vis[n]==1){
        cout<<0<<endl;
    }else{
        int dp[n+1];
        for(int i=0;i<=n;i++)dp[i]=INT_MAX;
        dp[0]=dp[1]=0;
        for(int i=1;i<=n;i++){
            dp[i]=min(dp[i],1+dp[i-1]);
            for(auto it:adj[i])dp[it]=min(dp[it],dp[i]);                                                                                                                                                                                                                                                                                                                                    
        }
        //for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
       //cout<<endl;
       cout<<dp[n]<<endl;
    }
   
}
return 0;

}

22

My solution is also similar to yours, I can’t figure out any edge case where it could fail. My submission

23

1
8 3
1 4
1 5
3 8

Try this testcase, correct answer is 1 whereas your code is giving 2

5 Likes
24

It was a beautiful problem, Kudos to the setter!
So much to learn from this problem!

3 Likes
25

https://www.codechef.com/viewsolution/59514198
This is my submission can anyone tell where it is failing.

26

Yeah, there were single-digit submissions in the 2nd hour. But it became 100+ within the end of 3rd hour

1 Like
27

my approach is kind of similar in thought processs but my implementation is bit different can you please check my submission. I am getting wa
https://www.codechef.com/viewsolution/59526173

28

can you please help me out in edge cases.I have a over complicated implementation but idea is kind of similar instead of doing multsource bfs from components containing first node i had done with component containing last node . This is my submission can you point out what i have done wrong
https://www.codechef.com/viewsolution/59526173

1 Like
29

I did exact same thing with dsu. Could you please tell where I am i wrong?
https://www.codechef.com/viewsolution/59509466

edit: It is just the implementation of bfs CodeChef: Practical coding for everyone. But i am still confused where could my implementation fail.

30

This question made my day.
Too interesting

5 Likes
31

if input graph contain more than one connected component then this approach fails

32

I am trying to solve this problem using union find
https://www.codechef.com/viewsolution/59549189
This is my solution
In this i am trying to find and two elements closest to each other but in different component one in 1’s and other in n’s component

33

Thank You for this test case,
I was trying to figure out where i went wrong in my approach and this test case enlightened me!

My approach : Wrong Answer for this test Case

Corrected Approach : https://www.codechef.com/viewsolution/59548208

2 Likes
34

This was exactly what I was thinking , awesome man :pinched_fingers:

35

my rank was 250 in div2 in the last half hour and when I checked it after the contest it was around 1000. Just because answer was leaked on youtube. And this is not the first time this happened. codechef admin should have to take measures to ban such channels on youTube as well as have a plagiarism checker just like codeforces. At this point of time we think that codechef would no longer be fair enough to look for competitive programming. Codechef adimins please look into it otherwise we have to shift to other platforms

2 Likes
36

Yes , I refreshed the page and the numbers were pretty big

37

Why not the answer would be the (number of connected components -1) ? Which test case would be failing ?

38

Some components may not be involved in the shortest path. So

1
9 4
1 4
5 9
2 8
3 6

has 5 connected components (including isolated node 7) but the correct answer is 1