Kickstart solutions

Kickstart Round A 2021

Problem D: Checksum

Given a $01$ matrix with noise (represented by $-1$) and their checksum in row/column direction. You can use some cost to recover a number from noise. Calculate the minimum cost that recovers the whole matrix.

According to characteristic of xor, we can recover a number without any cost if it is the only unknown number in this row/column. And after recovering it, maybe another number can be recovered. If we use brute-force to check this, the complexity will be very huge.

Considering a bipartite graph based on rows and columns like the graph above, a node can be erased if and only if it is a leaf. After removing all of leaves, if the graph is a tree, there will be no nodes. Otherwise, there will be some cycles. In this case, we must use some cost to break the cycles. So the problem becomes: how to remove some edges to change the graph to a tree, which is a spanning tree problem. The tree edge is the cost that we do not need to pay. So if we can calculate the maximum spanning tree (in fact forest here) for the graph, the answer is the total cost minus tree edges cost.

Here using kruscal algorithm, we can solve this problem in $O(n^2 \log n)$. About how to calculate maximum spanning forest, I choose to add a super node which connects to all of nodes with cost $0$. Then graph becomes connected and the edges with cost $0$ will not influence the maximum spanning forest.

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 1007;

vector<pair<int, int>> edges;
int cost[maxn][maxn];
int p[maxn];

int fi(int x) {
    if(x == p[x])   return x;
    return p[x] = fi(p[x]);
}

long long kruscal(int n) {
    for (int i = 0; i < n; i++) {
        p[i] = i;
    }
    sort(edges.begin(), edges.end(), [](const pair<int, int> &l, const pair<int, int> &r){
        return cost[l.first][l.second] > cost[r.first][r.second];
    });
    int cnt = 0;
    long long ret = 0;
    for (auto [u, v]: edges) {
        int w = cost[u][v];
        int p1 = fi(u), p2 = fi(v);
        if (p1 != p2) {
            ret += w;
            p[p1] = p[p2];
            cnt++;
        }
        if (cnt == n - 1)   break;
    }
    return ret;
}

int main() {
    int t, n;
    cin >> t;
    for (int _t = 1; _t <= t; _t++) {
        memset(cost, 0, sizeof(cost));
        memset(p, 0, sizeof(p));
        edges.clear();
        cin >> n;
        int tmp;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> tmp;
                if (tmp == -1) {
                    edges.emplace_back(i, n + j);
                }
            }
        }
        for (int i = 0; i < 2 * n; i++) {
            edges.emplace_back(i, 2 * n);
        }
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> cost[i][n + j];
                cost[n + j][i] = cost[i][n + j]; 
                ans += cost[i][n + j];
            }
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) cin>>tmp;
        }
        cout<<"Case #" << _t <<": "<<ans - kruscal(2 * n + 1)<<endl;
    }
}