Wiki › Thuật toán › Bài toán kiến thiết (Constructive Algorithms)

Bài toán kiến thiết (Constructive Algorithms)

Cách tiếp cận bài toán "xây một đáp án bất kỳ hoặc in -1": thử trường hợp nhỏ, bất biến và chẵn lẻ, quy nạp, mẫu đối xứng, tham lam, quy về cấu trúc đã biết, và kiểm chứng bằng checker.

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 18 phút 3 lượt xem

Bài toán kiến thiết (constructive) là dạng bài yêu cầu xây dựng một đáp án bất kỳ thỏa mãn điều kiện (một hoán vị, một ma trận, một đồ thị, một dãy thao tác...), hoặc in -1 / NO nếu không tồn tại. Không có "thuật toán chuẩn" để học thuộc: thứ cần luyện là quy trình tìm ra cấu trúc. Đổi lại, lời giải thường chỉ là một công thức hoặc một vòng lặp O(N), trong khi vét cạn mọi cấu hình tốn O(N!) hay O(2N2) và không bao giờ qua được giới hạn.

Đặc điểm nhận dạng: đề có câu "nếu có nhiều đáp án, in ra bất kỳ", ràng buộc lớn nhưng input rất ít (thường chỉ một số n), hoặc giới hạn số thao tác kiểu "dùng không quá n phép".

Ý tưởng / Trực giác

Vì được in bất kỳ đáp án nào, ta có quyền chọn một đáp án có cấu trúc đẹp để dễ chứng minh và dễ cài, thay vì tìm "đáp án tốt nhất". Bài toán thực chất gồm hai nửa độc lập:

  1. Khi nào không tồn tại? Cần một lập luận chặt (bất biến, chẵn lẻ, đếm, cận) chứng minh mọi cấu hình đều vi phạm.
  2. Khi tồn tại, xây thế nào? Cần một mẫu (pattern) chạy được cho mọi n thuộc trường hợp còn lại.

Hai nửa phải khớp nhau: tập "in -1" và tập "xây được" phải phủ kín mọi input. Nếu lập luận bất khả chỉ loại n chẵn mà cách xây chỉ chạy với n≥5 lẻ, thì n=1,3 đang bị bỏ ngỏ.

Bộ công cụ thường dùng, theo thứ tự nên thử:

Kỹ thuật Khi nào nghĩ tới Câu hỏi tự đặt
Thử tay / vét cạn n nhỏ Luôn luôn, bước đầu tiên Với n=1..6, đáp án trông thế nào? n nào in -1?
Bất biến, chẵn lẻ, đếm Có trường hợp -1 Đại lượng nào không đổi qua mọi thao tác? Tổng/chẵn lẻ có buộc điều gì không?
Quy nạp (từ n−1 hoặc n−2 lên n) Đáp án cho n "chứa" đáp án cho n nhỏ hơn Thêm 1 hoặc 2 phần tử vào đáp án cũ có giữ được điều kiện?
Mẫu đối xứng / tuần hoàn Điều kiện "đều", lặp lại theo vị trí Có xếp xen kẽ, zig-zag, theo chẵn lẻ, theo imodk được không?
Tham lam có chứng minh Cần đạt đúng một giá trị k Đặt phần lớn "ở mức tối thiểu", dồn phần dư vào một chỗ?
Quy về cấu trúc đã biết Đề nói về đồ thị, hoán vị, tô màu Đây có phải chu trình Euler, đồ thị hai phía, cây khung, chu trình hoán vị?
Đọc cận trong đề "Không quá n thao tác", "không quá 2n" Mỗi phần tử được một thao tác? Mỗi bước sửa xong một vị trí?

Câu cuối rất quan trọng: giới hạn đề cho thường tiết lộ lời giải. "Không quá n phép" gợi ý mỗi phép cố định một phần tử; "không quá ⌈n/2⌉" gợi ý mỗi phép xử lý một cặp; "đổi không quá 9 ô của Sudoku" gợi ý mỗi hàng (cột, khối) đổi đúng một ô.

Ví dụ 1: mẫu zig-zag

Đề: xây hoán vị p của 1..n sao cho các hiệu |p1−p2|,|p2−p3|,…,|pn−1−pn| đôi một khác nhau.

Có n−1 hiệu, mỗi hiệu nằm trong [1,n−1], nên chúng phải là đúng {1,2,…,n−1}. Hiệu n−1 chỉ có được từ cặp (1,n). Vậy đặt 1 cạnh n; hiệu n−2 có thể lấy từ (n,2); hiệu n−3 từ (2,n−1)... Ta đi xen kẽ hai đầu: lấy nhỏ nhất, lớn nhất, nhỏ nhì, lớn nhì...

