Bản đồ (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng C1)

Nguồn: Tin học trẻ toàn quốc 2025 Độ khó: Khó Bài tối ưu Heuristic

Đề bài

Các nhà khảo cổ tìm được $n$ mảnh bản đồ cổ. Mảnh thứ $k$ ($1 \le k \le n$) là một hình chữ nhật $a_k \times b_k$ ô vuông ($a_k$ dòng, $b_k$ cột), mỗi ô được tô một trong bốn màu $0, 1, 2, 3$ (thể hiện độ cao). Họ tin rằng mọi mảnh đều thuộc về một bản đồ lớn duy nhất, nhưng không biết vị trí của từng mảnh; chỉ biết mỗi mảnh nằm trọn bên trong bản đồ lớn và chiếm trọn các ô.

Hãy dựng một bản đồ hình chữ nhật có diện tích nhỏ nhất sao cho mỗi mảnh đều xuất hiện nguyên vẹn tại một vị trí nào đó (giữ nguyên kích thước, không xoay). Các mảnh được phép chồng lên nhau nếu màu ở các ô chung trùng khớp.

Dữ liệu vào:

• Dòng đầu: số nguyên $n$ ($n \le 100$).
• Tiếp theo là $n$ nhóm dòng, mỗi nhóm mô tả một mảnh: dòng đầu gồm hai số nguyên dương $a_k, b_k$ ($a_k, b_k \le 10$), tiếp theo $a_k$ dòng, mỗi dòng $b_k$ số (từ 0 đến 3).

Kết quả: dòng đầu hai số nguyên $r, c$ – kích thước bản đồ dựng được; tiếp theo $r$ dòng, mỗi dòng $c$ số (từ 0 đến 3).

Chấm điểm: với mỗi test, gọi $s = r \times c$ là số ô bản đồ của em, $d$ là kết quả của Ban giám khảo:

• nếu $s - d \le 100$: em nhận $0{,}95^{\max(0,\, s - d)}$ số điểm của test;
• ngược lại: 0 điểm. Bản đồ không hợp lệ (có mảnh không xuất hiện nguyên vẹn) cũng 0 điểm.

Subtask: Subtask 1 (20%): mọi mảnh có $a_k = 1$. Subtask 2 (40%): mọi mảnh có $a_k \le 2$. Subtask 3 (40%): không có ràng buộc gì thêm.

Giới hạn thời gian: 0,1 giây. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ – input

2
2 3
0 0 1
0 1 2
3 1
2
1
2

Ví dụ – output

3 3
0 0 2
0 0 1
0 1 2

Giải thích: mảnh thứ nhất ($2 \times 3$) nằm ở hai dòng cuối; mảnh thứ hai ($3 \times 1$, các màu 2, 1, 2) là cột cuối cùng – chồng lên mảnh 1 ở hai ô màu 1 và 2. Bản đồ có diện tích 9. Ô ở góc trên bên trái không thuộc mảnh nào, tô màu gì cũng được.

·	·	2
0	0	1
0	1	2

mảnh 1 (2×3)
mảnh 2 (3×1)
ô chung (khớp màu)
· ô không thuộc mảnh nào

Lưu ý: đây là bài tối ưu – không có "đáp án đúng duy nhất", trình chấm (checker) kiểm tra mọi mảnh có xuất hiện không rồi cho điểm theo diện tích. Trên CLUE, $d$ là diện tích trong file đáp án của bộ test (do lời giải của mình tạo ra), nên có test em còn làm tốt hơn $d$ được (vẫn nhận đủ điểm).

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng C1. Đề được mình viết lại cho dễ đọc, giữ nguyên ý và số liệu.

Lời mở đầu

Đây là bài "khác thường" nhất của cả kỳ thi: một bài tối ưu (NP-khó – không ai biết thuật toán nhanh cho đáp án tốt nhất). Điểm của em phụ thuộc vào việc bản đồ dựng được gần kết quả của Ban giám khảo tới đâu. Vì vậy lời giải không còn là "đúng/sai" mà là: nghĩ ra những ý tham lam hợp lý, rồi tận dụng hết 0,1 giây để thử thật nhiều phương án. Mình trình bày 3 mức: từ một dòng xếp ngây thơ (luôn hợp lệ) tới lời giải mình đã nộp lên tinhoctre.vn được 99,676/100.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngghép + xếpCách 11 hàngCách 2tham lamCách 3đã nộpTổng kếtđiểm

