October Long Challenge D-Dimensional MST

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
36:18:50
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

sid9406's blog

October Long Challenge D-Dimensional MST

By sid9406, history, 4 years ago, In English

I couldn't solve this problem from Codechef Long Challenge https://www.codechef.com/OCT20A/problems/DDIMMST . Can someone help me in this problem. I tried reading the editorial https://discuss.codechef.com/t/ddimmst-editorial/79385 but no help . What i don't understand is how are we able to reduce the number of edges from n^2 to 2^d*n .

This seems to be general class of problems , there is another problem that uses the same idea https://mirror.codeforces.com/contest/1093/problem/G , awoo i know this contest was long back , can you pls explain the idea behind the solution to these kind of problems.

sid9406
4 years ago
37

Comments (33)

Show archived | Write comment?

oversolver

4 years ago, # |

← Rev. 3 →

Hard to explane, try to solve it when D=2

Ofc if you got how to solve D=1 in $$$O(NlogN)$$$

We have two types relativity of points in edges: when $$$a_x \leq b_x; a_y \leq b_y;$$$ and when $$$a_x \leq b_x; a_y \geq b_y;$$$

So, to maximize first case we need point with maximum sum $$$a_x+a_y$$$ and minumim. To maximize second — max and min of $$$a_x - a_y$$$. In both max-min is new edge, choose best and connect.

In general we need $$$2^{D-1}$$$ such relativities (signums in sum)

→ Reply

sid9406

4 years ago, # ^ |

I was following this editorial https://discuss.codechef.com/t/ddimmst-editorial/79385 and understood that the manhanttan distance between two points p1 and p2 is the max of (p1,mask + p2,~ mask) . Can you explain from the line that says :- Let’s consider each mask separately, let point Mmask be the point that has maximum sum for the combination mask.

→ Reply

Everule

4 years ago, # ^ |

← Rev. 2 →

What he means is, That when you consider some type of mask, Each point now has a sum. We can show, that it is optimal, to pair only with the elements with the smallest or largest sum.

This is because, the largest edge containing any vertex, must either be with the smallest sum, or the largest sum. We know that we must consider at least the largest edge from each vertex, and we know it is enough, to form a spanning tree just considering this mask. So therefore, the other edges are redundant. And therefore we get $$$O(n)$$$ edges for each mask.

The final spanning tree, is formed from the union of edges from each mask. It may be possible, that some edges, do not have the correct distance. But those edges will be ignored, as there will be a better edge too.

You can either think of it as, we only removed redundant edges, so we are still finding the MST of all edges.

We can also explicitly show, that is there is an edge u->v in a mask, such that it is smaller than the actual distance, u and v will be in the same component before you reach this edge.

If u or v, are the smallest sum or largest sum in the mask, then the edge u->v will already exist, with a larger and correct distance in our set.

If u and v aren't the largest sum. Then the sum sort will look like a,u,v,b without loss of generality. We ignore the elements in between. We know that the distance a->b, a->v, u->b are larger than u->v, and therefore u and v will already be in the same component.

→ Reply

sid9406

4 years ago, # ^ |

After we fix a mask, how do we identify the elements with smallest or largest sum . For a vertex this sum will only change if we vary the mask . I am confused now , how to construct n edges for every mask.

→ Reply

Everule

4 years ago, # ^ |

← Rev. 2 →

Find the sum for each point, and sort.

Some code might help here

