Xếp hình (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng C2)

Nguồn: Tin học trẻ toàn quốc 2025 Độ khó: Khó Đường đi Euler Quy hoạch động

Đề bài

Có $n$ mảnh nhựa hình vuông đơn vị, đánh số từ 1 đến $n$. Trên mỗi cạnh và ở tâm của mỗi mảnh có ghi một số nguyên không âm. Mảnh nhựa được phép xoay nhưng không được lật mặt.

Cần chọn ra một số mảnh và xếp chúng thành một hàng ngang (các mảnh đặt cạnh nhau) sao cho:

• Hai mảnh kề nhau thì hai số ghi trên hai cạnh tiếp xúc của chúng phải bằng nhau;
• Tổng các số ghi ở tâm của những mảnh được xếp là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa năm số nguyên không âm $a_i, b_i, c_i, d_i, w_i$ ($0 \le a_i, b_i, c_i, d_i \le 3$): bốn số $a_i, b_i, c_i, d_i$ là các số trên các cạnh theo chiều kim đồng hồ (trên, phải, dưới, trái), $w_i$ là số ở tâm.

Kết quả: một số nguyên $s$ – tổng lớn nhất các số ở tâm của các mảnh xếp được.

Subtask:

• Subtask 1 (25% số điểm): $n \le 10$.
• Subtask 2 (25% số điểm): $n \le 20$.
• Subtask 3 (50% số điểm): $n \le 100$; $a_i = b_i$; $c_i = d_i$.

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

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

Ví dụ – output

3

Giải thích: có thể xếp ba mảnh đầu thành một hàng (xoay sao cho các cạnh ghi số 1 tiếp xúc nhau, hoặc các cạnh ghi số 2 tiếp xúc nhau), tổng tâm bằng 3. Không có cách nào nối thêm mảnh 4 hoặc mảnh 5 vào hàng đó.

Lưu ý: đề gốc không nêu giới hạn của $w_i$; bộ test dùng $0 \le w_i \le 10^9$ nên tổng có thể tới $10^{11}$ – phải dùng long long.

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 C2. Đề được mình viết lại cho dễ đọc, hình mảnh nhựa vẽ lại.

Lời mở đầu

Đọc đề thì tưởng là bài "xếp gạch" phải thử thứ tự và phép xoay – và với $n \le 10$ thì đúng là làm vậy được bằng QHĐ bitmask. Nhưng chìa khoá của bài là một cách nhìn rất đẹp: mỗi mảnh là một cạnh của đồ thị chỉ có 4 đỉnh, và một hàng hợp lệ chính là một đường đi Euler. Từ đó ta làm QHĐ với số trạng thái rất nhỏ, chạy được cho mọi $n \le 100$ (kể cả không có ràng buộc $a_i = b_i, c_i = d_i$).

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ưởngđường EulerCách 1bitmaskCách 2fullTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test của mình gồm 20 test chia đúng tỉ lệ subtask: test 1–5 (subtask 1), 6–10 (subtask 2), 11–20 (subtask 3). Test 1 là ví dụ của đề. Lời giải cuối cùng (cách 2) đã được nộp thử trên hệ thống chấm chính thức tinhoctre.vn và đạt 100/100 điểm.

Nhóm	Test	$n$	Số test có $a_i = b_i$, $c_i = d_i$	$w$ lớn nhất	Đáp án lớn nhất
Subtask 1	1–5	1 – 10	0/5	992.009.544	6.965.849.838
Subtask 2	6–10	19 – 20	0/5	990.270.802	12.225.206.062
Subtask 3	11–20	1 – 100	10/10	1.000.000.000	100.000.000.000

• Có test $n = 1$, test $w$ nhỏ (dễ có nhiều phương án bằng nhau), test $w$ tới $10^9$ (đáp án vượt $2^{31}$), test mọi mảnh giống hệt nhau, test các cạnh chỉ dùng 2 giá trị...
• Giới hạn thời gian chỉ 0,1 giây nên cách nào "hơi chậm" là mất điểm ngay.

