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

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (33)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Find the sum for each point, and sort.

          Some code might help here
          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Okay, Got it!

        Thanks for the help man, really appreciate that.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You know, many people that this "October Long Challenge D-Dimensional MST" is too long, but I'm not in this list)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What difficulty this problem would have got, if it was on codeforces?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably, Div 2E with around 2400-2600

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think so. More than 700 (Div1+Div2 combined) solved this. 2400-2600 is very tough, it would at max be 1900

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply