TRAVELLING - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Vishesh Saraswat
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

You should be familiar with the concept of shortest paths in a weighted graph. Specifically, this problem requires Dijkstra’s Algorithm

PROBLEM:

You are given a graph with N vertices (numbered 1 to N) and M bidirectional edges, which doesn’t contain multiple edges or self-loops — that is, the given graph is a simple undirected graph.

For each pair of vertices a, b such that 1 \leq a, b \leq N, it is possible to add a new edge between vertices a and b to the graph, with a cost of (a - b)^2.

Find the minimum cost of adding edges so that vertex N is reachable from vertex 1.

QUICK EXPLANATION:

  • Let us assume that in the optimal solution, we have added an edge (u, v). Let u < v and v - u \geq 2. We can show that instead of adding this edge, we could have added (u , u+1), (u+1, u+2) \ldots (v-1, v). This would have costed v - u.

  • Consider the edge (i, i+1). If it is already present in the graph, then it’s cost is 0, otherwise it’s cost is 1. Cost of all other edges which are already present in the graph is 0.

  • In the above graph, we want to find out the length of shortest path from 1 to N.

EXPLANATION:

First of all, let us analyze our cost function. One of the most important observation to solve this problem is to observe that if we want to add an edge (u, v), such that u < v and v - u \geq 2. We can instead add the edges (u , u+1), (u+1, u+2) \ldots (v-1, v). This would result in a lower cost. Also, the cost of adding any one of this edge would be 1.

Now, our problem reduces to finding out the minimum number of edges of the form (i, i+1), that we need to add in our graph, so that we can reach from 1 to N.

Let us add the edges (i, i+1) in the above graph if they were not already present. Also, let us assign the weight 0 to all the edges that were already present in the graph, and 1 to the edges that we have just added. We can see that our problem is exactly same as finding the length of shortest path in the newly formed graph.

To find the shortest path, we can use Dijkstra’s Algorithm or 0-1 BFS.

TIME COMPLEXITY:

O(M \cdot \log{N}) or O(N+M), depending on the implementation.

SOLUTION:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
const int mod = 1e9+7;
const int inf = (1<<30);

void solve(int tc) {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n);
    vector<bool> hasedge(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        if (u > v)
            swap(u, v);
        adj[u].push_back({v, 0});
        adj[v].push_back({u, 0});
        if (u + 1 == v)
            hasedge[u] = true;
    }
    for (int i = 0; i < n-1; ++i) {
        if (!hasedge[i]) {
            adj[i].push_back({i+1, 1});
            adj[i+1].push_back({i, 1});
        }
    }
    vector<int> dist(n, inf);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (dist[u] < d)
            continue;
        for (auto [v, w]: adj[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    cout << dist[n-1] << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}


Tester-1's solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
 
string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
        char g = getchar();
        assert(g != -1);
        if (g == endd) {
            break;
        }
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t=readInt(1,1000,'\n');
  int ns=0;
  while(t--){
    int n, m;
    n=readInt(2,200000,' ');
    m=readInt(0,200000,'\n');
    ns+=n;
    assert(ns<=200000);
    int a[n] = {};
    set<pair<int,int>> st;
    vector<pair<int, int>> gr[n + 1];
    for(int i = 0; i < m; i++){
      int u, v;
      u=readInt(1,n,' ');
      v=readInt(1,n,'\n');
      assert(u!=v);
      st.insert({min(u,v),max(u,v)});
      if(abs(u - v) == 1){
        a[min(u, v)] = 1;
      }
      gr[u].push_back({v, 0});
      gr[v].push_back({u, 0});
    }
    assert(st.size()==m);
    for(int i = 1; i < n; i++){
      if(a[i] == 0){
        gr[i].push_back({i + 1, 1});
        gr[i + 1].push_back({i, 1});
      }
    }
    set<pair<int, int>> s;
    int vis[n + 1] = {};
    int ans;
    s.insert({0, 1});
    while(s.size()){
      auto it = s.begin();
      int y = (*it).first;
      int x = (*it).second;
      if(x == n){
        ans = y;
        break;
      }
      s.erase(it);
      if(vis[x] == 0){
        vis[x] = 1;
        for(int i = 0; i < gr[x].size(); i++){
          s.insert({y + gr[x][i].second, gr[x][i].first});
        }
      }
    }
    cout<<ans<<"\n";
  }
  return 0;
}
Tester-2's solution
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;


vector<vector<pair<int,int> > > adj;
vector<int> vis;

