DDIMMST - Editorial

PROBLEM LINK:

Division 1
Division 2

Author: Ildar Gainullin
Tester: Radoslav Dimitrov
Editorialist: Srikkanth

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Minimum Spanning Tree algorithms

PROBLEM:

Given a n points in D dimensional space, find the maximum spanning tree of the complete graph with edge weights as manhattan distance between points.

QUICK EXPLANATION:

In the complete graph there are a lot of edges that will never be a part of any spanning tree.

We can identify 2^d points such that every edge that there will definitely exist a maximum spanning tree such that every edge of the spanning tree contains one of these 2^d points as an end point.

So we need not consider all n^2 graphs, rather only those edges that have atleast one end point in one of the 2^d points. We can then apply any maximum spanning tree algorithm on the smaller graph to obtain the result.

EXPLANATION:

First observation is we can apply any minimum spanning tree algorithm and change min to max and solve this problem.
We can construct the complete graph and easily solve the first subtask.

Recap of Prim’s algorithm

Suppose we have obtained some set of connected edges that we are sure lies in some minimum spanning tree.

Consider the points that belong to end points of edges visited so far, (say A)
Let the other points be B.

Consider all edges from some point in A and some point at B. Among these edges, atleast one edge must belong to the spanning tree so we can greedily choose the minimum (or maximum) to get the minimum (or maximum) spanning tree.

Initially A is any point we want, and we keep repeating the above until B is empty.

Let’s see if we can use any properties of the manhattan distance to speed up the algorithm

We cannot afford to construct all edges (since it’s already \mathcal{O}(n^2)).
However we can remove some redundant edges and still obtain the required Maximum Spanning Tree.

Suppose we are at some stage of Prim’s algorithm, we have the set A of visited nodes and complimentary set B of unvisited nodes.

Let’s look at the edge weight between a pair of points p_1 \in A and p_2 \in B.

d(p_1, p_2) = \sum_{i=1}^{d} |p_{1i} - p_{2i}|

Let’s consider the value |a - b|, we can rewrite it as a - b or b - a according to whether a \geq b or a \leq b

If we didn’t have the absolute value, we can combine the p_1 terms and the p_2 and split them.

Since we only have to find the maximum value of the sum of absolute values, let’s consider all 2^d combinations of each expression and take maximum of all of them. The maximum would definitely contain all d terms to be positive, and would be our actual edge weight.

Consider the 2^d possible expansions of d(p1, p2), i.e. with each summand as p_{1i} - p_{2i} or p_{2i} - p_{1i}.
The removes the absolute values and we can group all p_{1i} terms together and p_{2i} terms together.

We’ll obtain 2^d possible values for every point (according to whether each coordinate is positive or negative), let’s denote that by p_{i, mask}

The maximum among these 2^d terms p_{i, mask} - p_{j,mask} will be equal to d(p_1, p_2).

Let’s rewrite the formula for d(p_1, p_2),

d(p_1, p_2) = \max_{mask=0}^{2^d-1} p_{1, mask} - p_{2, mask}, and equivalently

d(p_1, p_2) = \max_{mask=0}^{2^d-1} p_{1, mask} + p_{2, \overline{mask}} where \overline{mask} is 1’s complement of mask.

We will always want to choose the point p_i that maximises p_{i, mask} and similarly p_{j, \overline{mask}}.

Let the point M_{mask} be the point that has maximum sum for the combination mask.

Consider the points M_{mask} and M_{\overline{mask}}.

  • If both lie on the set A, then d(M_{mask}, p_2) \geq d(p_1, p_2)
  • If both lie on the set B, then d(p_1, M_{\overline{mask}})\geq d(p_1, p_2)
  • If one lies in A and other in B, then d(M_{mask}, M_{\overline{mask}}) \geq d(p_1, p_2)

So we need not consider the edge p_1, p_2 if neither of them are one of the points that maximise mask or \overline{mask}.

There are only 2^d maximum points (one for each point) and we need to consider only those edges that have atleast one end point among these 2^d points, because others will not be candidates for the maximum as per the argument shown above.

We have reduced the number of edges from n^2 to n 2^d, which is enough to solve the problem.

TIME COMPLEXITY:

TIME: \mathcal{O}(n 2^d (d + \log n))
SPACE: \mathcal{O}(n 2^d)

SOLUTIONS:

Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 2e5 + 7;

