Lưu ý: bài viết sử dụng spoiler do phần chứng minh của bài viết hơi dài. Những phần không có spoiler là phần ý tưởng chính cho bài này.

Bài toán này được dựa trên một bài khá cổ điển, và cũng có rất nhiều trên các OJ khác nhau. Một ví dụ cụ thể là bài Timus 1401. Gamers. Bài toán chúng ta đang giải có thể coi là bài toán ngược của bài Timus 1401.

Ý tưởng

Trước khi đi vào tutorial, để diễn đạt có thể dễ dàng hơn, chúng ta sẽ quy ước một vài kí hiệu dưới đây:

• ~P_{type}~ (Piece Type) là kiểu miếng ghép, tức các giá trị ~\texttt{TL}~, ~\texttt{TR}~, ~\texttt{BR}~, , ~\texttt{BL}~.
• ~P_{type}^x~ là miếng ghép ~P_{type}~ khi được quay đi ~x~ độ theo chiều kim đồng hồ. Ví dụ ~\texttt{TL}^{90} = \texttt{TR}~, ~\texttt{TR}^{180}=\texttt{BL}~, ~\texttt{BL}^{270} = \texttt{BR}~. Chi tiết các giá trị có thể xem ở bảng trong spoiler bên dưới.

~P_{type}~	~P_{type}^{90}~	~P_{type}^{180}~	~P_{type}^{270}~
~\texttt{ TL }~	~\texttt{ TR }~	~\texttt{ BR }~	~\texttt{ BL }~
~\texttt{ TR }~	~\texttt{ BR }~	~\texttt{ BL }~	~\texttt{ TL }~
~\texttt{ BR }~	~\texttt{ BL }~	~\texttt{ TL }~	~\texttt{ TR }~
~\texttt{ BL }~	~\texttt{ TL }~	~\texttt{ TR }~	~\texttt{ BR }~

• 2 loại miếng ghép gọi là đối nhau nếu ta xoay loại này đi 180 độ thì ta có thể thu được loại kia. Nói cách khác, ~x~ và ~y~ đối nhau khi ~x^{180} = y~.
• 2 loại miếng ghép gọi là vuông góc với nhau khi ta thu được loại này bằng cách xoay 90 độ (theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ), ta thu được loại kia. Nói cách khác, ~x~ và ~y~ vuông góc với nhau khi ~x^{90} = y~ hoặc ~x^{270} = y~.

Quan sát về miếng chữ L có kích thước to hơn 1.

Để giải cả bài toán xuôi lần bài toán ngược, chúng ta có quan sát như sau: ta có thể gộp các miếng ghép thành một miếng ghép chữ L có kích thước ~2^k \times 2^k~ bất kì (từ giờ ta sẽ gọi là kích thước ~k~). Miếng ghép chữ L kích thước ~k~ có thể được xây dựng một cách đệ quy dựa vào các miếng chữ L kích thước ~k - 1~ như minh họa cho miếng ~\texttt{TL}~ dưới đây.

Ở đây miếng ~\texttt{TL}~ kích thước ~k~ được tạo bởi 2 miếng ~\texttt{TL}~ kích thước ~k - 1~, 1 miếng ~\texttt{TR}~ kích thước ~k - 1~ và 1 miếng ~\texttt{BL}~ cũng kích thước ~k - 1~. Với các loại còn lại cũng có thể xây dựng một cách tương tự bằng cách xoay miếng ~\texttt{TL}~.

Bài toán xuôi

Dựa vào quan sát trên, ta có thể giải bài toán xuôi (Timus 1401) như sau:

Với bảng có kích thước ~k~ và vị trí cần bỏ trống ~(r, c)~, ta có thể xác định xem vị trí này nằm trong góc phần tư nào của bảng. Xác định được vị trí, ta có thể điền miếng chữ L với kích thước ~k~ có góc phần tư tương ứng vào bảng. Sau đó ta sẽ tìm vị trí ~(r', c')~ là vị trí ô trống trong góc phần tư đang được bỏ trống, và đệ quy giải bài toán này cho ~k - 1~ và ~(r', c')~. Quá trình sẽ được lặp cho đến khi ~k = 0~.

Với mỗi một ô trống bất kì, lúc nào ta cũng cần điền ~k~ miếng ghép chữ L có kích thước từ 1 đến ~k~ độc lập với nhau.

Subtask 1 có thể được giải nhờ vào bài toán xuôi: ta có thể tính toán đáp án cho mọi bảng có kích thước bé hơn ~9~ và trả lời các truy vấn dựa vào đáp án đã tính toán trước đó.

Bài toán ngược

Lời giải cho bài toán ngược thật ra rất giống với bài toán xuôi.