void solve()
{   
    int n = readIntSp(2,2e5);
    int m = readIntLn(0,2e5);

    sum_n+=n, sum_m+=m;
    max_n = max(max_n, n);
    max_m = max(max_m, m);

    adj.assign(n, vector<pair<int,int> >());
    vis.assign(n, -1);

    int x,y;

    rep(i,m){
        x = readIntSp(1,n);
        y = readIntLn(1,n);

        --x, --y;

        adj[x].push_back(mp(y,0));
        adj[y].push_back(mp(x,0));
    }

    rep(i,n-1){
        adj[i].push_back(mp(i+1,1));
        adj[i+1].push_back(mp(i,1));
    }

    vector<int> dis(n,n);
    dis[0]=0;

    set<pair<int,int> > pq;
    pq.insert({0,0});

    while(!pq.empty()){
        auto z = *(pq.begin());

        for(auto h:adj[z.ss]){
            if(dis[h.ff]>z.ff+h.ss){
                dis[h.ff] = z.ff+h.ss;
                pq.insert(mp(dis[h.ff], h.ff));
            }
        }

        pq.erase(z);
    }

    cout<<dis[n-1]<<'\n';
    
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,1000);
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_n<=2e5 && sum_m<=2e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
    cerr<<"Maximum length : " << max_n <<" "<<max_m<<'\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}

Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll ,ll>
using namespace std ;
const ll z = 998244353 ;

void shortest_path(vector<pll> adj[] , int n , vector<ll> &vis , vector<ll> &dist)
{
    set<pll> s ;
    s.insert({0 , 0}) ;

    while(!s.empty())
    {
        pll g = (*s.begin()) ;
        s.erase(s.begin()) ;

        ll u = g.second , curr_dist = g.first ;
        //cout << "u = " << u << " curr_dist = " << curr_dist << endl ;
        if(vis[u] == 1)
        {
            continue ;
        }

        vis[u] = 1 ;
        dist[u] = curr_dist ;

        for(int i = 0 ; i < adj[u].size() ; i++)
        {
            ll v = adj[u][i].first ;
            ll w = adj[u][i].second ;
            //cout << "v = " << v << " w = " << w << endl ;

            if(vis[v] == 0)
                s.insert({curr_dist + w , v}) ;
        }
    }

    return ;
}
 
void solve()
{
    int n , m ;
    cin >> n >> m ;
    vector<pll> adj[n] ;
    for(int i = 0 ; i < m ; i++)
    {
        int u , v ;
        cin >> u >> v ;
        u-- ; v-- ;
        adj[u].push_back({v , 0}) ;
        adj[v].push_back({u , 0}) ;
    }

    for(int i = 0 ; i < n-1 ; i++)
    {
        adj[i].push_back({i+1, 1}) ;
        adj[i+1].push_back({i , 1}) ;
    }

    vector<ll> vis(n) , dist(n) ;
    shortest_path(adj , n , vis , dist) ;
    cout << dist[n-1] << endl ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    ll t;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }

    return 0;
}
5 Likes

My approach is to take maximum node value(say m) that is reachable from vertex 1
and add edges from that vertex to its next vertex(m+1) and from m+1 to m+2 … so on n-1 to n

So the cost of edges is n-maximum_value_node_reached_by_1

What is wrong in this approach?

5 Likes

1
100 2
1 50
2 100

Correct output: 1

4 Likes

I tried to calculate the minimum cost to reach the ith vertex which was min of all its connected vertices and (i-1)th vertex cost.
Here is the code: CodeChef: Practical coding for everyone

Can anyone please tell why is it failing?

2 Likes

i used another approach, I condensed the graph based on the components , and formed the new graph based on components , since the max answer can be n -1 in worst case, so if node i and i+1 aren’t in same component I added a edge between their component with cost 1 [(i+1) - i]^2, since every edge has cost 1 , so I did simple bfs from component[1] to reach component[n] .

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

1 Like

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

Can anybody please tell that in which testcase is this solution failing ?

1
100 2
100 50
1 99

by directly connecting 100 and 99 correct output: 1

While going thorough the AC submitted solutions, i can see many users code is similar line by line,
has anyone else observed it?

7 Likes

Yes, my logic is giving the same output.

There was a sudden surge of submissions for this problem … atleast in Div 3…i request admins to look into this matter

6 Likes

nodes = 7
edges: 1->3, 2->7
expected answer: 1
your answer: 4

Here is my solution using Union Find and BFS.
https://www.codechef.com/viewsolution/59524676

Time Complexity: O(N*log N + M)
Space Complexity: O(N)

There are simply two observations in the problem, which are as follows:

  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.

For obtaining the connected components, we can use Union Find.

Once we have connected components, we can use above two observations and can find the minimum cost using BFS.

Note: For simplicity, I have defined arrays globally. so, space complexity would be O(2*10^5), but it can be improved to O(N) by defining them locally and pass them to the function as a input !!

3 Likes

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

i cant figure out whats wrong with this logic… i computed an array of length n where each index lets us know which one of connected graph it is node of …
then we calculate the shortest path from each connected component to the Nth node’s component. using Dynamic programming

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

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.

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;

}

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

1
8 3
1 4
1 5
3 8

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

5 Likes

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

3 Likes

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