void solve(){
    int n,d;
    cin>>n>>d;
    vector<vector<pair<int,int>>> points(1<<d, vector<pair<int,int>>(n));
    //points[j][i] = {sum of point index using mask j, index}
    for(int i=0;i<n;i++){
        vector<int> c(d);
        cin>>c;
        for(int j=0;j<(1<<d);j++){
            for(int k=0;k<d;k++){
                points[j][i].first += c[k]*((j&(1<<k)) ? -1 : 1);
            }
            points[j][i].second = i;
        }
    }
    for(int i=0;i<(1<<d);i++){
        sort(points[i].begin(), points[i].end());
        //sorting sums of each mask
    }
    DSU tree(n);
    vector<Edge> edges;
    for(const auto &p : points){
        //adding edges with min sum
        for(int i=1;i<n;i++){
            edges.emplace_back(p[0].second,p[i].second,p[i].first - p[0].first);
        }
        //adding edges with largest sum
        for(int i=n-2;i>=0;--i){
            edges.emplace_back(p[n-1].second,p[i].second,p[n-1].first - p[i].first);
        }
    }
   //basic MST algo
    ll ans = 0;
    sort(edges.begin(), edges.end());
    for(const auto &[u,v,w] : edges){
        if(tree.find_set(u)!=tree.find_set(v)){
            tree.join_sets(u,v);
            ans+=w;
        }
    }
    cout<<ans<<"\n";
}

→ Reply

sid9406

4 years ago, # ^ |

Thanks , finally understood the solution, just one thing how did you get the intuition to solve this problem ? Does this intuition came from the fact that MST will only contain the edges connecting vertex to one of 2^d corner points only.

→ Reply

Everule

4 years ago, # ^ |

← Rev. 2 →

Well, I got the intuition from experience.

Tasks

→ Reply

sid9406

4 years ago, # ^ |

Thanks a lot.

→ Reply

sid9406

4 years ago, # ^ |

So we need not consider the edge (p1, p2) if neither of them are one of the points that maximise mask or ~ mask.How to check if this point maximise mask or ~ mask ??

→ Reply

madlogic

4 years ago, # |

← Rev. 2 →

I'll try to explain my solution

The weight of an edge between two points $$$i$$$ and $$$j$$$ is $$$|$$$$$$x_{i,1}$$$$$$−$$$$$$x_{j,1}$$$$$$|+|$$$$$$x_{i,2}$$$$$$−$$$$$$x_{j,2}$$$$$$|+…+|$$$$$$x_{i,d}$$$$$$−$$$$$$x_{j,d}$$$$$$|$$$

To remove the absolute sign there are different ways the formula can turn out to be e.g.
$$$($$$$$$x_{i,1}$$$$$$−$$$$$$x_{j,1}$$$$$$)+($$$$$$x_{i,2}$$$$$$−$$$$$$x_{j,2}$$$$$$)+…+($$$$$$x_{i,d}$$$$$$−$$$$$$x_{j,d}$$$$$$)$$$
$$$($$$$$$x_{j,1}$$$$$$-$$$$$$x_{i,1}$$$$$$)+($$$$$$x_{i,2}$$$$$$−$$$$$$x_{j,2}$$$$$$)+…+($$$$$$x_{i,d}$$$$$$−$$$$$$x_{j,d}$$$$$$)$$$
$$$($$$$$$x_{j,1}$$$$$$-$$$$$$x_{i,1}$$$$$$)+($$$$$$x_{j,2}$$$$$$-$$$$$$x_{i,2}$$$$$$)+…+($$$$$$x_{i,d}$$$$$$−$$$$$$x_{j,d}$$$$$$)$$$ $$$.$$$ $$$.$$$
There are $$$2^d$$$ possible expansions

So for all the $$$2^d$$$ possible masks(the mask represents either a positive or negative sign attached to the value) for a point $$$i$$$ you can create an edge between $$$mask$$$ and ($$$2^d-1$$$) ^ $$$mask$$$ with another point $$$j$$$

I used Prim's Algorithm
So I'll have masks for values $$$in$$$ the MST and values not in the MST yet ($$$out$$$)
For each mask store the maximum value you can get for both $$$in$$$ and $$$out$$$ (NOTE: MAX not MIN problem asks for the maximum spanning tree)
To add an edge loop through all the masks and combine $$$in$$$ masks with their matching $$$out$$$ masks ($$$mask$$$ and ($$$2^d-1$$$) ^ $$$mask$$$) and pick the edge with the maximum value
After getting the edge add the $$$out$$$ vertex to the $$$in$$$ vertices and update the max values in $$$in$$$ and $$$out$$$
Continue the algorithm until you've formed the Spanning Tree($$$n - 1$$$ times)

Complexity: O(

Unable to parse markup [type=CF_MATHJAX]

)