Bộ testBộ test có gì?

Bộ test của mình gồm 20 test, chia theo tỉ lệ subtask: test 1–4 (mọi $a_k = 1$), 5–12 ($a_k \le 2$), 13–20 (tổng quát; test 13 là ví dụ của đề). Phần lớn test được sinh đúng như câu chuyện của đề: tạo một bản đồ ẩn ngẫu nhiên rồi cắt ra $n$ mảnh ở vị trí ngẫu nhiên; một số test khác là các mảnh ngẫu nhiên độc lập (gần như không chồng được), test chỉ 2 màu (dễ "khớp nhầm").

Test	Subtask	$n$	$a$, $b$ lớn nhất	Số màu	Tổng ô các mảnh	Bản đồ ẩn (lúc sinh)	$d$ của file đáp án
1	1	100	1, 10	4	587	8×30 = 240	1×169 = 169
2	1	100	1, 10	4	771	3×120 = 360	1×288 = 288
3	1	100	1, 10	4	528	mảnh ngẫu nhiên	1×287 = 287
4	1	100	1, 10	2	561	mảnh ngẫu nhiên	1×133 = 133
5	2	100	2, 10	4	733	10×40 = 400	4×85 = 340
6	2	100	2, 10	4	1.134	4×100 = 400	4×102 = 408
7	2	100	2, 10	4	777	mảnh ngẫu nhiên	2×270 = 540
8	2	60	2, 10	2	515	mảnh ngẫu nhiên	3×86 = 258
9	2	100	2, 10	3	884	20×20 = 400	3×114 = 342
10	2	100	2, 10	4	2.000	mảnh ngẫu nhiên	6×299 = 1.794
11	2	30	2, 10	4	283	6×30 = 180	6×27 = 162
12	2	1	1, 1	1	1	1×1 = 1	1×1 = 1
13	3	2	3, 3	3	9	3×3 = 9 (ví dụ)	3×3 = 9
14	3	100	10, 10	4	2.812	30×30 = 900	29×29 = 841
15	3	100	10, 10	4	5.768	20×40 = 800	20×40 = 800
16	3	100	10, 10	4	2.863	mảnh ngẫu nhiên	12×235 = 2.820
17	3	100	10, 10	4	10.000	mảnh ngẫu nhiên	10×1000 = 10.000
18	3	100	10, 10	2	3.518	50×50 = 2500	45×47 = 2.115
19	3	100	10, 10	2	2.984	mảnh ngẫu nhiên	65×43 = 2.795
20	3	70	10, 10	4	2.209	15×15 = 225	15×15 = 225

• Cột "bản đồ ẩn" là kích thước bản đồ dùng khi sinh test – một cận trên của đáp án tối ưu. Lời giải tốt còn tìm được bản đồ nhỏ hơn bản đồ ẩn (ví dụ test 1: 169 < 240), vì không phải ô nào của bản đồ ẩn cũng bị mảnh nào đó phủ.
• Cột $d$ là diện tích trong file đáp án – chính là kết quả của lời giải cách 3 (một lần chạy). Trình chấm CLUE so với $d$ này.

Điểm (theo công thức $0{,}95^{\max(0, s - d)}$, chấm bằng checker) của các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1	Cách 2	Cách 3 (TB 5 lần)
Subtask 1 (20%)	mọi $a_k = 1$	1–4	0,00	0,07	20,00
Subtask 2 (40%)	mọi $a_k \le 2$	5–12	5,00	6,49	39,28
Subtask 3 (40%)	không ràng buộc thêm	13–20	9,29	26,45	37,65
Tổng		1–20	14,29	33,01	96,93

Ý tưởngGhép mảnh như ghép tranh, rồi xếp khối vào dải

Có hai nguồn "tiết kiệm" diện tích:

1. Chồng các mảnh lên nhau. Nếu hai mảnh có một phần chung khớp màu đủ lớn (ví dụ 8 ô khớp với 4 màu – xác suất trùng ngẫu nhiên chỉ $(1/4)^8 \approx 0{,}000015$), gần như chắc chắn chúng cạnh nhau trên bản đồ thật → ghép lại thành một khối. Duyệt các cặp theo số ô chồng giảm dần (giống thuật toán Kruskal), mỗi lần ghép hai khối nếu toàn bộ phần chung của chúng khớp.
2. Xếp các khối thật khít. Cố định chiều cao $H$ của bản đồ, xếp từng khối vào vị trí "trái nhất, rồi trên nhất" còn đặt được (khối có thể chồng lên ô đã có nếu khớp màu). Thử nhiều $H$, giữ phương án diện tích $H \times W$ nhỏ nhất.

Ngưỡng "đủ lớn" $T$ rất quan trọng: nhỏ quá thì ghép nhầm (hai mảnh tình cờ khớp vài ô) làm khối to và lệch, lớn quá thì bỏ lỡ nhiều cách ghép đúng. Gọi $q = \sum_c (\text{tỉ lệ màu } c)^2$ là xác suất hai ô ngẫu nhiên trùng màu, và có tổng cộng "số lần thử" cách đặt chồng; chọn $T$ sao cho $q^T \cdot \text{số lần thử} < 1$, tức $T = \left\lceil \dfrac{\ln(\text{số lần thử})}{-\ln q} \right\rceil$.

Em sửa các mảnh, chọn ngưỡng $T$ rồi bấm Tiếp để xem quá trình ghép và xếp (ô kẻ sọc là ô chưa biết màu):

Các mảnh (như dữ liệu vào): 2 2 3 0 0 1 0 1 2 3 1 2 1 2Ngưỡng T =

Ví dụ nhanh:

Cách 1Xếp mọi mảnh thành một hàng

Cách "an toàn" nhất: đặt các mảnh cạnh nhau thành một hàng, không chồng lên nhau. Bản đồ cao $\max a_k$, rộng $\sum b_k$; ô thừa tô màu 0. Luôn hợp lệ!

C++▶ Chạy tay từng dòng codeCách 1: xếp mọi mảnh thành một hàng, không chồng.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 0 0 1 0 1 2 3 1 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(\sum a_k b_k)$

Thời gian$O(\max a \cdot \sum b)$

Kết quả chạy thật: được 14,29/100 điểm (bản Python 14,29). Hầu hết các test bị 0 điểm vì $s - d > 100$; chỉ ăn điểm test 1 mảnh, ví dụ (12 ô so với 9 → $0{,}95^3 \approx 0{,}86$) và test 17 (100 mảnh $10 \times 10$ ngẫu nhiên, không chồng được nên xếp thẳng hàng đã là tốt nhất).

Cách 2Ghép chắc chắn + xếp vào dải cao H

Cài đặt đúng hai ý ở phần ý tưởng với một bộ tham số duy nhất:

1. Bỏ các mảnh giống hệt nhau. Với mọi cặp mảnh $(i, j)$ và mọi độ lệch $(dy, dx)$ để chúng giao nhau, nếu phần giao khớp màu thì lưu "cạnh" (số ô chồng, $i$, $j$, $dy$, $dx$).
2. Duyệt các cạnh theo số ô chồng giảm dần, ghép hai khối khi phần chung của hai khối (không chỉ hai mảnh) khớp, và (số ô chồng $\ge T$ hoặc ghép xong hình bao không lớn hơn khối lớn). Mảng off lưu vị trí của mỗi mảnh trong khối của nó, để quy đổi độ lệch giữa hai mảnh thành độ lệch giữa hai khối.
3. Thử $H$ từ chiều cao khối lớn nhất trở lên, xếp first-fit, giữ diện tích nhỏ nhất. Cắt tỉa: nếu $H \times \max w \ge$ kết quả tốt nhất thì dừng; nếu cận dưới $H \cdot \lceil \text{số ô đã biết} / H \rceil$ không tốt hơn thì bỏ qua $H$ đó.