array
6
1 6 2 5 3 4
step Lấy xen kẽ: nhỏ nhất, lớn nhất, nhỏ nhì, lớn nhì...
highlight green 1 3 5
highlight orange 2 4 6
step Các hiệu lần lượt là 5, 4, 3, 2, 1: giảm dần đúng 1 mỗi bước
label 1 5
label 2 4
label 3 3
label 4 2
label 5 1

Vì sao đúng với mọi n: sau mỗi bước khoảng [lo,hi] còn lại co lại đúng 1 đơn vị, nên hiệu tiếp theo nhỏ hơn hiệu trước đúng 1. Với n=5: 1 5 2 4 3, hiệu 4,3,2,1. Không có trường hợp -1.

Bài học: lập luận "phần tử cực trị bị ép" (hiệu lớn nhất chỉ có một cách tạo) thường chỉ thẳng ra cách xây.

Ví dụ 2: trường hợp nhỏ và chẵn lẻ

Đề (notadj): điền 1..n2 vào bảng n×n sao cho hai ô chung cạnh không chứa hai số hơn kém nhau đúng 1.

Bước 1: thử tay n nhỏ. n=1 hiển nhiên được. n=2: mỗi ô có đúng 2 ô kề và 1 ô chéo. Số 2 không được kề với 1 và 3, nên cả 2 ô kề của nó phải chứa số 4. Chỉ có một số 4, mâu thuẫn. Vậy n=2 in -1.

Bước 2: tìm mẫu. Hai số hơn kém 1 luôn khác chẵn lẻ. Nếu xếp mọi số lẻ trước rồi mọi số chẵn (theo thứ tự đọc từng hàng), hai ô kề nhau phần lớn cùng chẵn lẻ nên hiệu là số chẵn, không thể bằng 1:

grid
1 3 5
7 9 2
4 6 8
step n = 3: điền số lẻ trước (xanh), số chẵn sau (cam)
highlight green 1,1..1,3 2,1 2,2
highlight orange 2,3 3,1..3,3
step Chỉ những cặp ở ranh giới lẻ/chẵn mới khác chẵn lẻ
highlight red 1,3 2,1 2,2 2,3 3,1 3,2

Bước 3: kiểm tra ranh giới. Gọi m=⌈n2/2⌉ là số số lẻ. Ô thứ k (đếm từ 0 theo thứ tự đọc) chứa 2k+1 nếu k<m, chứa 2(k−m)+2 nếu k≥m.

  • Kề ngang cùng vùng: hiệu 2. Kề ngang qua ranh giới: số lẻ cuối là n2 hoặc n2−1 (ít nhất 8 khi n≥3) nằm cạnh số 2, hiệu ≥6.
  • Kề dọc cùng vùng: hiệu 2n. Kề dọc qua ranh giới: ô k (lẻ) trên ô k+n (chẵn), hiệu =(2k+1)−(2(k+n−m)+2)=2m−2n−1. Hiệu này bằng ±1 chỉ khi m∈{n,n+1}, tức n≤2. Với n≥3 thì m≥n+2, an toàn.

Lưu ý kết quả "tình cờ" khớp: phép tính ở bước 3 cũng chỉ ra đúng n=2 là ngoại lệ, trùng với bước 1. Đây là dấu hiệu tốt cho thấy hai nửa (bất khả và xây dựng) phủ kín input.

Ví dụ 3: bất biến chứng minh NO (bài đại diện)

Đề (almeq): xếp 1..2n trên vòng tròn sao cho tổng của mọi n số liên tiếp (có 2n tổng như vậy) chênh nhau không quá 1. In NO nếu không được.

Thử tay / vét cạn: chạy vét cạn với n=1..5 cho kết quả: n=1,3,5 có đáp án, n=2,4 không. Giả thuyết: có đáp án khi và chỉ khi n lẻ.

Chứng minh n chẵn thì NO. Gọi Si=ai+ai+1+…+ai+n−1 (chỉ số vòng theo mod 2n) và di=Si+1−Si=ai+n−ai.

  • Các số đôi một khác nhau nên di≠0. Mọi Si thuộc {x,x+1} nên di=±1, và phải đan dấu +1,−1,+1,… (hai lần +1 liên tiếp sẽ cho chênh lệch 2). Suy ra di+n=(−1)ndi.
  • Mặt khác di+n=ai+2n−ai+n=ai−ai+n=−di.

