HackerEarth Grid of Many Xors problem solution

In this HackerEarth Grid of Many Xors problem solution Consider a grid with N rows and M columns, where each cell has some integer value written in it. Every cell is connected to every side adjacent cell via an undirected edge. The cost of an edge e connecting any two cells with value a and b is Ce = a xor b.

We define a good trip between two cells (r1, c1) and (r2, c2) as a trip starting at cell (r1, c1) and ending at cell (r2, c2) while visiting every cell of the grid at least once.

There is a cost associated with every good trip. Let’s say, for a given edge e, you travel that edge Te times. Then the cost of the trip is:

Summation(for all e) (Ce * Ceil(Te/2))

For the given starting cell (r1, c1) and ending cell (r2, c2), you have to find the minimum cost of a good trip.

HackerEarth Grid of Many Xors problem solution.

#include <bits/stdc++.h>
using namespace std;

struct dsu {
  vector<int> Rank, P;
  int V;
  dsu(int v = 0) : V(v) {
    Rank = vector<int>(v + 1, 0);
    P = vector<int>(v + 1, 0);
    for(int i = 0; i < P.size(); i++) {
      P[i] = i, Rank[i] = 1;
    }
  }
  int find_root(int x) { return x == P[x] ? x : P[x] = find_root(P[x]); }
  void merge(int x, int y) {
    int xr = find_root(P[x]), yr = find_root(P[y]);
    if(xr == yr) return ;
    if(Rank[xr] < Rank[yr]) swap(xr, yr), swap(x, y);
    Rank[xr] += Rank[yr];
    P[yr] = xr;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  int t, n, m, r1, c1, r2, c2;
  cin >> t;
  while(t--) {
    cin >> n >> m;
    cin >> r1 >> c1 >> r2 >> c2;
    vector<vector<int> > grid(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        cin >> grid[i][j];
      }
    }
    vector<pair<int, pair<int, int> > > edges;
    auto encode = [&](int r, int c) -> int {
      return r * m + c;
    };
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(j + 1 != m)
          edges.push_back({grid[i][j] ^ grid[i][j + 1],
                          {encode(i, j), encode(i, j + 1)}});
        if(i + 1 != n)
          edges.push_back({grid[i][j] ^ grid[i + 1][j],
                          {encode(i, j), encode(i + 1, j)}});
      }
    }
    sort(edges.begin(), edges.end());
    dsu tester(n*m);
    long long res = 0;
    for(int i = 0; i < edges.size(); i++) {
      int wt = edges[i].first, a = edges[i].second.first, b = edges[i].second.second;
      if(tester.find_root(a) != tester.find_root(b)) {
        res += wt;
        tester.merge(a, b);
      }
    }
    cout << res << 'n';
  }
  return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define f first
#define s second
#define rep(i, N) for(int i=0;i<N;i++)

int pa[100011];
int sz[100011];


int f(int x) {
    if(x == pa[x]) return x;
    return pa[x] = f(pa[x]);
}
bool join(int a, int b) {
    a = f(a);
    b = f(b);
    if(a != b) {
        if(sz[a] < sz[b]) swap(a, b);
        pa[b] = a;
        sz[a] += sz[b];
        return 1;
    }
    return 0;
}
struct Edge{
    int u,v,val;
};
bool func(Edge a, Edge b) {
    return a.val < b.val;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int N,M;
        cin >> N >> M;
        vector<vector<int> >G(N, vector<int>(M));
        int r1,c1,r2,c2;
        cin >> r1 >> c1 >> r2 >> c2;
        // No need for r1 c1 r2 c2. The value of answer is independent of them.
        map<pi, int> C;
        int cnt = 0;
        vector<Edge> E;
        rep(i, N) {
            rep(j, M) {
                cin >> G[i][j];
                C[{i,j}] = cnt++;
                if(i-1 >= 0) {
                    E.push_back({C[{i-1,j}], C[{i,j}], G[i][j]^G[i-1][j] });
                }
                if(j-1 >= 0) {
                    E.push_back({C[{i,j-1}], C[{i,j}], G[i][j]^G[i][j-1] });
                }
            }
        }
        sort(E.begin(),E.end(),func);
        for(int j=0;j<cnt;j++) {
            pa[j] = j;
            sz[j] = 1;
        }
        int ans = 0;
        for(auto e:E) {
            if(join(e.u,e.v)) ans += e.val;
        }
        cout << ans << "n";
    }
}

coding problems solutions