Với mỗi một bộ số ~cnt_{\texttt{TL}}, cnt_{\texttt{TR}}, cnt_{\texttt{BR}}, cnt_{\texttt{BL}}~, vị trí góc phần tư của ô bỏ trống hoàn toàn có thể xác định được một cách duy nhât. Góc phần tư mà ô bị bỏ trống nằm vào sẽ là ~x~ (~x~ là ~P_{type}~) thỏa mãn:

$$ cnt_x - cnt_{x^{180}} > |cnt_{x^{90}} - cnt_{x^{270}}| $$

Nói cách khác, hiệu số lượng đếm giữa ~x~ và đối của ~x~ phải lớn hơn sai khác giữa 2 loại miếng vuông góc với ~x~.

Xác định được ~x~, ta có thể trừ bộ số ~cnt~ đi cho số lượng miếng ghép của miếng chữ L loại ~x~ kích thước ~k~ và đệ quy giải bài toán cho bộ số ~cnt~ và ~k - 1~ cho đến khi ~k = 1~. Trong quá trình giải mà không tìm đợc số ~x~ thỏa mãn, hoặc đến khi ~k = 1~ mà vẫn còn miếng ghép chưa được dùng, không có cách điền thỏa mãn.

Chứng minh thuật toán

Với bài toán ngược này, ta cần quan tâm đến số lượng mỗi miếng ghép đơn vị cho từng miếng ghép kích thước ~k~. Tức ta cần quan tâm đến giá trị ~C_{k, x, y}~ (với ~x~ và ~y~ là ~P_{type}~) là số lượng miếng ghép đơn vị loại ~y~ cần có để tạo ra miếng loại ~x~ kích thước ~k~. Gía trị của ~C~ có thể tìm được công thức truy hồi (tức có thể sử dụng quy hoạch động), hoặc sử dụng công thức tính nhanh.

Trường hợp cơ bản cho ~C~.

Công thức truy hồi và công thức tính nhanh đều không đúng với trường hợp cơ bản.

~C_{1, x, x} = 1~ và ~C_{1, x, y} = 0~ với (~y \ne x~).

Công thức truy hồi cho ~C~

Với hình minh hoạ trên, ta có thể viết:

$$ C_{k, \texttt{TL}, y} = 2 \cdot C_{k - 1, \texttt{TL}, y} + C_{k - 1, \texttt{TR}, y} + C_{k - 1, \texttt{BL}, y} $$ Công thức này có được nhờ vào chính quan sát cách ghép miếng chứ L kích thước lớn hơn một ở phía trên.

Tổng quát hơn: $$ C_{k, x, y} = 2 \cdot C_{k - 1, x, y} + C_{k - 1, x^{90}, y} + C_{k - 1, x^{270}, y} $$

Công thức tính nhanh cho ~C~

Dựa vào công thức truy hồi và trường hợp cơ bản, ta hoàn toàn có thể chứng minh công thức dưới đây đúng sử dụng quy nạp.

$$ \begin{array}{rcl} C_{k, \texttt{TL}, \texttt{TL}} &=& 4^{k - 2} + 2^{k - 2} \\ C_{k, \texttt{TL}, \texttt{TR}} &=& 4^{k - 2} \\ C_{k, \texttt{TL}, \texttt{BR}} &=& 4^{k - 2} - 2^{k - 2} \\ C_{k, \texttt{TL}, \texttt{BL}} &=& 4^{k - 2} \end{array} $$

Tổng quát hơn $$ \begin{array}{lcl} C_{k, x, x} &=& 4^{k - 2} + 2^{k - 2} \\ C_{k, x, x^{90}} &=& 4^{k - 2} \\ C_{k, x, x^{180}} &=& 4^{k - 2} - 2^{k - 2} \\ C_{k, x, x^{270}} &=& 4^{k - 2} \end{array} $$

Để chứng minh thuật toán, ta sử dụng công thức tính nhanh.

Định lý

Nhắc lại thuật toán: Với một bộ số ~cnt~ và kích thước bảng ~k~, góc phần tư chứa ô trống là ~x~ sao cho

$$ cnt_x - cnt_{x^{180}} > |cnt_{x^{90}} - cnt_{x^{270}}| $$

Nói cách khác, hiệu số lượng đếm giữa ~x~ và đối của ~x~ phải lớn hơn sai khác giữa 2 loại miếng vuông góc với ~x~.

Điều trên thực tế được tương đương 3 điều dưới đây, và ta sẽ đi chứng minh lần lượt chúng.

• ~cnt_x~ là lớn nhất trong số các phần tử của bộ số ~cnt~.
• ~cnt_{x^{180}}~ là nhỏ nhất trong số các phần tử của bộ số ~cnt~.
• ~cnt_x - cnt_{x^{180}} \ne |cnt_{x^{90}} - cnt_{x^{270}}|~.

