Ta có nhận xét : các thao tác loại 1 (tráo 2 cột) và các thao tác loại 2 (biến đổi 1 hàng) là độc lập với nhau.
Thao tác loại 1 không làm thay đổi thứ tự của các hàng.
Thao tác loại 2 không làm thay đổi thứ tự của các cột.

Subtask 1: \(n \le 4\)

Nhận thấy các thao tác 2 r chỉ có 2 lựa chọn: thực hiện hoặc không (đảo một hàng chẵn lần thì bảng coi như không đổi). Do đó ta có \(2^n\) cách thực hiện các thao tác loại 2.

Các thao tác loại 1 tạo ra hoán vị của các cột. Xét thuật toán sắp xếp để biến dãy \(a_1,a_2,a_3,...,a_n\) thành \(a_{p_1},a_{p_2},a_{p_3},...,a_{p_n}\) với \(p\) là hoán vị của \(n\) số nguyên dương đầu tiên : Duyệt \(i\) từ 1 tới \(n\), số \(p_i\) hiện tại nằm trong đoạn từ \(i\) tới \(n\) nên ta cần thực hiện không quá \(n-i\) thao tác loại 1 (tráo 2 cột kề nhau) để đưa \(p_i\) về vị trí \(i\). VD để biến dãy \(a_1,a_2,a_3,a_4\) thành dãy \(a_2,a_4,a_3,a_1\), ta thực hiện các thao tác như sau :

• \(1,2,3,4 \rightarrow 2,1,3,4\) (một thao tác 1 1)
• \(2,1,3,4 \rightarrow 2,4,1,3\) (hai thao tác 1 3, 1 2)
• \(2,4,1,3 \rightarrow 2,4,3,1\) (một thao tác 1 3)

Từ đó ta có thuật toán trâu như sau : Đệ quy để chọn cách thực hiện các thao tác loại 2. Sau đấy lại tiếp tục đệ quy để chọn cách thực hiện các thao tác loại 1 (tại cột \(i\), sẽ thực hiện tráo đổi để đưa cột \(j \ge i\) về vị trí cột \(i\) hiện tại). Sau khi đã có một chuỗi các thao tác ta biến đổi bảng C và kiểm tra có khác bảng B tại nhiều nhất một ô?

Độ phức tạp : \(O(2^nn!n^2)\)

Subtask 2: \(n \le 10\)

Ta đệ quy tất cả cách thực hiện thao tác loại 1. Lúc này các cột đã hoán vị cho nhau, vị trí của chúng là cố định. Việc sử dụng các thao tác loại 2 có thể quyết định được trong \(O(n^2)\). Xét từng của bảng, ta sẽ quyết định đảo/ không đảo hàng này để bảng số có ít khác biệt nhất so với bảng mục tiêu (B). Có thể loại bỏ đi được vài thao tác loại 2 nếu tổng số ô khác biệt không quá 1.

Độ phức tạp : \(O(n!n^2)\)

Subtask 3: \(n \le 20\)

Ta đệ quy tất cả cách thực hiện thao tác loại 2. Bây giờ cần giải quyết bài toán : tính số thao tác loại 1 ít nhất (tráo 2 cột liền kề) để biến đổi bảng C sao cho chỉ sai khác với bảng B nhiều nhất một ô.

Lúc này, ta coi mỗi cột như một số nhị phân có \(n\) bit. Các bit của cột \(i\) theo thứ tự là \((1,i) (2,i) (3,i) … (n,i)\). Như vậy có thể kiểm tra cột này giống cột kia hay không, hoặc sai khác nhau bao nhiêu ô trong \(O(1)\) (vì lúc này là thực hiện phép tính trên số).
Xét đa tập SC chứa các cột của C hiện tại, đa tập SB chứa các cột của B. Nếu SC khác SB tối đa là một phần tử (nếu có, 2 phần tử ấy sai khác nhau ở đúng 1 bit) thì có thể tiếp tục biến đổi C đến khi thỏa mãn. Ta biến đổi bằng thuật toán trình bày ở subtask 1, có thể chứng minh số thao tác đã dùng là ít nhất (chính là tổng nghịch thế của hoán vị \(p\)).

Độ phức tạp: \(O(2^nn^2)\)

Subtask 4:

Chỉ có \(n^2+1\) trường hợp cho cấu hình cuối cùng của bảng C (giống hoàn toàn hoặc sai khác B tại một trong \(n \times n\) ô) → cần phải có cách duyệt thông minh hơn.

Xử lý riêng trường hợp \(n = 1\).

Xét cột \(x\) bất kì của bảng A, có 2 trường hợp:

• TH1: cột \(x\) không chứa ô khác biệt nào → cột \(x\) bằng với một cột bất kì trong bảng B → ta duyệt qua \(n\) khả năng có thể của cột \(x\), với mỗi khả năng cố định duy nhất một cách thực hiện các thao tác loại 2. Lúc này bài toán quy về như subtask 3.
• TH2: cột \(x\) chứa ô khác biệt với bảng B → tồn tại cột \(y \neq x\) của A mà nó bằng đúng một cột nào đấy trong B. Như vậy chỉ cần xử lý như TH1 cho 2 cột \(x,y\) khác nhau bất kỳ.

Cụ thể hơn, TH1 được giải quyết như thế nào?
Sau khi xác định cách thực hiện thao tác loại 2, ta tạm coi số ô khác biệt trong bảng bằng tổng lượng chênh lệch số lượng bit 1 trên từng hàng của bảng C so với bảng B.

Nếu có khác biệt, ta xác định hàng \(i\) duy nhất trên bảng C mà tại hàng này, số lượng bit 1 khác biệt so với hàng \(i\) của bảng B. Sau đó duyệt cột \(j \neq x\) và đảo ô \((i,j)\) của bảng C để số lượng bit 1 là như nhau ở cả 2 bảng (khi xét xong phải trả về như cũ).

Tạm coi như bảng C lúc này chỉ cần hoán vị cột là tạo thành bảng B. Vì \(n\) lên tới 100 nên có thể Hash giá trị của mỗi cột, hoặc sử dụng bitset để xử lý như Subtask 3. Nếu hoán vị cột của C mà không tạo được B thì phương án không hợp lệ. Có cách cài đặt không cần dùng tới bitset hay hash.

Độ phức tạp : \(O(n^4)\)

Source code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 100;
const int INF = 1e18;
bool minimize(int& a, int b) {
if (a > b) return a = b, 1;
return 0;
}
using vl = bitset<MAXN>;
int n;
int inp[MAXN][MAXN];
vl col[MAXN];
vl coltar[MAXN];
vl tmp[MAXN];
int used[MAXN];
int num_change = INF;
vl vet_change;
vector<int> vet, cur;
void solve(int x, int y) {
if (x >= 0 && y >= 0 && x <= n && y <= n) col[y][x] = 1 - col[y][x];
for (int colA = 0; colA <= 0; colA++) {
for (int colB = 0; colB <= n; colB++) {
vl change = col[colA] ^ coltar[colB];
for (int i = 0; i <= n; i++) {
used[i] = 0;
tmp[i] = col[i] ^ change;
}
int cnt = change.count();
vector<int> v(n + 1);
for (int i = 0; i <= n; i++) {
int ok = 0;
for (int j = 0; j <= n; j++) {
if (!used[j] && coltar[i] == tmp[j]) {
v[i] = j;
used[j] = 1;
ok = 1;
break;
}
}
if (!ok) goto ss;
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < i; j++) if (v[j] > v[i]) cnt++;
}
if (minimize(num_change, cnt)) vet_change = change, vet = v;
ss:;
}
}
if (x >= 0 && y >= 0 && x <= n && y <= n) col[y][x] = 1 - col[y][x];
}
void swappo(int x) {
swap(cur[x], cur[x + 1]);
cout << 1 << ' ' << x + 1 << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
n--;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
cin >> inp[i][j];
col[j][i] = inp[i][j];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
cin >> inp[i][j];
coltar[j][i] = inp[i][j];
}
}
solve(-1, -1);
for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) solve(i, j);
for (int i = 0; i <= n; i++) cur.push_back(i);
if (num_change < INF) {
cout << num_change << '\n';
for (int i = n; i >= 0; i--) {
for (int j = 0; j <= n; j++) {
if (cur[j] == vet[i]) {
for (int k = j; k < i; k++) swappo(k);
}
}
}
for (int i = 0; i <= n; i++) {
if (vet_change[i]) cout << 2 << ' ' << i + 1 << '\n';
}
}
else cout << -1;
}