C++▶ Chạy tay từng dòng codeCách 2: ghép kiểu Kruskal với ngưỡng T rồi thử các chiều cao H, xếp first-fit.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 0 0 1 0 1 2 3 1 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hàm overlap, mergeBlock, pack được tính gọn trong một bước (hình bên phải cho thấy kết quả).

Không gian$O(n^2 \cdot 4ab)$ cạnh

Thời gian$O(n^2 \cdot 4ab \cdot ab)$ + xếp dải

Kết quả chạy thật: được 33,01/100 điểm, lâu nhất 0,07 giây. Cách này tốt ở các test "bản đồ ẩn" nhiều chồng lấn (test 15, 20 đạt đúng $d$) và đặc biệt tốt ở test ngẫu nhiên 2 màu (test 18 còn được bản đồ nhỏ hơn $d$), nhưng ở subtask 1, 2 (mảnh mỏng, mỗi cặp chỉ chồng được ít ô) ngưỡng $T$ quá "khó tính" nên gần như không ghép được gì → thừa hơn 100 ô → 0 điểm. Ví dụ của đề cũng chỉ được 12 ô vì mảnh 2 chỉ chồng 2 ô (nhỏ hơn $T$) mà ghép thì hình bao lớn lên.

Cách 3Thử thật nhiều tham số trong 0,07 giây (lời giải đã nộp)

Không có bộ tham số nào tốt cho mọi test, nên lời giải cuối cùng thử rất nhiều và giữ phương án tốt nhất, dừng theo thời gian CPU:

1. Pha 1 – ghép mảnh với nhiều bộ tham số $(T, \alpha, \ldots)$: ghép khi số ô chồng $\ge T$, hoặc khi hình bao tăng không quá $\alpha \times$ số ô chồng; có thể giới hạn chiều cao/rộng khối, xáo trộn thứ tự các cặp có cùng số ô chồng. Đầu tiên thử một danh sách tham số cố định ($T$ từ $T_{\text{chắc}}$ giảm dần, $\alpha \in \{0; 0{,}5; 1; 2\}$...), sau đó sinh ngẫu nhiên tới khi gần hết giờ. Các bộ khối trùng nhau (cùng chữ ký) được bỏ qua.
2. Pha 2 – xếp khối: với mỗi bộ khối thử nhiều chiều cao $H$, cả bản chuyển vị (xếp theo chiều ngang thay vì dọc), 2 thứ tự (diện tích giảm dần; cao rồi rộng giảm dần) và 2 chế độ: first-fit, hoặc ưu tiên vị trí chồng khớp nhiều ô nhất trong phần đã xếp (lấp vào "lỗ" đúng chỗ).
3. Pha 3 – tìm kiếm cục bộ: 10% thời gian cuối đổi chỗ/di chuyển vài khối trong thứ tự xếp, đổi $H$ một chút, giữ lại nếu không tệ hơn.
4. Cuối cùng xoá các dòng/cột hoàn toàn không có mảnh nào đi qua. So khớp nhanh: mỗi dòng của mảnh mã hoá thành một số 2 bit/ô, so cả dòng bằng một phép so sánh số nguyên.

C++▶ Chạy tay từng dòng codeCách 3 (đã nộp tinhoctre.vn, bài 3040: 99,676 điểm): nhiều bộ tham số ghép + xếp dải 2 hướng/2 chế độ + tìm kiếm cục bộ.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 0 0 1 0 1 2 3 1 2 1 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Code 500 dòng nên khung này chạy theo từng pha (mỗi lần gọi assemble/tryPack là một bước). Phần thử ngẫu nhiên và tìm kiếm cục bộ phụ thuộc thời gian máy nên được bỏ qua; với dữ liệu nhỏ chúng không cải thiện thêm, kết quả trùng chương trình thật.

Một vài điểm đáng chú ý trong code:

