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";
}
}