Editorial - Bảng đẹp

1. Điều kiện tồn tại

Gọi ~s_j~ là tổng của cột ~j~. Vì mỗi hàng là một hoán vị của ~1, 2, \ldots, n~, nên tổng tất cả các phần tử trong bảng là cố định:

~\sum_{j=1}^{n} s_j = k \cdot \frac{n(n+1)}{2}~.

Nếu bảng đẹp, dãy ~s_1, s_2, \ldots, s_n~ là một cấp số cộng công sai ~1~, nên có dạng:

~x,\ x+1,\ x+2,\ \ldots,\ x+n-1~.

Tổng của dãy này là:

~n \cdot x + \frac{n(n-1)}{2}~.

Suy ra cần có:

~n \cdot x + \frac{n(n-1)}{2} = k \cdot \frac{n(n+1)}{2}~,

hay:

~x = \frac{k(n+1) - (n-1)}{2}~.

Vì ~x~ phải là số nguyên, điều kiện cần là:

~k(n+1) - (n-1)~ phải chẵn.

Lời giải xây dựng trong mã của bạn dùng đúng điều kiện này: nếu biểu thức trên lẻ thì in ~-1~ ngay. fileciteturn1file0

2. Dựng một bảng đẹp đích

Sau khi biết bài toán có nghiệm, ta chỉ cần dựng một bảng đẹp mẫu rồi biến đổi từng hàng của bảng ban đầu về đúng hàng tương ứng trong bảng mẫu.

Trường hợp ~k~ lẻ

Ta dựng xen kẽ:

• Hàng lẻ: ~1, 2, 3, \ldots, n~
• Hàng chẵn: ~n, n-1, \ldots, 1~

Khi đó tổng cột tăng đều thêm ~1~.

Trường hợp ~k~ chẵn

Ta dựng riêng hai hàng đầu theo một mẫu đặc biệt:

• Hàng 1: các số lẻ tăng dần rồi đến các số chẵn
• Hàng 2: một thứ tự giảm vòng như trong lời giải

Hai hàng này tạo ra dãy tổng cột liên tiếp. Các hàng từ ~3~ trở đi tiếp tục xen kẽ tăng dần / giảm dần như trên. Đây chính là cách xây dựng được cài trong lời giải đã tải lên. fileciteturn1file0

3. Biến đổi từng hàng bằng các phép đổi chỗ

Với mỗi hàng, ta biết:

• hàng hiện tại là một hoán vị của ~1..n~
• hàng đích cũng là một hoán vị của ~1..n~

Ta cần biến hoán vị hiện tại thành hoán vị đích bằng các phép đổi chỗ trong cùng một hàng.

Cách làm chuẩn:

1. Với mỗi giá trị, lưu vị trí của nó trong hàng đích.
2. Từ hàng hiện tại, xây dựng hoán vị ~perm~ sao cho ~perm[i]~ là vị trí đích của phần tử đang đứng ở cột ~i~.
3. Mỗi chu trình của ~perm~ có thể sửa bằng các phép đổi chỗ trực tiếp.
4. Số phép đổi chỗ trên một hàng không vượt quá ~n-1~.

Tổng số phép đổi chỗ trên toàn bảng nhỏ hơn ~k \cdot n \le 5 \cdot 10^5 < 10^6~, nên luôn thỏa yêu cầu.

4. Độ phức tạp

• Dựng bảng đích: ~O(kn)~
• Xử lý hoán vị từng hàng: ~O(kn \log n)~ nếu dùng set, hoặc ~O(kn)~ nếu quản lý chu trình khéo hơn
• Với ràng buộc ~k \le 5~, ~n \le 10^5~, cách cài trong lời giải là đủ nhanh. fileciteturn1file0

5. Code C++ tham khảo

Dưới đây là lời giải bạn đã tải lên:

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

#define fi   first
#define se   second

#define MAX   100100

struct Transform {
    int row, from, to;
    Transform(int _row = 0, int _from = 0, int _to = 0) {
        row = _row; from = _from; to = _to;
    }

    void print(void) const {
        printf("%d %d %d\n", row, from, to);
    }
};

int k, n;
int input[10][MAX], output[10][MAX], perm[MAX], pos[MAX];
vector<Transform> transforms;

void solve(void) {
    scanf("%d%d", &k, &n);
    FOR(j, 1, k) FOR(i, 1, n) scanf("%d", &input[j][i]);

    if ((k * (n + 1) - (n - 1)) % 2 != 0) {
        printf("-1\n");
        return;
    }

    if (k % 2 != 0) {
        FOR(j, 1, k) FOR(i, 1, n) output[j][i] = j % 2 == 1 ? i : n - i + 1;
    } else {
        int val = 1;
        FOR(i, 1, n) {
            output[1][i] = val;
            val += 2;
            if (val > n) val = 2;
        }
        val = (n + 1) / 2;
        FOR(i, 1, n) {
            output[2][i] = val;
            val--;
            if (val < 1) val = n;
        }

        FOR(i, 1, n - 1) {
            int cur = output[1][i] + output[2][i];
            int next = output[1][i + 1] + output[2][i + 1];
            assert(cur + 1 == next);
        }

        FOR(j, 3, k) FOR(i, 1, n) output[j][i] = j % 2 == 1 ? i : n - i + 1;
    }

    FOR(row, 1, k) {
        FOR(i, 1, n) pos[output[row][i]] = i;
        FOR(i, 1, n) perm[i] = pos[input[row][i]];

        set<int> diffPos;
        FOR(i, 1, n) if (perm[i] != i) diffPos.insert(i);
        while (!diffPos.empty()) {
            int x = *diffPos.begin();
            int y = perm[x];

            transforms.push_back(Transform(row, x, y));
            swap(perm[x], perm[y]);
            if (x == perm[x]) diffPos.erase(x);
            if (y == perm[y]) diffPos.erase(y);
        }
    }

    assert(transforms.size() < (int)1e6);
    printf("%d\n", (int)transforms.size());
    for (const Transform &t : transforms) t.print();
}

int main(void) {
    solve();
    return 0;
}