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 
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.