Định lý hiển nhiên đúng với trường hợp ~k = 1~. Dưới đây là chứng minh cho trường hợp ~k > 1~.

Chứng minh chiều đảo

Ta giả sử rằng ô trống chắc chắn ở góc phần tư thứ ~x~. Để chứng minh ~cnt_x~ là lớn nhất, đầu tiên ta có thể xét hiệu:

$$ D_1 = cnt_x - cnt_{x^{180}} $$

Ta sẽ đi tìm giá trị nhỏ nhất của biểu thức này. Để tìm giá trị này, ta có thể xem mỗi miếng ghép chữ L kích thước ~i~ đóng góp cho biểu thức này ra sao dựa vào giá trị ~C~ trong tất cả các góc quay:

• Với miếng chữ L kích thước ~k~, vì ta đã cố định điền miếng ghép loại ~x~, nên miếng ghép đóng góp cho biểu thức này ~(4^{k - 2} + 2^{k - 2}) - (4^{k - 2} - 2^{k - 2}) = 2 \times 2^{k - 2} = 2^{k - 1}~.
• Với miếng ghép kích thước ~1 < i < k~, hoặc nó sẽ không đóng ghép gì (nếu như loại đó vuông góc với ~x~), hoặc nó sẽ đóng góp một lượng có trị tuyệt đối bằng ~(4^{i - 2} + 2^{i - 2}) - (4^{i - 2} - 2^{i - 2}) = 2 \times 2^{i - 2} = 2^{i - 1}~. Vì miếng ghép này ta không cố định, và ta đang đi tìm giá trị nhỏ nhất, và các miếng ghép kích thước ~i~ được điền độc lập nhau, nên ta sẽ lấy giá trị đóng góp là ~-2^{i - 1}~.
• Miếng chữ L kích thước 1 có thể đóng góp giá trị ~-1~.

Vậy giá trị nhỏ nhất của biểu thức ~D_1~ là: $$ 2^{k - 1} - \sum_{i = 2} ^ {k - 1} 2^{i - 1} - 1 = 2^{k - 1} - (2^{k - 1} - 2) - 1 = 1 $$

Vậy ~D_1~ dương, tức ~cnt_x > cnt_{x^{180}}~.

Xét tiếp hiệu

$$ D_2 = cnt_x - cnt_{x^{90}} $$ Tương tự, ta sẽ đi tìm giá trị nhỏ nhất của biểu thức này dựa vào từng đóng góp của các miếng chữ L.

• Với miếng chữ L kích thước ~k~, vì ta đã cố định điền miếng ghép loại ~x~, nên miếng ghép đóng góp cho biểu thức này ~(4^{k - 2} + 2^{k - 2}) - (4^{k - 2}) = 2^{k - 2}~.
• Với miếng ghép kích thước ~i~ (~1 < i < k~), tất cả các loại sẽ đóng góp một lượng có trị tuyệt đối bằng ~(4^{i - 2} + 2^{i - 2}) - (4^{i - 2} ) = 2^{i - 2}~. Với lập luận tương tự trên, ta lấy giá trị ~-2^{i - 2}~.
• Miếng chữ L kích thước 1 có thể đóng góp giá trị ~-1~.

Tổng các đóng góp sẽ là: $$ 2^{k - 2} - \sum_{i = 2} ^ {k - 1} 2^{i - 2} - 1 = 2^{k - 2} - (2^{k - 2} - 1) - 1 = 0 $$

Như vậy ~D_2~ không âm, do đó ~cnt_x \ge cnt_{x^{90}}~.

Chứng minh tương tự ta cũng có ~cnt_x \ge cnt_{x^{270}}~ do chúng vuông góc với nhau.

Như vậy ~cnt_x~ sẽ là lớn nhất nếu ta chọn điền miếng chữ L loại ~x~ có kích thước ~k~.

Chứng minh hoàn toàn tương tự, nhưng thay việc tìm giá trị nhỏ nhất bằng lớn nhất, ta có thể chứng minh được ~cnt_{x^{90}}~ là bé nhất khi chọn điền miếng chữ L loại ~x~ có kích thước ~k~.

Nếu như không có trường hợp dấu bằng, chứng minh 2 ý đầu của ta có thể dừng ở đây để suy ra biểu thức trong thuật toán. Để đảm bảo trường hợp dấu bằng cũng đúng, ta sẽ chứng minh ý cuối cùng là ~cnt_x - cnt_{x^{180}} \ne |cnt_{x^{90}} - cnt_{x^{270}}|~. Thật vậy, tổng ~cnt_{\texttt{TL}} + cnt_{\texttt{TR}} + cnt_{\texttt{BR}} + cnt_{\texttt{BL}} = \frac {4^k - 1} 3~ là một số lẻ, vì ~4^k~ có dạng ~6t + 4~ (hay ~4^k \equiv 4 \pmod 6~), do đó ~4^k - 1 = 6t + 3~, nên ~\frac{4^k - 1} 3 = \frac{6t + 3} 3 = 2t + 1~ là một số lẻ.