1. elapsed() đo thời gian CPU (clock()) vì hệ thống chấm đo thời gian CPU. Hạn 0,07 giây chừa khoảng an toàn so với giới hạn 0,1 giây. Hệ quả: kết quả có thể khác nhau giữa các lần chạy (máy nhanh thì thử được nhiều phương án hơn).
2. Biến work đếm khối lượng công việc trong packStrip để một lần xếp quá đắt không "ăn" hết thời gian của các phương án khác.
3. Lần xếp đầu tiên luôn chạy trọn để chắc chắn có một phương án hợp lệ.

Không giannhư cách 2

Thời giancố định ≈ 0,07 giây CPU

Kết quả chạy thật (5 lần, chấm với $d$ của bộ test): 100,00 / 93,20 / 92,75 / 100,00 / 98,68 (trung bình 96,93) điểm, lâu nhất 0,07 giây CPU. Bảng chi tiết từng test:

Test	$d$	Cách 1 diện tích	điểm	Cách 2 diện tích	điểm	Cách 3 (5 lần chạy) diện tích	điểm TB
1	169	587	0,00	286	0,00	169	1,00
2	288	771	0,00	478	0,00	288	1,00
3	287	528	0,00	389	0,00	287	1,00
4	133	561	0,00	217	0,01	133	1,00
5	340	1.060	0,00	411	0,03	340	1,00
6	408	1.134	0,00	552	0,00	408	1,00
7	540	1.064	0,00	664	0,00	540	1,00
8	258	688	0,00	350	0,01	258	1,00
9	342	1.092	0,00	458	0,00	342 / 348 / 354	0,86
10	1.794	2.000	0,00	1.992	0,00	1.794	1,00
11	162	366	0,00	188	0,26	162	1,00
12	1	1	1,00	1	1,00	1	1,00
13	9	12	0,86	12	0,86	9	1,00
14	841	5.020	0,00	870	0,23	841	1,00
15	800	7.560	0,00	800	1,00	800	1,00
16	2.820	5.150	0,00	2.862	0,12	2.820 / 2.832	0,91
17	10.000	10.000	1,00	10.000	1,00	10.000	1,00
18	2.115	5.560	0,00	2.044	1,00	2.115 / 2.160 / 2.205	0,62
19	2.795	5.270	0,00	2.842	0,09	2.795	1,00
20	225	3.890	0,00	225	1,00	225	1,00

Chính code trên đã được nộp lên hệ thống chấm chính thức tinhoctre.vn (bài nộp 3040) và đạt 99,676/100 điểm: test 24 được 0,9/1, test 48 được 0,8/1, mọi test còn lại đủ điểm. Bản trước đó (dừng ở 0,065 giây, không xoá dòng/cột trống) cũng đạt đúng 99,676; bản 1 đơn giản hơn, chỉ ghép theo vài ngưỡng cố định, được 96,356. Lưu ý: lời giải này không đảm bảo tối ưu; trên các test nhỏ xíu mình so với vét cạn thì 599/600 test đạt tối ưu.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Điểm trên bộ test (/100)	Lâu nhất	Ghi chú
1. Xếp thành một hàng	C++	14,29	0.004s	Luôn hợp lệ, nhưng thừa rất nhiều ô
1. Xếp thành một hàng	Python	14,29	0.024s	Như bản C++
2. Ghép chắc chắn + xếp dải	C++	33,01	0.071s	Tất định, nhanh
3. Nhiều bộ tham số + lấp lỗ + tìm kiếm cục bộ	C++	100,00 / 93,20 / 92,75 / 100,00 / 98,68	0.075s	5 lần chạy (kết quả phụ thuộc thời gian máy)

Ghi chú của mình: điểm tính bằng checker của bài ($0{,}95^{\max(0, s - d)}$, quá 100 ô thì 0), trung bình 20 test × 100; thời gian là thời gian CPU, giới hạn 0,1 giây. Với bài tối ưu, chiến lược thi nên là: (1) nộp ngay một lời giải luôn hợp lệ (cách 1); (2) thêm ý tham lam chính (cách 2); (3) dành thời gian còn lại để thử nhiều biến thể và giữ cái tốt nhất trong giới hạn thời gian (cách 3) – chính bước này đưa điểm từ khoảng 33 lên gần 100 trên bộ test của mình.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