Problem: and (2021 finals)

Andy has no time for ores, he's just here for the `AND`s.

Andy has \(N\) pairs of integers, with each integer given in binary as a bitstring. The \(i\)th pair consists of bitstrings \(A_i\) and \(B_i\). No bitstring has leading zeros (except for the bitstring `"0"` itself).

Andy may choose at most \(K\) of these pairs for swapping. For each chosen pair \(i\), he'll swap its bitstrings \(A_i\) and \(B_i\).

After all of these swaps, he'll compute \(X\) as the bitwise `AND` of the \(N\) bitstrings \(A_{1..N}\), and \(Y\) as the bitwise `AND` of the \(N\) bitstrings \(B_{1..N}\), and finally add \(X\) and \(Y\) together. What's the maximum sum of \(X + Y\) that Andy can achieve?

Note that:

  - The integer value of a bitstring \(S\) is equal to \(S_1 * 2^{|S|-1} + S_2 * 2^{|S|-2} + ... + S_{|S|} * 2^0\).
  - The bitwise `AND` of a set of bitstrings \(S\) is a bitstring \(V\) such that, if leading zeros were appended to bitstrings in \(S\) until they all had the same length, then \(V\) also has that same length, with \(V_i\) equal to `1` if and only if all bitstrings in \(S\) have a `1` at index \(i\).


# Constraints

\(1 \le T \le 90\) 
\(1 \le N \le 2{,}000{,}000\)
\(0 \le K \le N\)
\(0 \le A_{i,j}, B_{i,j} \le 1\)

