Problem: transposing_tiles (2023 finals)

*Bejeweled™* is a classic puzzle game where the player tries to match three-in-a-row in a 2D grid by swapping adjacent tile pairs. You may remember Hacker Cup's [spinoff](https://www.facebook.com/codingcompetitions/hacker-cup/2022/final-round/problems/C) by the name of *Isblinged™*. The all new sequel, *Isblinged 2*, is also played on a grid of \(R\) rows by \(C\) columns of tiles where the tile at \((i, j)\) is of an integer type \(G_{i,j}\).

At any time, the *score* of the grid is the number of subarrays of \(3\) equal tiles in either a single row or column (i.e. either a \(3 \times 1\) or \(1 \times 3\) submatrix). Note that different subarrays can overlap, and will each count toward the score. The score of the initial grid is guaranteed to be \(0\).

You will make exactly \(2\) moves, where each involves swapping a pair of adjacent tiles (either in the same row or column). What is the maximum score that can be achieved after the \(2\) moves?

# Constraints

\(1 \le T \le 100\)
\(1 \le R, C \le 1{,}000\)
\(R*C \ge 2\)
\(1 \le G_{i,j} \le 1{,}000{,}000\)

The sum of \(R * C\) across all test cases is at most \(4{,}000{,}000\).

# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is first a line containing two space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which contains \(C\) space-separated integers \(G_{i,1..C}\).

# Output Format

For the \(i\)th case, print a line containing `"Case #i: "` followed by a single integer, the maximum score.

# Sample Explanation

In the first case, one possible optimal ordered pair of swaps is depicted below:

{{PHOTO_ID:1050535959425825|WIDTH:750}}

The total score is \(5\) as there are \(3\) equal subarrays in the the first row and \(2\) in the second.



Sample input:
3
2 5
1 1 2 1 1
2 2 1 3 2
1 4
1 1 2 1
5 1
1
2
1
2
1


Sample output:
Case #1: 5
Case #2: 1
Case #3: 1


Solution: Consider all possible initial moves (of swapping one pair of adjacent tiles) and the corresponding score achieved. Note that to calculate the score of \(1\) swap, it is enough to consider the submatrix of size \(7\) x \(7\) centered at one of the tiles being swapped.

One candidate for the answer is a pair of \(1\)-swaps as long as these swaps are not close to each other (otherwise they might interfere). We also need to consider swaps that are close to each other. For that, consider some tile \(A\) to be swapped with an adjacent one, and another tile \(B\) also to be swapped with another adjacent one. It's enough to consider all tiles \(B\) that are in either the same column or same row as \(A\), and with a Manhattan distance of at most \(2\) from \(A\).

For each tile chosen to be swapped, there are at most \(4\) tiles adjacent to it. With that, the overall time complexity is \(\mathcal{O}(R*C*(K + \log(R*C)))\), where \(K\) is a constant denoting the number \(2\)-swaps that can be made close to each other as well as checking the score for them. \(K\) is approximately \(7*7*8*4*4 = 6272\).


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

int N, M;
vector<vector<int>> G;

inline bool check(int r, int c) {
  return r >= 0 && c >= 0 && r < N && c < M;
}

inline void upd_options(int r, int c, vector<pair<int, int>>& options) {
  options.emplace_back(r, c);
  for (auto [r2, c2] : {pair{r - 2, c}, {r - 1, c}, {r, c - 1}, {r, c - 2}}) {
    if (r2 >= 0 && c2 >= 0) {
      options.emplace_back(r2, c2);
    }
  }
}

int count(vector<pair<int, int>>& options) {
  sort(options.begin(), options.end());
  int res = 0;
  for (int i = 0; i < (int)options.size(); i++) {
    if (i > 0 && options[i] == options[i - 1]) {
      continue;
    }
    auto [r, c] = options[i];
    res += (c + 2 >= M) ? 0 : G[r][c] == G[r][c + 1] && G[r][c] == G[r][c + 2];
    res += (r + 2 >= N) ? 0 : G[r][c] == G[r + 1][c] && G[r][c] == G[r + 2][c];
  }
  return res;
}

int solve() {
  cin >> N >> M;
  G.assign(N, vector<int>(M));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> G[i][j];
    }
  }
  vector<vector<int>> b(N, vector<int>(M));
  vector<int> cnts(1 << 7, 0);
  vector<pair<int, int>> options, semi_options;
  int res = 0;
  int skip_same = (N > 4 || M > 4);
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < M; c++) {
      semi_options.clear();
      upd_options(r, c, semi_options);
      for (auto [r2, c2] : {pair{r + 1, c}, {r, c + 1}}) {
        if (!check(r2, c2) || G[r][c] == G[r2][c2]) {
          continue;
        }
        swap(G[r][c], G[r2][c2]);
        options = semi_options;
        upd_options(r2, c2, options);
        b[r][c] = max(b[r][c], count(options));
        swap(G[r][c], G[r2][c2]);
      }
      if (skip_same) {
        res = max(res, b[r][c]);
      }
      cnts[b[r][c]]++;
    }
  }
  int max_cnt = 0;
  for (int i = 0; i < (int)cnts.size(); i++) {
    if (cnts[i]) {
      max_cnt = max(max_cnt, i);
    }
  }
  const int WINSZ = 3;
  for (int r = 0; r < N; r++) {
    for (int c = 0; c < M; c++) {
      if (res == 16) {
        break;
      }
      if (b[r][c] + 8 <= res) {
        continue;
      }
      if (skip_same) {
        bool found = false;
        for (auto [r11, c11] : {pair{r + 1, c}, {r, c + 1}}) {
          if (!check(r11, c11)) {
            continue;
          }
          if (G[r][c] != G[r11][c11]) {
            found = true;
            break;
          }
        }
        if (!found) {
          continue;
        }
      }
      for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {
        for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {
          cnts[b[r2][c2]]--;
        }
      }
      int cur_max = 0;
      for (int i = max_cnt; i > 0; i--) {
        if (cnts[i]) {
          cur_max = i;
          break;
        }
      }
      res = max(res, cur_max + b[r][c]);
      for (auto [r11, c11] : {pair{r + 1, c}, {r, c + 1}}) {
        if (!check(r11, c11) || (skip_same && G[r][c] == G[r11][c11])) {
          continue;
        }
        swap(G[r][c], G[r11][c11]);
        semi_options.clear();
        upd_options(r, c, semi_options);
        upd_options(r11, c11, semi_options);
        for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {
          for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {
            for (auto [r22, c22] : {pair{r2 + 1, c2}, {r2, c2 + 1}}) {
              if (!check(r22, c22) || (skip_same && G[r2][c2] == G[r22][c22])) {
                continue;
              }
              swap(G[r2][c2], G[r22][c22]);
              options = semi_options;
              upd_options(r2, c2, options);
              upd_options(r22, c22, options);
              res = max(res, count(options));
              swap(G[r2][c2], G[r22][c22]);
            }
          }
        }
        swap(G[r][c], G[r11][c11]);
      }
      for (int r2 = max(0, r - WINSZ); r2 <= min(r + WINSZ, N - 1); r2++) {
        for (int c2 = max(0, c - WINSZ); c2 <= min(c + WINSZ, M - 1); c2++) {
          cnts[b[r2][c2]]++;
        }
      }
    }
  }
  return res;
}

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