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 
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/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.
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.
- We can move from one node to the other freely within connected component without any cost.
- 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.