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.
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 , trong khi vét cạn mọi cấu hình tốn hay 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ố ), hoặc giới hạn số thao tác kiểu "dùng không quá 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:
- 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.
- Khi tồn tại, xây thế nào? Cần một mẫu (pattern) chạy được cho mọi 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 chẵn mà cách xây chỉ chạy với lẻ, thì đ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 nhỏ | Luôn luôn, bước đầu tiên | Với , đáp án trông thế nào? 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ừ hoặc lên ) | Đáp án cho "chứa" đáp án cho 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 được không? |
| Tham lam có chứng minh | Cần đạt đúng một giá trị | Đặ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á thao tác", "không quá " | 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á phép" gợi ý mỗi phép cố định một phần tử; "không quá " 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ị của sao cho các hiệu đôi một khác nhau.
Có hiệu, mỗi hiệu nằm trong , nên chúng phải là đúng . Hiệu chỉ có được từ cặp . Vậy đặt cạnh ; hiệu có thể lấy từ ; hiệu từ ... 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 : sau mỗi bước khoảng 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 : 1 5 2 4 3, hiệu . 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 vào bảng sao cho hai ô chung cạnh không chứa hai số hơn kém nhau đúng .
Bước 1: thử tay nhỏ. hiển nhiên được. : mỗi ô có đúng 2 ô kề và 1 ô chéo. Số không được kề với và , nên cả 2 ô kề của nó phải chứa số . Chỉ có một số , mâu thuẫn. Vậy in -1.
Bước 2: tìm mẫu. Hai số hơn kém 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 :
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 là số số lẻ. Ô thứ (đếm từ theo thứ tự đọc) chứa nếu , chứa nếu .
- Kề ngang cùng vùng: hiệu . Kề ngang qua ranh giới: số lẻ cuối là hoặc (ít nhất khi ) nằm cạnh số , hiệu .
- Kề dọc cùng vùng: hiệu . Kề dọc qua ranh giới: ô (lẻ) trên ô (chẵn), hiệu . Hiệu này bằng chỉ khi , tức . Với thì , 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 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 trên vòng tròn sao cho tổng của mọi số liên tiếp (có tổng như vậy) chênh nhau không quá . In NO nếu không được.
Thử tay / vét cạn: chạy vét cạn với cho kết quả: có đáp án, không. Giả thuyết: có đáp án khi và chỉ khi lẻ.
Chứng minh chẵn thì NO. Gọi (chỉ số vòng theo mod ) và .
- Các số đôi một khác nhau nên . Mọi thuộc nên , và phải đan dấu (hai lần liên tiếp sẽ cho chênh lệch ). Suy ra .
- Mặt khác .
Ghép lại: , nên phải lẻ. Lập luận này còn cho thêm thông tin: , 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 lẻ. Ghép cặp ; cặp thứ đặt ở hai vị trí đối diện và . Số nhỏ của cặp nằm ở nửa đầu nếu lẻ, ở nửa sau nếu 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ừ sang , ta bỏ và thêm là "bạn cặp" của nó. Với , khi lẻ, khi chẵn, tức đan dấu. Với , ; vì lẻ nên và , 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 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
Cài đặt
#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' : ' ');
}
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 |
YES1 4 5 2 3 6 |
4 |
NO |
5 |
YES1 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 số nguyên dương phân biệt ; xóa lần lượt từng cặp , mỗi cặp cho điểm. Cần tổng điểm đúng bằng .
Cận dưới. Có cặp, mỗi , nên tổng . Nếu thì in -1. Trường hợp riêng : không có cặp nào, chỉ được khi .
Xây khi (tham lam dồn dư). Cho cặp sau ở mức tối thiểu (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 , cặp đầu là với . Các số còn lại là liên tiếp, nên phân biệt, lớn hơn và mọi cặp sau có .
| Dãy | Điểm | |||
|---|---|---|---|---|
1 2 3 4 5 |
||||
2 4 5 6 7 |
||||
-1 |
tổng |
Kiểm tra giới hạn giá trị: , nên số lớn nhất . 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ị đỉnh có thành phần liên thông, đồ thị bù có thành phần.
- Định lý đã biết: nếu 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 và cùng lúc là
NO. - Đối xứng: đổi vai và phần bù thì thành . Chỉ cần giải , trường hợp thì xây cho rồi lấy bù.
- Xây , : đỉnh cô lập, đỉnh còn lại nối thành một đường. không liên thông nên phần bù tự động liên thông.
- Trường hợp : vét cạn nhỏ cho thấy là
NO(: có cạnh thì bù rời rạc, không có thì rời rạc; tương tự cho mọi đồ thị). Với và , đường đi 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 với là ví dụ điển hình của ngoại lệ chỉ lộ ra khi thử 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ứ:
- 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 đề.
- Vét cạn: với 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
NOsai.
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 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 , 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: thời gian, bộ nhớ cho mảng kết quả (có thể in thẳng để còn ). Bài notadj: , đúng bằng số ô phải in.
- Checker: thường đến , đủ nhanh để chạy cả trên test lớn. Checker của almeq là nhờ trượt cửa sổ thay vì tính lại từng tổng ().
- Vét cạn: với almeq, chỉ dùng được tới . Đó 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 (, ). Triệu chứng: WA ở test hoặc . Cách tránh: luôn chạy checker với mọi từ đến khoảng .
- In
-1khi đá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 nhỏ; mỗi lần in-1phả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", "", "đồ thị không có cạnh lặp", "không quá 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ụ hay vượt
int. Cách tránh: ước lượng giá trị lớn nhất trước khi cài, dùnglong longkhi 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 inYEStrước đáp án. Đọc kỹ mục dữ liệu ra. - Output quá chậm. Đáp án có thể tới số; in bằng
cout << endltừng dòng sẽ TLE. Dùng'\n',printf, hoặc gom chuỗi rồi in một lần (Python:print(*arr)haysys.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ề 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 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 từ các khối , 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
NOvà 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 ; 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ệ .
Bình luận