Ghép lại: (−1)n=−1, nên n phải lẻ. Lập luận này còn cho thêm thông tin: |ai+n−ai|=1, tức hai vị trí đối diện chứa hai số liên tiếp. Đó chính là gợi ý để xây.

Cách xây khi n lẻ. Ghép cặp (1,2),(3,4),…,(2n−1,2n); cặp thứ i đặt ở hai vị trí đối diện i và i+n. Số nhỏ của cặp nằm ở nửa đầu nếu i lẻ, ở nửa sau nếu i chẵn:

array
6
1 4 5 2 3 6
step n = 3, cặp thứ i chiếm vị trí i và i + 3
highlight green 1 4
highlight orange 2 5
highlight purple 3 6
step Cặp 1 = (1,2): số nhỏ ở nửa đầu. Cặp 2 = (3,4): số nhỏ ở nửa sau. Cặp 3 = (5,6): nửa đầu
label 1 cặp 1
label 2 cặp 2
label 3 cặp 3
step Trượt cửa sổ: 1+4+5 = 10, 4+5+2 = 11, 5+2+3 = 10, 2+3+6 = 11, 3+6+1 = 10, 6+1+4 = 11
clear
highlight blue 1..3

Kiểm tra tại sao luôn đúng: khi trượt cửa sổ từ Si sang Si+1, ta bỏ ai và thêm ai+n là "bạn cặp" của nó. Với i=1..n, di=+1 khi i lẻ, −1 khi i chẵn, tức đan dấu. Với i=n+1..2n, di=−di−n; vì n lẻ nên dn=+1 và dn+1=−d1=−1, chuỗi tiếp tục đan dấu trọn vòng. Tổng chỉ dao động giữa hai giá trị kề nhau.

Với n=5 chương trình in 1 4 5 8 9 2 3 6 7 10, các tổng cửa sổ lần lượt 27,28,27,28,…

Cài đặt
C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    // Parity argument: a valid circle exists only when n is odd
    if (n % 2 == 0) {
        puts("NO");
        return 0;
    }
    vector<int> pos(2 * n);
    // Pair (2i-1, 2i) occupies opposite positions i and i+n,
    // the smaller number alternates between the two halves
    for (int i = 1; i <= n; i++) {
        int small = 2 * i - 1, big = 2 * i;
        if (i % 2 == 1) {
            pos[i - 1] = small;
            pos[i - 1 + n] = big;
        } else {
            pos[i - 1] = big;
            pos[i - 1 + n] = small;
        }
    }
    puts("YES");
    for (int i = 0; i < 2 * n; i++) printf("%d%c", pos[i], i + 1 == 2 * n ? '\n' : ' ');
}
Python
import sys


def main():
    n = int(sys.stdin.readline())
    # Parity argument: a valid circle exists only when n is odd
    if n % 2 == 0:
        print("NO")
        return
    pos = [0] * (2 * n)
    # Pair (2i-1, 2i) occupies opposite positions i and i+n,
    # the smaller number alternates between the two halves
    for i in range(1, n + 1):
        small, big = 2 * i - 1, 2 * i
        if i % 2 == 1:
            pos[i - 1], pos[i - 1 + n] = small, big
        else:
            pos[i - 1], pos[i - 1 + n] = big, small
    print("YES")
    print(*pos)


main()
Input Output
3 YES
1 4 5 2 3 6
4 NO
5 YES
1 4 5 8 9 2 3 6 7 10

Ví dụ 4: dùng cận và dồn phần dư

Đề (mashnum): chọn n số nguyên dương phân biệt ≤109; xóa lần lượt từng cặp (a1,a2),(a3,a4),…, mỗi cặp cho gcd điểm. Cần tổng điểm đúng bằng k.

Cận dưới. Có m=⌊n/2⌋ cặp, mỗi gcd≥1, nên tổng ≥m. Nếu k<m thì in -1. Trường hợp riêng n=1: không có cặp nào, chỉ được khi k=0.

Xây khi k≥m (tham lam dồn dư). Cho m−1 cặp sau ở mức tối thiểu gcd=1 (hai số liên tiếp luôn nguyên tố cùng nhau), dồn toàn bộ phần dư vào cặp đầu: đặt x=k−m+1, cặp đầu là (x,2x) với gcd=x. Các số còn lại là 2x+1,2x+2,… liên tiếp, nên phân biệt, lớn hơn 2x và mọi cặp sau có gcd=1.

n,k m x Dãy Điểm
5,2 2 1 1 2 3 4 5 1+1=2
5,3 2 2 2 4 5 6 7 2+1=3
7,2 3 -1 tổng ≥3>2

