I understand and can implement Prim’s algorithm and Kruskal’s algorithm, but can’t follow the editorial concerning how to minimize the number of edges that must be considered in applying these algorithms. The part of the editorial describing the masks is especially difficult for me to follow. Could you provide one or two numerical examples of the steps involved in generating the masks and showing how this minimizes the number of edges that need to be considered in the solution?
3 Likes
can you tell us in easy language what exactly has happened in this editorial pls
1 Like
why do you waste time writing editorial when you have a firm determination of not letting new comers understand.
15 Likes
New comers must learn how to read.
1 Like
Can someone provide some test cases other than the given ones?
So what should I do so I understand this editorial.
1 Like
Read it multiple times, try to make sure you understand every line of the editorial, use pen and paper to analyse, even then if you can’t, wait for some video editorial, once you understand the solution (if from some other source) then come to this editorial again and try to understand.
bro i also find mst for 2D manhattan distance algo in these links, but i was unable to implement that algo for 5D coordinates.
https://programmersought.com/article/47251928114/
https://www.programmersought.com/article/6396113136/
this one is for maximum spanning tree
this one is chinese link, but i found its explanation better after changing it into english and after understanding the algo from here I implemented mst for 2D manhattan distance , but can’t do same for this question 
Can you help me please
Thanks in advance
Can someone help me understand why this exceeds time limit for the first subtask?
#include "bits/stdc++.h"
#define ll long long int
using namespace std;
const int mod = 1e9+7, mxN = 2e5+10;
ll a[mxN];
ll parent(ll x)
{
ll i = x;
while(a[i] != -1)
{
i = a[i];
}
return i;
}
void un(ll x, ll y)
{
ll px = parent(x), py = parent(y);
a[py] = px;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
int tt;
// cin >> tt;
tt = 1;
for(int pp = 0 ; pp < tt ; pp++)
{
ll n,d;
cin >> n >> d;
ll x[n][d];
priority_queue <pair<ll,pair<ll,ll>>> elist;
for(int i = 0 ; i < n ; i++)
{
for (int j = 0; j < d; j++)
{
cin >> x[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
ll wt = 0;
for (int k = 0; k < d; k++)
{
wt += abs(x[i][k]-x[j][k]);
}
elist.push(make_pair(wt,make_pair(i,j)));
}
}
ll cnt = 0, ans = 0;
for (ll i = 0; i < n; i++)
{
a[i] = -1;
}
while(cnt != n-1)
{
auto edge = elist.top();
elist.pop();
ll u,v;
u = edge.second.first;
v = edge.second.second;
ll pu = parent(u), pv = parent(v);
if(pu != pv)
{
un(u,v);
cnt++;
ans += edge.first;
}
}
cout << ans << '\n';
}
return 0;
}
1 Like
Sure man, These are the links I came across too. As they have told for 2 Dimensions, so how i approached this question is I looked at all possible cases.
Let us check for d = 2, We take two points distance between them is
|x1 - x2| + |y1 - y2|
So what can be the possibilities, let us look into them.
1. x1 > x2 and y1 > y2 so we will get after removing | | --> x1 - x2 + y1 - y2
Which we can write as ( x1 + y1 ) - ( y1 + y2 )
Do this for every point remove MOD with a possibility and check:
Now for 2D there will be 4 possibilities ++ – ± -+ you have to find them and store all the ++ values in one array and sort it subtract highest - lowest and this way you will get max edge from that point, move to next point and so on. Then once all points are used move to next possibility store the sums in an array and do the same. This way you will end with 2^D.N edges.
Like for 4D we will have like a possibility where:
x1 > x2 and y1 < y2 and z1 < z2 and r1 > r2 for a points (x,y,z,r)
So like we did in 2 dimensions we will have to check all possible possibilities in any D.
So basically you have to check 2^D possible configurations of a point in terms of ±, D being the Dimension. I suggest you look at my code because I have commented a lot and also it’s very brute lol, Also keeping track of weights and indexes were kind of tricky so i used a custom struct for that and in the end Kruskal.
3 Likes
8 Likes
I was facing the same issue due to the tight TL for subtask 1 with Kruskal.
You’ve to make your find parent function a little faster.
Partial AC
1 Like
I’ll tell you what, Kruskal’s algorithm with a complete graph, for sorting it out was enough for 10 pts, for the rest you needed Delaunay Triangulation, and my lazy bum was not able to do a D-dimensional Delaunay Triangulation for this:joy:
I used the similar approach in combination with 2^d possibilities and it passed all the cases , If you want I can share my approach with you .
2 Likes
yeah please i will be thankfull to you,
coz i spend much time in this but getting 4WA
Can anyone tell me how does it take O(n square) time when we don’t reduce the edges. Shouldn’t it be O(nlog(n)) as this: ( as it is undirected graph i.e. edge(a,b)==edge(b,a)
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
sum=0;
for(int k=0;k<d;k++) sum+=abs(a[i][k]-a[j][k];
// add the edge in the vector
}
}
1 Like
Man thats insane and inspiring
1 Like
It would still be an ((n-1)*(n-2))/2 task, resulting in O(n^2) time complexity.
1 Like
Why would someone write editorials like these . Editorials are meant for the help of people who couldn’t solve it during the contest and want to upsolve them . No offence, but this editorial is shit, couldn’t understand a thing . Can someone pls explain the idea behind the solution in simpler terms.
4 Likes