int dsu[N];

int get(int v) {
  if (v == dsu[v]) return v;
  else return dsu[v] = get(dsu[v]);
}

void uni(int u, int v) {
  dsu[get(u)] = get(v);
}

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, d;
  cin >> n >> d;
  vector <vector <int> > x(n, vector <int> (d));
  for (int i = 0; i < n; i++) for (int j = 0; j < d; j++) cin >> x[i][j];
  vector <pair <int, pair <int, int> > > e;
  auto add_edge = [&] (int u, int v) {
    int sum = 0;
    for (int i = 0; i < d; i++)
      sum += abs(x[u][i] - x[v][i]);
    e.push_back({sum, {u, v}});
  };
  for (int mask = 0; mask < (1 << d); mask++) {
    vector <pair <int, int> > e;
    for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = 0; j < d; j++) {
        if ((mask >> j) & 1) {
          sum += x[i][j];
        } else {
          sum -= x[i][j];
        }
      }
      e.push_back({sum, i});
    }
    int s = min_element(e.begin(), e.end())->second;
    int t = max_element(e.begin(), e.end())->second;
    for (int x = 0; x < n; x++) {
      add_edge(s, x);
      add_edge(t, x);
    }
  }
  sort(e.rbegin(), e.rend());
  for (int i = 0; i < n; i++) dsu[i] = i;
  ll ans = 0;
  for (auto c : e) {
    int u = c.second.first, v = c.second.second;
    if (get(u) != get(v)) {
      uni(u, v);
      ans += c.first;
    }
  }
  cout << ans << '\n';
}

24 Likes

this and add square questions were great, learnt a lot thanks

3 Likes

It took me 4 days to solve this one, I found a similar type of question too but it was Euclidean distance. Somewhat similar question, I used it’s solution to solve this one for 10 points :stuck_out_tongue: :
https://www.codechef.com/problems/CHEFGAME

I read so many articles, even came across minimum spanning tree of 2D with Manhattan distance then too It took me a lot of time to figure out how to actually do it for all dimensions. I don’t know much about masking so I wrote all possible conditions:

My 400+ line AC Code: https://www.codechef.com/viewsolution/38771350

It was amazing question!! Thank you!!

23 Likes

I was stuck at this problem for the last 6 days ,finally solved it on 8th day.
This and adding squares were great problems.
Learned a lot in this long challenge.

5 Likes

Just like in Lunchtime or cookoff , why CC doesn’t make Video Editorial for these , please make for long too , at least from 5’th question onwards.

5 Likes

Could anyone help me with my logic?
Here is my code…

http://p.ip.fi/wQ7R

Let’s me know if you could understand something, i will try to explain.
PS: I didn’t use any algo sort of thing, but an observation to select nodes in such a way that I could get max weight.

I can’t solve this for full but i came across lot of computation geometry algorithms like line sweep ,
Delanuy triangulation . I know this question could be solve by delanuay triangulation but couldn’t implement it.
i any one has use this method i would be very thankful to them to share their ideas on these.

1 Like

Research is still going on for Delaunay’s triangulation in dimensions >=3

1 Like

After seeing the hard work of people like you and then plagiarism from others, it makes me sad.

5 Likes

Ya I too proceeded in the same way but I was adding all Di instead of multiplying, that’s why I couldn’t solve it full even with >25 wrong submissions

1 Like

what i was thinking after completing for partial that if i am able to find two points whose distance is maximum let say p1 and p2,
then i will add this max distance and
while iterating through the points and not p1 and not p2
ans+=max((p1-pi),(p2-pi))

1 Like

@ssrivastava990 Actually, it exists! Go check it out here.

1 Like

Yeah , But I think instead of live they record separate video for each question and attach the video above.

Yup any how it was intereseting to come across this topics

@ssrivastava990 Bro, I think it doesn’t matter whether it’s live or recorded because you can access the video editorial any time on youtube so, that’s not an issue. But yeah, they can provide the link in every editorial.

where is the video tutorial for DDIMMST?

2 Likes

video bna de bro in do question pe

Did someone read this paper and tried to implement based on this ?

The editorial is shit man. Learn from codeforces!! short, precise and easy to understand.

For eg : Read G of this editorial, sorry for the bad language, but it really is SHIT.

9 Likes

You overkilled it dude :rofl:

1 Like