Kiểm tra giới hạn giá trị: k≤108, n≤105 nên số lớn nhất ≈2x+n≤2·108+105<109. Bước "kiểm tra số lớn nhất có vượt giới hạn đề không" là bắt buộc với mọi bài kiến thiết in số.

Ví dụ 5: quy về tính chất đã biết và đối xứng

Đề (graphcomp): xây đồ thị n đỉnh có a thành phần liên thông, đồ thị bù có b thành phần.

  • Định lý đã biết: nếu G không liên thông thì phần bù của nó liên thông (hai đỉnh khác thành phần thì kề nhau trong phần bù; hai đỉnh cùng thành phần cùng kề với một đỉnh ở thành phần khác). Vậy a>1 và b>1 cùng lúc là NO.
  • Đối xứng: đổi vai G và phần bù thì (a,b) thành (b,a). Chỉ cần giải b=1, trường hợp a=1,b>1 thì xây cho (b,1) rồi lấy bù.
  • Xây b=1, a≥2: a−1 đỉnh cô lập, n−a+1 đỉnh còn lại nối thành một đường. G không liên thông nên phần bù tự động liên thông.
  • Trường hợp a=b=1: vét cạn nhỏ cho thấy n=2,3 là NO (n=2: có cạnh thì bù rời rạc, không có thì G rời rạc; n=3 tương tự cho mọi đồ thị). Với n=1 và n≥4, đường đi 1−2−…−n có phần bù liên thông.
graph
4
1 2
2 3
3 4
step Đường đi P4 (a = 1)
highlight blue 1-2 2-3 3-4
step Phần bù của P4: cạnh 1-3, 1-4, 2-4, vẫn liên thông (b = 1)
clear
highlight orange 1 2 3 4
label 1 bù: 1-3, 1-4
label 2 bù: 2-4

Trường hợp a=b=1 với n=2,3 là ví dụ điển hình của ngoại lệ chỉ lộ ra khi thử n nhỏ: lập luận tổng quát không cấm nó, nhưng cách xây tổng quát cũng không chạy được.

Kiểm chứng: checker và vét cạn

Bài kiến thiết có nhiều đáp án đúng nên không thể so output với một file đáp án. Thay vào đó viết hai thứ:

  1. Checker: nhận input và output của bạn, kiểm tra trực tiếp mọi điều kiện của đề.
  2. Vét cạn: với n nhỏ, thử mọi cấu hình để biết có tồn tại đáp án hay không. Dùng nó để bắt lỗi in NO sai.

Ví dụ cho bài almeq (chương trình C++ ở trên biên dịch thành ./almeq):

import subprocess
from itertools import permutations


def valid(n, circle):
    # Checker: correct multiset, and every window of n numbers differs by <= 1
    if sorted(circle) != list(range(1, 2 * n + 1)):
        return False
    s = sum(circle[:n])
    sums = [s]
    for i in range(2 * n - 1):
        s += circle[(i + n) % (2 * n)] - circle[i]   # slide the window by one
        sums.append(s)
    return max(sums) - min(sums) <= 1


def brute_exists(n):
    # Brute force: fix 1 at the first position (rotations are equivalent)
    return any(valid(n, [1, *rest]) for rest in permutations(range(2, 2 * n + 1)))


for n in range(1, 6):
    out = subprocess.run(["./almeq"], input=f"{n}\n",
                         capture_output=True, text=True).stdout.split()
    exists = brute_exists(n)
    if out[0] == "NO":
        assert not exists, f"n={n}: printed NO but an answer exists"
    else:
        assert valid(n, list(map(int, out[1:]))), f"n={n}: invalid answer"
    print(n, out[0], "OK")

Output:

1 YES OK
2 NO OK
3 YES OK
4 NO OK
5 YES OK

Vét cạn còn dùng trước khi có lời giải: in ra mọi đáp án cho n=1..6 rồi nhìn để đoán mẫu. Xem thêm Kỹ thuật debug về stress test.

Độ phức tạp

  • Lời giải: thường O(kích thước output), vì mỗi phần tử của đáp án được tính bằng công thức trực tiếp. Bài almeq: O(n) thời gian, O(n) bộ nhớ cho mảng kết quả (có thể in thẳng để còn O(1)). Bài notadj: O(n2), đúng bằng số ô phải in.
  • Checker: thường O(output) đến O(output·log), đủ nhanh để chạy cả trên test lớn. Checker của almeq là O(n) nhờ trượt cửa sổ thay vì tính lại từng tổng (O(n2)).
  • Vét cạn: O((2n−1)!·n) với almeq, chỉ dùng được tới n≈5. Đó là lý do phải tìm ra cấu trúc chứ không thể vét cạn trên test thật.

