TRAVELLING - Editorial

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

1 Like

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

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

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.

This question made my day.
Too interesting

5 Likes

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

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

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

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

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

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

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

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

For some reason I couldnt find error in your code, but this testcase is failing in your code, hope it helps.
1
26 3
6 25
1 5
5 20

Correct answer is 2, whereas your code gives 6.

Can anyone tell what is wrong with my apporoch. I have use dsu and check maximum node in 1 components and adding necessary nodes.similary from last node .it is not passing some testcase.can some one help?

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

#define int     long long
#define all(xs)   xs.begin(), xs.end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
map<int, int> mp;
map<int, int> mp2;
struct D {

    vector<int> par;
    vector<int> sz;

    D(int n) {
        par.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 0; i <= n; i++)
        {
            par[i] = i;
            sz[i] = 1;
            mp[i] = i;
            mp2[i] = i;
        }
        // mp.clear();
        // mp2.clear();
    }

    int find(int a) {
        if (a == par[a]) {
            return a;
        }
        return par[a] = find(par[a]);
    }
    void merge(int x, int y) {
        int p1 = find(x), p2 = find(y);
        if (sz[p1] > sz[p2]) {
            par[p2] = p1;
            sz[p1] = sz[p2] + 1;
            mp[p1] = max(mp[p1] , mp[p2]);
            // mp.erase(p2);
            mp2[p1] = min(mp2[p1] , mp2[p2]);

        }
        else {
            par[p1] = p2;
            sz[p2] = max(sz[p2], sz[p1] + 1);
            mp[p2] = max(mp[p1] , mp[p2]);
            // mp.erase(p1);
            mp2[p2] = min(mp2[p1] , mp2[p2]);


        }
    }

    int getmax(int i) {
        return mp[par[i]];
    }
    int getmin(int i) {
        return mp2[par[i]];
    }

};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        mp.clear();
        mp2.clear();
        int n;
        cin >> n;
        D obj(n);
        int m;
        cin >> m;
        vector<pair<int, int>> tt;
        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            tt.emplace_back(u , v);
            obj.merge(u , v);
        }
        if (obj.find(1) == obj.find(n)) {
            cout << 0 << "\n";
            continue ;
        }


        int ans = (n - 1) * (n - 1) , c  = 0;
        int mn = obj.getmin(1);
        int mx = obj.getmax(1);
        int mn1 = obj.getmin(n);
        int mx2 = n;
        int d1 = abs(mn - mn1);
        ans = min(ans , d1 * d1);
        d1 = abs(mn - mx2);
        ans = min(ans , d1 * d1);
        d1 = abs(mx - mn1);
        ans = min(ans , d1 * d1);
        d1 = abs(mx - mx2);
        ans = min(ans , d1 * d1);


        // ans = min(ans , abs(n - mx));
        // ans = min(ans , abs(mn1 - mx));
        // ans = min(ans , abs(n - max(mx , mn1)));
// cout << mx

        for (int i = mx + 1; i <= n; i++) {
            if (obj.find(1) != obj.find(i)  ) {
                // cout << i << " ";
                c++;
                obj.merge(1, i);
            }

            if (obj.find(1) == obj.find(n)) {
                break;
            }
        }

        // cout << c << " ";
        ans  = min(ans , c);

        c = 0;


        // ans = min(ans , abs(mx - mn1));
        // for (int i = 2; i <= n; i++) {
        //     if (obj.find(1) != obj.find(i)) {
        //         // cout << i << " ";
        //         c += (i - maxi) * (i - maxi);
        //         obj.merge(1 , i);
        //         maxi = i;
        //     }
        //     else {
        //         maxi = i;
        //     }

        //     if (obj.find(1) == obj.find(n)) {
        //         break;
        //     }
        //     mx = i;
        //     d1 = abs(mx - mn1);
        //     ans = min(ans , d1 * d1 + c);


        //     // cout << ans << " ";
        // }
        // // cout << "\n";
        // ans = min(ans , c);
        // c = 0;
        // maxi = n ;
        // mx = old;
        D obj1(n);
        for (auto [x , y] : tt) {
            obj1.merge(x , y);
        }
        c = 0;
        for (int i = mn1 -  1 ; i >= 1; i--) {
            if (obj1.find(i) != obj1.find(n)) {
                c++;
                obj1.merge(i, n);
            }
            if (obj1.find(1) == obj1.find(n)) {
                break;
            }
        }
        ans = min(ans , c);
        cout << ans << "\n";
    }
}

Thanks for this TestCase.

1 Like

https://www.codechef.com/viewsolution/59576149
here is my solution using bfs and dfs.

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

Here is my solution. But it is getting wrong answer in test case 5 to 9. Can you please tell me why Iā€™m getting wrong answer or what have I missed ?

1
9 4
1 3
3 4
6 7
5 8
correct output 2
check forthis input

Yupp, getting 2 only.