Vì tổng của 4 hạng tử là 1 số lẻ, nên hai vế của bất đẳng thức của ta cũng phải khác tính chẵn lẻ, do đó chúng khác nhau.

Như vậy khi ta điền miếng chữ L kích thước ~k~ với loại ~x~, ta thu được 3 điều kiện:

• ~cnt_x~ là lớn nhất trong số các phần tử của bộ số ~cnt~..
• ~cnt_{x^{180}}~ là nhỏ nhất trong số các phần tử của bộ số ~cnt~..
• ~cnt_x - cnt_{x^{180}} \ne |cnt_{x^{90}} - cnt_{x^{270}}|~.

Và từ đây có thể dễ dàng suy ra ~cnt_x - cnt_{x^{180}} > |cnt_{x^{90}} - cnt_{x^{270}}|~. Và hệ quả suy ra được là điều kiện này chỉ tồn tại với một ~P_{type}~ duy nhất, tương ứng với chính ~P_{type}~ của miếng chữ L kích thước ~k~ cần điền.

Chứng minh chiều xuôi

Nếu như tồn tại ~x~ thỏa mãn bất đẳng thức ~cnt_x - cnt_{x^{180}} > |cnt_{x^{90}} - cnt_{x^{270}}|~, nhưng miếng chữ L kích thước ~k~ cần điền lại không phải là loại ~x~, mà là loại ~y \ne x~, vậy điều kiện thu được phải là điều kiện đối với loại ~y~ chứ không phải là ~x~. Như ta đã chứng minh ở phần đảo, điều kiện này chỉ tồn tại với một ~P_{type}~ duy nhất, suy ra điều giả sử là vô lý.

Trong trường hợp không tìm thấy ~P_{type}~ nào thỏa mãn bất đẳng thức, ta có thể kết luận không có cách xếp nào thỏa mãn điều kiện đề bài, bởi vì với một cách xếp đúng, giá trị ~x~ vẫn phải tồn tại, cũng theo chứng minh chiều đảo ở trên.

Code mẫu

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

using ll = long long;
using Config = array<ll, 4>;
enum PieceType { TL, TR, BR, BL };

Config operator-(Config u, const Config& v) {
    for (int i = 0; i < 4; ++i) {
        u[i] -= v[i];
    }
    return u;
}

Config build_L_piece(PieceType type, int size) {
    Config ans;
    if (size == 1) {
        ans = {1, 0, 0, 0};
    } else {
        size -= 2;
        ll pw2 = 1ll << size;
        ll pw4 = pw2 << size;
        ans = {pw4 + pw2, pw4, pw4 - pw2, pw4};
    }
    rotate(ans.rbegin(), ans.rbegin() + type, ans.rend());
    return ans;
}

bool find_ans(int& r, int& c, int k, Config conf) {
    if (k == 0) {
        for (int i = 0; i < 4; ++i) if (conf[i]) return false;
        return true;
    }

    if (*min_element(conf.begin(), conf.end()) < 0) return false;
    PieceType big_piece;
    for (auto x: {TL, TR, BR, BL}) {
        auto x180 = (PieceType)(x ^ 2);
        // these 2 below might not be x90 and x270, but their roles might be swapped
        // but that is not important nontheless
        auto x90 = (PieceType)(x ^ 1);
        auto x270 = (PieceType)(x ^ 3);
        if (conf[x] - conf[x180] > abs(conf[x90] - conf[x270])) {
            big_piece = x;
            break;
        }
    }
    int half = 1 << (k - 1);
    if (big_piece == BL or big_piece == BR) r += half;
    if (big_piece == TR or big_piece == BR) c += half;
    return find_ans(r, c, k - 1, conf - build_L_piece(big_piece, k));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int ntest;
    cin >> ntest;
    while (ntest--) {
        int k;
        cin >> k;
        Config conf;
        for (int i = 0; i < 4; ++i) cin >> conf[i];
        ll sum = conf[0] + conf[1] + conf[2] + conf[3];
        if (sum != ((1ll << k << k) - 1) / 3) {
            cout << "-1\n";
            continue;
        }
        int ans_r = 0, ans_c = 0;
        if (find_ans(ans_r, ans_c, k, conf)) {
            cout << ans_r << ' ' << ans_c << '\n';
        } else {
            cout << "-1\n";
        }
    }

    return 0;
}

Bonus

Để giải thích test ví dụ, cũng như có thêm góc nhìn về bài toán và có thể debug dễ dàng hơn, tác giả đã tạo ra một tool vẽ hình. Các bạn có thể xem source code và thao tác trực tiếp tại đây.