Kết quả chạy thật của các cách theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 bitmask C++	Cách 1 Python	Cách 2 Euler C++	Cách 2 Python
Subtask 1 (25%)	$n \le 10$	1–5	5/5	5/5	5/5	5/5
Subtask 2 (25%)	$n \le 20$	6–10	0/5	0/5	5/5	5/5
Subtask 3 (50%)	$n \le 100$, $a_i = b_i$, $c_i = d_i$	11–20	1/10	1/10	10/10	10/10

Ý tưởngMỗi mảnh là một cạnh, mỗi hàng là một đường đi Euler

Bước 1 – một mảnh trong hàng chỉ có 2 "kiểu". Khi mảnh nằm trong hàng, thứ duy nhất quan trọng là cặp (cạnh trái, cạnh phải). Xoay mảnh 4 cách cho 4 cặp: $(d, b)$, $(c, a)$, $(b, d)$, $(a, c)$. Tức là cạnh trái – phải luôn là một cặp cạnh đối diện: $\{a, c\}$ hoặc $\{b, d\}$, và đi theo chiều nào cũng được (xoay thêm 180°).

Bước 2 – đồ thị 4 đỉnh. Lấy 4 giá trị 0, 1, 2, 3 làm 4 đỉnh. Mảnh được chọn đặt theo kiểu $\{a, c\}$ chính là một cạnh vô hướng nối đỉnh $a$ và đỉnh $c$ (có thể là khuyên nếu $a = c$). Hàng mảnh $L_1 R_1, L_2 R_2, \ldots$ với $R_1 = L_2, R_2 = L_3, \ldots$ chính là đi qua các cạnh liên tiếp: $L_1 \to R_1 = L_2 \to R_2 \to \ldots$ – một đường đi dùng mỗi cạnh đúng một lần, tức là đường đi Euler!

Định lý Euler (cho đường đi)

Một tập cạnh có đường đi Euler (đi qua mỗi cạnh đúng một lần) khi và chỉ khi: các cạnh liên thông với nhau và số đỉnh bậc lẻ là 0 hoặc 2.

Vậy bài toán trở thành: với mỗi mảnh chọn một trong 3 khả năng (bỏ, cạnh $a$–$c$, cạnh $b$–$d$) sao cho tập cạnh chọn được liên thông, có $\le 2$ đỉnh bậc lẻ, và tổng $w$ lớn nhất.

Bước 3 – QHĐ. Duyệt từng mảnh, trạng thái gồm: (1) tập đỉnh bậc lẻ – một mặt nạ 4 bit (thêm cạnh $u$–$v$ thì lật bit $u$ và bit $v$); (2) các thành phần liên thông của những đỉnh đã có cạnh – một cách chia 4 đỉnh thành nhóm (tối đa 52 cách). Tổng cộng chỉ $16 \times 52$ trạng thái, mỗi mảnh 3 lựa chọn: quá nhanh.

Em nhập các mảnh (mỗi dòng a b c d w, tối đa 7 mảnh) rồi bấm Tiếp: widget tìm cách chọn tốt nhất, vẽ đồ thị và đi đường Euler để dựng hàng:

Các mảnh (a b c d w): 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 3 0 3 0 1 3 3 3 3 1

Ví dụ nhanh:

Cách 1QHĐ bitmask theo tập mảnh đã dùng (subtask 1)

Xếp hàng từ trái sang phải. Trạng thái dp[mask][r] = tổng tâm lớn nhất của một hàng dùng đúng các mảnh trong mask và cạnh phải cùng bằng r. Từ trạng thái đó nối thêm mảnh $j$ chưa dùng, với phép xoay có cạnh trái bằng r. Đáp án là max mọi trạng thái đạt được.

C++▶ Chạy tay từng dòng codeCách 1: QHĐ bitmask dp[mask][r] – xếp từ trái sang phải, nối mảnh chưa dùng có cạnh trái khớp.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Hàm orient(i, t) trả về cặp (trái, phải) của mảnh $i$ sau khi xoay $t \cdot 90°$ – đúng 4 cặp ở bước 1 của phần ý tưởng.
2. Duyệt mask tăng dần là đúng thứ tự QHĐ vì mask | 1 << j luôn lớn hơn mask.

Không gian$O(2^n \cdot 4)$

