HackerEarth Replace and maximize problem solution

In this HackerEarth Replace and maximize problem solution You are given a square grid consisting of H rows and columns respectively. Each of the cells in the grid consists of either 0, 1, or 2. You are required to make the grid binary which means that the cell value should be 1 or 2. To do this task, you must replace each 2 and you can replace any 2 by either 0 or 1.

Grid value: It is the sum of XOR between all pairs of cells such that they share the side.

Your task is to replace each 2 by 1 or 0 in such a way that the grid value is maximized.

HackerEarth Replace and maximize problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
struct edge {
    int from, to;
    long long mx;
};
 
long long max_flow_dinic(vector<vector<pair<int, long long>>> g_main, int s, int t) {
    int n = g_main.size();
    vector<vector<int>> g(n);
    vector<edge> e;
    for (int u = 0; u < n; ++u) {
        for (auto pr : g_main[u]) {
            int v = pr.first;
            long long w = pr.second;
            g[u].push_back(e.size());
            e.push_back({u, v, w});
            g[v].push_back(e.size());
            e.push_back({v, u, 0});
        }
    }
    long long flow = 0;
    vector<int> layer(n, -5);
    vector<int> q(n + 10);
    int ql, qr;
    vector<int> ptr(n, 0);
    for (int i = 0; i < n; ++i) {
        layer.assign(n, -5);
        ptr.assign(n, 0);
        ql = 0;
        qr = 1;
        q[0] = s;
        layer[s] = 0;
        while (ql < qr) {
            int v = q[ql++];
            for (auto k : g[v]) {
                if (e[k].mx > 0 && layer[e[k].to] == -5) {
                    layer[e[k].to] = layer[v] + 1;
                    q[qr++] = e[k].to;
                }
            }
        }
        if (layer[t] == -5)
            break;
        long long prev_flow = flow;
        while (true) {
            function<long long(int, long long)> go = [&](int v, long long now) -> long long {
                if (v == t)
                    return now;
                while (ptr[v] < g[v].size()) {
                    if (layer[v] + 1 == layer[e[g[v][ptr[v]]].to] && e[g[v][ptr[v]]].mx > 0) {
                        long long next = min(now, e[g[v][ptr[v]]].mx);
                        long long x = go(e[g[v][ptr[v]]].to, next);
                        if (x > 0) {
                            e[g[v][ptr[v]]].mx -= x;
                            e[g[v][ptr[v]]^1].mx += x;
                            return x;
                        } else {
                            ++ptr[v];
                        }
                    } else {
                        ++ptr[v];
                    }
                }
                return 0;
            };
            long long el_flow = go(s, 1e9l * 1e9l * 4l);
            if (el_flow == 0)
                break;
            flow += el_flow;
        }
        if (flow == prev_flow)
            break;
    }
    return flow;
}
int main() {
    FIO;
    ll n; cin>>n;
    vector<vector<ll>>v(n,vector<ll>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>v[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i + j) % 2 == 1) {
                if (v[i][j] !=2) {
                    v[i][j] ^= 1 ^ 0;
                }
            }
        }
    }
    vector<vector<pair<int, ll>>> g(n * n + 2);
    for (int i = 0; i < n * n; ++i) {
        if (v[i / n][i % n] == 0)
            g[n * n].emplace_back(i, 1e9);
        if (v[i / n][i % n] == 1)
            g[i].emplace_back(n * n + 1, 1e9);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - 1; ++j) {
            g[i * n + j].emplace_back(i * n + (j + 1), 1);
            g[i * n + j + 1].emplace_back(i * n + j, 1);
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i * n + j].emplace_back((i + 1) * n + j, 1);
            g[(i + 1) * n + j].emplace_back(i * n + j, 1);
        }
    }
 
    cout << n * (n - 1) * 2 - max_flow_dinic(g, n * n, n * n + 1) << 'n';

  return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


namespace F {
    const int maxn = 1e4 + 14, maxm = 20 * maxn, inf = 1e9, so = maxn - 1, si = maxn - 2;
    int ptr[maxn], head[maxn], prv[maxm], to[maxm], cap[maxm], d[maxn], q[maxn], ec;

    void init() {
        memset(head, -1, sizeof head);
        ec = 0;
    }

    void add(int v, int u, int vu, int uv = 0) {
        to[ec] = u, prv[ec] = head[v], cap[ec] = vu, head[v] = ec++;
        to[ec] = v, prv[ec] = head[u], cap[ec] = uv, head[u] = ec++;
    }

    bool bfs() {
        memset(d, 63, sizeof d);
        d[so] = 0;
        int h = 0, t = 0;
        q[t++] = so;
        while (h < t) {
            int v = q[h++];
            for (int e = head[v]; e >= 0; e = prv[e])
                if (cap[e] && d[to[e]] > d[v] + 1) {
                    d[to[e]] = d[v] + 1;
                    q[t++] = to[e];
                    if (to[e] == si)
                        return 1;
                }
        }
        return 0;
    }

    int dfs(int v, int f = inf) {
        if (v == si || f == 0)
            return f;
        int r = 0;
        for (int &e = ptr[v]; e >= 0; e = prv[e])
            if (d[v] == d[to[e]] - 1) {
                int x = dfs(to[e], min(f, cap[e]));
                f -= x, r += x;
                cap[e] -= x, cap[e ^ 1] += x;
                if (!f)
                    break;
            }
        return r;
    }

    int mf() {
        int ans = 0;
        while (bfs()) {
            memcpy(ptr, head, sizeof ptr);
            ans += dfs(so);
        }
        return ans;
    }
};

const int MAX_N = 1e2 + 14;

int n;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    F::init();
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int x;
            cin >> x;
            x ^= x != 2 && (i + j) % 2;
            if (x == 0)
                F::add(F::so, i * n + j, F::inf);
            else if (x == 1)
                F::add(i * n + j, F::si, F::inf);
            if (i + 1 < n) {
                F::add(i * n + j, i * n + n + j, 1);
                F::add(i * n + n + j, i * n + j, 1);
            }
            if (j + 1 < n) {
                F::add(i * n + j, i * n + j + 1, 1);
                F::add(i * n + j + 1, i * n + j, 1);
            }
        }
    }
    cout << n * (n - 1) * 2 - F::mf() << 'n';
}

coding problems solutions