The total length of all bitstrings \(A_{1..N}\) and \(B_{1..N}\) is at most \(4{,}000{,}000\).
The total length of all bitstrings across all test cases is at most \(10{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of test cases. For each test case, there is first a line containing \(2\) space-separated integers, \(N\) and \(K\). Then, \(N\) lines follow, the \(i\)th of which contains \(2\) space-separated bitstrings, \(A_i\) and \(B_i\).


# Output

For the \(i\)th test case, print a line containing *"Case #i: "* followed by a single bitstring, the maximum achievable sum of bitstring `AND`s, with no leading zeros (unless the bitstring is ``"0"``).


# Sample Explanation

In the first case, \(X = 1011011_2 \,(91_{10})\), \(Y = 101101_2 \,(45_{10})\), and \(X + Y = 10001000_2 \,(136_{10})\).

In the second case, no swaps are allowed, so we must have \(X = 1011011_2\) `AND` \(0_2 = 0_2\) and \(Y = 0_2 \) `AND` \(101101_2 = 0_2\).

In the third case, one option is to swap \(A_1\) and \(B_1\). This yields \(X = 0_2\) `AND` \(0_2 = 0_2\) and \(Y = 1011011_2\) `AND` \(101101_2 = 1001_2\).

In the fourth case, one option is to swap \(A_1\) and \(B_1\) as well as \(A_3\) and \(B_3\), resulting in \(X = 111_2 \,(7_{10})\), \(Y = 1_2 \,(1_{10})\), and \(X + Y = 1000_2 \,(8_{10})\).


Sample input:
6
1 1
1011011 101101
2 0
1011011 0
0 101101
2 1
1011001 0
0 101101
3 3
1 111
111 1
1 111
5 1
1101 11011
11101 11111
11011 1111
10111 1001
1011 10101
5 2
1101 11011
11101 11111
11011 1111
10111 1001
1011 10101


Sample output:
Case #1: 10001000
Case #2: 0
Case #3: 1001
Case #4: 1000
Case #5: 1010
Case #6: 11010


Solution: Let \(L\) be the length of the longest bitstring. Each bit index \(i\) (counting from the right, starting at \(0\)) between \(0\) and \(L-1\) (inclusive) will contribute either \(0\), \(2^i\), or \(2*2^i\) to the answer, depending on whether it's set in all bitstrings \(A_{1..N}\) and/or in all bitstrings \(B_{1..N}\). Once we determine which of these each bit index will contribute in the optimal solution, we'll be able to compute the resulting summed bitstring in \(O(L)\) time.

Considering bit indices \(i\) in order from most to least significant (from \(L-1\) down to \(0\)), each will fall into one of three categories:

  1. If \(i\) is set in all \(2N\) bitstrings \(A_{1..N}\) and \(B_{1..N}\), then it must always contribute \(2*2^i\) to the answer.
  
  2. If, for at least one pair \(j\), \(i\) is set in neither \(A_j\) nor \(B_j\), then it must always contribute \(0\) to the answer.
  
  3. Otherwise, it may either contribute \(0\) or \(2^i\) to the answer. We should greedily cause it to contribute \(2^i\) if possible (without compromising previously-considered bit indices), as doing so would be strictly better than doing so for all later bit indices combined (as \(2^i \gt \sum_{j=0}^{i-1}{2^j}\)).

  Let \(O_j\) be the "orientation" of pair \(j\) (whether or not it's being swapped), \(X\) be the set of pairs \(j\) for which \(i\) is set in \(A_j\) but not \(B_j\), and \(Y\) be the set of pairs \(j\) for which \(i\) set in \(B_j\) but not \(A_j\).
  
  Bit index \(i\) will then contribute to the answer if and only if all pairs in \(X\) have equal \(O\) values, all pairs in \(Y\) have equal \(O\) values, and the \(X\) pairs' \(O\) values are the opposite of the \(Y\) pairs' \(O\) values. This can be expressed as a set of at most \(|X|+|Y|+1\) pairwise relationships, each stating whether a certain pair of pairs must have equal or opposite \(O\) values.

  We'll maintain information about these relationships using a [disjoint set union](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) data structure (over the \(N\) pairs), augmented such that the root of each set stores its total number of pairs and the number of pairs which must have opposite \(O\) values to the root, and such that each pair stores whether or not it must have the opposite \(O\) value to the root of its set.
  
  So, when considering each bit index \(i\), we'll make a copy of the DSU and attempt to add all of the newly-required relationships to it in \(O(N*α(N))\) time. If that proves possible without introducing conflicts, we'll take another \(O(N)\) time to compute the minimum total number of swaps required (by greedily choosing between the two possible arrangements of orientations for each set). If that comes out to at most \(K\), then we'll add \(2^i\) to the answer and keep the new state of the DSU, while we'll otherwise roll back to the DSU's prior state.
  
Each time a bit index falls into the third category described above, there must have been at least \(N\) set bits in the input (at that index). Therefore, if \(S\) is the sum of all \(2N\) bitstring lengths, then only \(O(S/N)\) bit indices can fall into that category. This means that the time complexity of this algorithm is \(O(S/N * N * α(N)) = O(S α(N))\) (effectively \(O(S)\)).


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int LIM = 4000005;

struct UnionFind {
  int N;
  vector<int> root, diff_to_root, rank, sz, diffsum;

  UnionFind(int _N):
   N(_N), root(_N), diff_to_root(_N), rank(_N), sz(_N, 1), diffsum(_N) {
    for (int i = 0; i < N; i++) {
      root[i] = i;
    }
  }

  int find(int i) {
    int r = root[i];
    if (r != i) {
      root[i] = find(r);
      diff_to_root[i] ^= diff_to_root[r];
    }
    return root[i];
  }

  bool merge(int i, int j, int d) {
    int ri = find(i), rj = find(j);
    d ^= diff_to_root[i] ^ diff_to_root[j];
    if (ri == rj) {
      return !d;
    }
    if (rank[ri] > rank[rj]) {
      swap(ri, rj);
    }
    root[ri] = rj;
    diff_to_root[ri] = d;
    sz[rj] += sz[ri];
    diffsum[rj] += d ? sz[ri] - diffsum[ri] : diffsum[ri];
    if (rank[ri] == rank[rj]) {
      rank[rj]++;
    }
    return true;
  }
};

int N, K;

void solve() {
  vector<int> both(LIM), ans(LIM);
  vector<vector<vector<int>>> ind(LIM, vector<vector<int>>(2));
  int maxL = 0;
  // Input.
  cin >> N >> K;
  for (int i = 0; i < N; i++) {
    string s[2];
    cin >> s[0] >> s[1];
    int len = max(s[0].size(), s[1].size());
    maxL = max(maxL, len);
    for (int b = 0; b < len; b++) {
      int ch[2];
      for (int j : {0, 1}) {
        int slen = s[j].size();
        ch[j] = b < slen ? s[j][slen - b - 1] - '0' : 0;
      }
      if (ch[0] && ch[1]) {
        both[b]++;
      } else {
        for (int j : {0, 1}) {
          if (ch[j]) {
            ind[b][j].push_back(i);
          }
        }
      }
    }
  }
  // Consider each bit, starting from the most significant.
  UnionFind U(N);
  for (int b = maxL - 1; b >= 0; b--) {
    ans[b] = 0;
    // Bit included twice?
    if (both[b] == N) {
      ans[b] = 2;
      continue;
    }
    // Bit not included at all?
    if (both[b] + ind[b][0].size() + ind[b][1].size() < N) {
      continue;
    }
    // Include bit once if possible.
    int k = 0;
    bool imp = false;
    UnionFind U2 = U;
    for (int i = 0; !imp && i < 2; i++) {
      for (int j = 0; !imp && j < (int)ind[b][i].size() - 1; j++) {
        if (!U2.merge(ind[b][i][j], ind[b][i][j + 1], 0)) {
          imp = true;
        }
      }
    }
    if (imp) {
      continue;
    }
    if (ind[b][0].size() > 0 && ind[b][1].size() > 0) {
      if (!U2.merge(ind[b][0][0], ind[b][1][0], 1)) {
        continue;
      }
    }
    for (int i = 0; i < N; i++) {
      if (U2.find(i) == i) {
        k += min(U2.diffsum[i], U2.sz[i] - U2.diffsum[i]);
      }
    }
    if (k > K) {
      continue;
    }
    U = U2;
    ans[b] = 1;
  }
  // Add up answer in binary.
  for (int i = 0; i < maxL; i++) {
    if (i == maxL - 1 && ans[i] >= 2) {
      ans[maxL++] = 0;
    }
    ans[i + 1] += ans[i] / 2;
    ans[i] %= 2;
  }
  // Output.
  while (maxL > 1 && !ans[maxL - 1]) {
    maxL--;
  }
  for (int i = maxL - 1; i >= 0; i--) {
    cout << ans[i];
  }
  cout << endl;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": ";
    solve();
  }
  return 0;
}