My submission: Submission.

Hope it helps.

→ Reply

sid9406

4 years ago, # ^ |

← Rev. 2 →

Can you confirm if i got it right, let's say A is the set of vertices already included in MST and B is the vertices that are not in the MST yet . Then according to prim's algorithm we choose the max weight edge from the A-B cut and include it in the MST. To calculate this max weight edge, for each mask we calculate the max of all values in set A and minimum of all values in set B . Then the we will include the edge for which the difference max(A) — min(B) is maximum for all the masks .

→ Reply

madlogic

4 years ago, # ^ |

Exactly!

→ Reply

The_mysterio

4 years ago, # ^ |

where is your logn factor coming if you are directly building these n-1 maximum edges by iterating through the masks and selecting max of in and out?

→ Reply

madlogic

4 years ago, # ^ |

Notice I sorted the out masks before I started building the spanning tree cos I need just the max for each of the masks.

→ Reply

The_mysterio

4 years ago, # ^ |

Sir, I really wonder how were u able to do it? The idea needed was completely out of the box

→ Reply

madlogic

4 years ago, # ^ |

After thinking about how to expand the expression the remaining part wasn't that difficult
You can try similar problems here

→ Reply

The_mysterio

4 years ago, # ^ |

Sorry sir, the link that you have given is returning to this page only. Ok, I just want to know, are you applying prim's algo and simultaneously filtering out n-1 edges from n^2 edges?

→ Reply

madlogic

4 years ago, # ^ |

The link links to a comment above and I'm using Prim's to choose the maximum edge each time but I'm not looping through the edges instead I loop through the bitmasks.

→ Reply

tushaar789

4 years ago, # ^ |

← Rev. 4 →

Hi, Great explanation, I was looking at the code but couldn't understand why you just took the first element to build initial "in" array?

for (int mask = 0; mask < (1 << d); mask++) {

int cur = 0;
for (int j = 0; j < d; j++) 
  if (mask & (1 << j)) 
    cur -= a[0][j];
  else
    cur += a[0][j];
in[mask] = cur;

}

Please help me with this !!

→ Reply

madlogic

4 years ago, # ^ |

I started the spanning tree with node 0 and I start adding the edges from that.

→ Reply

tushaar789

4 years ago, # ^ |

Okay, Got it!

Thanks for the help man, really appreciate that.

→ Reply

break2000

4 years ago, # ^ |

for (int mask = 0; mask < (1 << d); mask++) {
      int m = out[mask].size();
      while (pos[mask] < m && vis[out[mask][pos[mask]].second]) 
        ++pos[mask];
      if (pos[mask] < m) {
        int k = (1 << d) - 1;
        int to = mask ^ k;
        int cur = out[mask][pos[mask]].first + in[to];
        if (cur > mx) {
          mx = cur;
          node = out[mask][pos[mask]].second;
        }
      }
    }

Could you please explain what is pos[mask] in this loop and what is its significance?

→ Reply

madlogic

4 years ago, # ^ |

It's a pointer to the largest mask value that isn't in the MST yet.

→ Reply

sid9406

4 years ago, # |

Auto comment: topic has been updated by sid9406 (previous revision, new revision, compare).

→ Reply

rath772k

4 years ago, # |

← Rev. 2 →

Imagine a hyper-rectangle that encloses all the given points. We can easily find the corners of smallest such hyper-rectangles. Now for every point, the farthest point will be the one closest to one of the corners. Just make $$$2^d$$$ such edges for every point. Now the number of edges reduces to $$$O(N*2^d)$$$ from the trivial $$$O(N^2)$$$. After this you can just apply one of the standard MST algorithms.My submission.

→ Reply

sid9406

4 years ago, # ^ |

You said we make 2^d such edges for every point . What is the other end point of these edges ? corners of hyper rectangle ??

→ Reply

rath772k

4 years ago, # ^ |

← Rev. 3 →

The other end is that point that is closest to a given corner. The index of those points are stored in the array $$$closest$$$ in my submission. $$$closest[i]$$$ stores index of the point closest to this particular corner.

→ Reply