Thời gian$O(2^n \cdot n \cdot 16)$

Kết quả chạy thật: Bản C++ đúng 6/20 test, sai test 11–14, 16, 18–20, quá thời gian test 6–10, 15, chạy lâu nhất 0.643s. Bản Python đúng 6/20 test, quá thời gian test 6–16, 18–20, chạy lâu nhất 1.002s. Với $n = 20$ có $2^{20} \cdot 4$ trạng thái, mỗi trạng thái thử $20 \cdot 4$ cách nối – khoảng $3 \cdot 10^8$ phép, mất hơn 0,6 giây, vượt xa giới hạn 0,1 giây. Còn $n = 100$ thì $2^{100}$ là không tưởng (chương trình còn bị lỗi khi cấp phát mảng). Bản C++ chỉ ăn subtask 1 (và test 17 có $n = 1$).

Cách 2Đường đi Euler + QHĐ trạng thái liên thông (full điểm)

Cài đặt bước 3 của phần ý tưởng. Phân hoạch liên thông được lưu bằng mảng nhãn lab[0..3]: lab[v] = 0 nếu đỉnh $v$ chưa có cạnh, các đỉnh cùng thành phần có cùng nhãn. Để mỗi phân hoạch có một mã duy nhất, ta đánh số lại nhãn theo thứ tự xuất hiện (ví dụ nhãn $(0, 3, 3, 2)$ chuẩn hoá thành $(0, 1, 1, 2)$) rồi ghép thành số cơ số 5 – nhỏ hơn $5^4 = 625$.

C++▶ Chạy tay từng dòng codeCách 2: QHĐ qua từng mảnh, trạng thái = (tập đỉnh bậc lẻ, phân hoạch liên thông).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mảng dp có 16 × 625 ô nhưng phần lớn là NEG; khung chạy tay chỉ dừng ở các trạng thái đạt được. Kí hiệu: "lẻ {1,2}" = đỉnh 1, 2 có bậc lẻ; "{0,2} {3}" = các thành phần liên thông.

1. addEdge: thêm cạnh $u$–$v$ – nếu cả hai đỉnh chưa có cạnh thì tạo thành phần mới; nếu một đỉnh chưa có thì nhập vào thành phần của đỉnh kia; nếu hai đỉnh khác thành phần thì gộp.
2. Bậc lẻ: odd ^ (1 << u) ^ (1 << v). Với khuyên $u = v$ hai phép XOR triệt tiêu – đúng vì khuyên làm bậc tăng 2.
3. Cuối cùng chỉ nhận trạng thái có $\le 2$ đỉnh bậc lẻ và chỉ một thành phần (nhãn lớn nhất $\le 1$). Trạng thái "chưa chọn gì" cho đáp án 0.
4. Cách này đúng với mọi $n \le 100$, không cần ràng buộc $a_i = b_i, c_i = d_i$ của subtask 3.

Không gian$O(16 \cdot 625)$

Thời gian$O(n \cdot 16 \cdot 625)$

Kết quả chạy thật: bản C++ đúng 20/20 test, chạy lâu nhất 0.007s – full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.040s (bản Python chỉ lưu các trạng thái đạt được trong dict nên cũng rất nhanh).

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. QHĐ bitmask	C++	6/20	0.643s	25 điểm (theo subtask)
1. QHĐ bitmask	Python	6/20	1.002s	25 điểm (theo subtask)
2. Đường đi Euler + QHĐ	C++	20/20	0.007s	100 điểm (theo subtask)
2. Đường đi Euler + QHĐ	Python	20/20	0.040s	100 điểm (theo subtask)

Ghi chú của mình: thời gian là thời gian CPU trên máy mình, giới hạn 0,1 giây; điểm tính theo subtask. Mình còn đối chiếu cách 2 với cách 1 trên các test nhỏ: khớp toàn bộ. Bài học: khi các "mảnh ghép" chỉ nối với nhau qua rất ít giá trị (ở đây 4), hãy thử coi giá trị là đỉnh và mảnh là cạnh – bài xếp hàng biến thành bài đường đi Euler. Lời giải cách 2 đã đạt 100/100 trên tinhoctre.vn.

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 😇