⚠️ Lỗi thường gặp

  • Bỏ sót trường hợp nhỏ. Mẫu tổng quát thường chỉ đúng từ một ngưỡng (n≥3, n≥4). Triệu chứng: WA ở test n=1 hoặc n=2. Cách tránh: luôn chạy checker với mọi n từ 1 đến khoảng 10.
  • In -1 khi đáp án vẫn tồn tại. Lập luận bất khả "có vẻ đúng" nhưng thiếu chặt. Cách tránh: so với vét cạn trên n nhỏ; mỗi lần in -1 phải chỉ ra được bất biến hay phép đếm cụ thể.
  • Đáp án vi phạm ràng buộc phụ. Quên điều kiện "phân biệt", "≤109", "đồ thị không có cạnh lặp", "không quá n thao tác". Triệu chứng: WA dù ý tưởng đúng. Cách tránh: checker phải kiểm tra toàn bộ điều kiện trong đề, không chỉ điều kiện chính.
  • Tràn số khi giá trị xây ra lớn. Ví dụ 2x hay n2 vượt int. Cách tránh: ước lượng giá trị lớn nhất trước khi cài, dùng long long khi cần.
  • Sai định dạng YES/NO/-1. Mỗi bài yêu cầu một kiểu (NO, -1, Impossible), có bài còn cần in YES trước đáp án. Đọc kỹ mục dữ liệu ra.
  • Output quá chậm. Đáp án có thể tới 106 số; in bằng cout << endl từng dòng sẽ TLE. Dùng '\n', printf, hoặc gom chuỗi rồi in một lần (Python: print(*arr) hay sys.stdout.write).
  • Mất thời gian tìm "đáp án tối ưu". Đề chỉ cần một đáp án hợp lệ; theo đuổi đáp án đẹp nhất làm bài khó hơn mức cần.

Biến thể / Mở rộng

  • Kiến thiết bằng thao tác (sắp xếp bằng phép đổi chỗ, đưa bảng về 0 bằng phép lật): thường dùng quy nạp "mỗi bước cố định một phần tử" để đảm bảo cận số thao tác. Liên hệ chu trình hoán vị khi cần đúng số phép đổi chỗ tối thiểu.
  • Kiến thiết đồ thị/cây: xây đồ thị có đúng khoảng cách, bậc hay số thành phần cho trước; công cụ là cây BFS theo tầng, đồ thị hai phía, chu trình Euler. Xem Thuật toán đồ thị và Đường đi Euler.
  • Kiến thiết bằng tham lam: xây từng vị trí, mỗi bước chọn giá trị "an toàn" và chứng minh luôn còn lựa chọn cho phần còn lại. Xem Tham lam.
  • Khi không tìm ra mẫu: dùng Quay lui sinh đáp án cho n nhỏ để quan sát, hoặc ghép các khối nhỏ tìm bằng vét cạn (ví dụ xây bảng n×m từ các khối 2×3, 3×3 tìm sẵn).
  • Bài tương tác và bài "hack": xây input làm một thuật toán sai chạy chậm hoặc ra kết quả sai, cùng tư duy kiến thiết nhưng đối tượng xây là test.

Quy trình chung khi gặp bài mới được tóm tắt ở Tiếp cận bài toán.

Bài tập luyện

  • Sắp xếp z (zsort) (Nghiệp dư): hoán vị dãy thành dạng lên xuống xen kẽ; sắp xếp rồi đặt nửa lớn vào vị trí chẵn là một mẫu xen kẽ đơn giản.
  • Ma trận không kề (notadj) (Nghiệp dư): ví dụ 2 ở trên, luyện thử tay trường hợp nhỏ và mẫu theo chẵn lẻ.
  • Anti-Sudoku (antisudoku) (Trung cấp): đổi không quá 9 ô để mọi hàng, cột, khối có số lặp; cận "9 ô" gợi ý ngay mỗi hàng đổi đúng một ô.
  • Gần bằng nhau (almeq) (Trung cấp): bài đại diện ở trên, lập luận chẵn lẻ chứng minh NO và cách xây ghép cặp đối diện.
  • Mashmokh và những con số (mashnum) (Nâng cao): tổng gcd đúng bằng k; dùng cận dưới để loại và dồn phần dư vào một cặp.
  • Đồ thị và phần bù (graphcomp) (Nâng cao): số thành phần liên thông của đồ thị và phần bù; quy về định lý đã biết, dùng đối xứng và xử lý ngoại lệ n=2,3.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0