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://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.
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)
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.
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.
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.
Find the sum for each point, and sort.
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.
Well, I got the intuition from experience.
https://atcoder.jp/contests/abc178/tasks/abc178_e
I had solved this before, and I realised that distance is the max of difference between x+y or x-y. I simple extended it to multiple dimensions, and I could show that it is still correct.
It is also mentioned in page 272 of https://cses.fi/book/book.pdf.
I have solved this task too
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e
Which requires you to eliminate redundant edges in finding MST
Thanks a lot.
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 ??
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($$$nlogn.2^d$$$)
My submission: Submission.
Hope it helps.
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 .
Exactly!
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?
Notice I sorted the out masks before I started building the spanning tree cos I need just the max for each of the masks.
Sir, I really wonder how were u able to do it? The idea needed was completely out of the box
After thinking about how to expand the expression the remaining part wasn't that difficult
You can try similar problems here
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?
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.
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 !!
I started the spanning tree with node 0 and I start adding the edges from that.
Okay, Got it!
Thanks for the help man, really appreciate that.
Could you please explain what is pos[mask] in this loop and what is its significance?
It's a pointer to the largest mask value that isn't in the MST yet.
Auto comment: topic has been updated by sid9406 (previous revision, new revision, compare).
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.
You said we make 2^d such edges for every point . What is the other end point of these edges ? corners of hyper rectangle ??
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.
Makes sense .Thanks.
You know, many people that this "October Long Challenge D-Dimensional MST" is too long, but I'm not in this list)
What difficulty this problem would have got, if it was on codeforces?
Probably, Div 2E with around 2400-2600
I don't think so. More than 700 (Div1+Div2 combined) solved this. 2400-2600 is very tough, it would at max be 1900
You should take into account the fact that you have 10 whole days to solve it instead of the 2-3 hours of a Codeforces round. I'd say about 2100.