Tô màu bảng (Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B, C2)

Nguồn: Tin học trẻ 2024 Độ khó: Trung bình Tổ hợp Fibonacci QHĐ bitmask Quay lui

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B và Bảng C2 (bài Tô màu bảng). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho một bảng $n$ dòng, $m$ cột. Mỗi ô được tô bằng một trong hai màu: trắng hoặc đen.

Hãy đếm số cách tô màu cả bảng sao cho không có ba ô liên thông nào cùng màu. Ba ô gọi là liên thông nếu chúng tạo thành một trong các hình sau (ba ô thẳng hàng dọc, thẳng hàng ngang, hoặc bốn kiểu hình chữ L):

Dữ liệu vào: một dòng chứa hai số nguyên $n, m$ ($1 \le n, m \le 100$).

Kết quả: một số nguyên là số cách tô thoả mãn, lấy phần dư khi chia cho $10^9 + 7$.

Subtask:

• Subtask 1 (42%): $n, m \le 5$;
• Subtask 2 (21%): $n = 2$;
• Subtask 3 (27%): $n \le 5$;
• Subtask 4 (10%): không có ràng buộc gì thêm.

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

Ví dụ – input

2 2

Ví dụ – output

6

Giải thích: bảng $2 \times 2$ có $2^4 = 16$ cách tô. Các cách hỏng là các cách có ít nhất 3 ô cùng màu (khi đó 3 ô ấy luôn tạo thành một hình chữ L): có $2 \cdot (4 + 1) = 10$ cách như vậy. Còn lại $16 - 10 = 6$ cách: 2 kiểu bàn cờ, 2 kiểu "hai hàng khác màu", 2 kiểu "hai cột khác màu".

Lời mở đầu

Đây là một bài đếm rất đẹp (giống bài Ivan the Fool and the Probability Theory trên Codeforces). Đáp án cuối cùng chỉ là một công thức Fibonacci vài dòng, nhưng để thấy được công thức đó thì mình đi từng bước theo subtask: quay lui để đếm thử (subtask 1), quy hoạch động theo cột khi một cạnh nhỏ (subtask 1, 2, 3), rồi nhìn ra cấu trúc của bảng để có công thức (full).

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ộ test25 testÝ tưởng2 nhận xétCách 1quay lui – 42đCách 2QHĐ cột – 90đCách 3Fibonacci – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 25 test (test 1 là ví dụ của đề). Có đủ các trường hợp biên như $1 \times 1$, $1 \times m$, $n \times 1$, $100 \times 100$.

Nhóm	Test	Các giá trị $n$	$m$ nhỏ nhất – lớn nhất	Test có cạnh nhỏ $\le 5$
Subtask 1	1–10	1, 2, 3, 4, 5	1 – 5	test 1–10
Subtask 2	11–15	2	1 – 100	test 11–15
Subtask 3	16–22	1, 3, 4, 5	46 – 100	test 16–22
Subtask 4	23–25	90, 100	1 – 100	test 24

Lưu ý test nhóm trước cũng thoả điều kiện các nhóm sau (ví dụ test $2 \times 5$ thuộc cả subtask 1, 2, 3). Subtask 4 có test $100 \times 1$ – cạnh nhỏ vẫn chỉ là 1.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng trong bài mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 quay lui C++	Cách 1 Python	Cách 2 QHĐ cột C++	Cách 3 công thức C++	Cách 3 Python
Subtask 1 (42%)	$n, m \le 5$	1–10	10/10	10/10	10/10	10/10	10/10
Subtask 2 (21%)	$n = 2$	11–15	1/5	1/5	5/5	5/5	5/5
Subtask 3 (27%)	$n \le 5$	16–22	0/7	0/7	7/7	7/7	7/7
Subtask 4 (10%)	không ràng buộc thêm	23–25	0/3	0/3	1/3	3/3	3/3

Ý tưởngMỗi ô có tối đa một ô kề cùng màu

Sáu hình trong đề chính là tất cả các cách chọn 3 ô liên thông (theo cạnh). Ba ô liên thông thì luôn có một ô ở giữa kề với hai ô còn lại. Vì vậy:

Nhận xét 1

Không có 3 ô liên thông cùng màu $\iff$ mỗi ô có tối đa một ô kề (trên, dưới, trái, phải) cùng màu với nó.

Với một dải $1 \times k$ (một hàng), điều kiện là không có 3 ô liên tiếp cùng màu. Gọi $f(k)$ = số cách tô dải $1 \times k$ chia 2 (cố định màu ô đầu). Dải kết thúc bằng một khối 1 ô hoặc khối 2 ô cùng màu, nên:

$$f(1) = 1, \quad f(2) = 2, \quad f(k) = f(k-1) + f(k-2).$$

Đó chính là dãy Fibonacci! Dải $1 \times k$ có $2f(k)$ cách tô.

Nhận xét 2

Nếu trong bảng có hai ô kề ngang cùng màu (giả sử ô $(i, j)$ và $(i, j+1)$) thì ô ngay dưới mỗi ô đó bắt buộc khác màu (nếu không thì ô trên có 2 ô kề cùng màu). Lan dần ra cả hàng, hàng dưới phải là hàng trên đảo màu – và cứ thế cho mọi hàng. Khi đó cả bảng do hàng đầu quyết định, hàng đầu là một dải $1 \times m$ hợp lệ: $2f(m)$ cách.
Ngược lại, nếu không có hai ô kề ngang nào cùng màu thì mọi hàng đều xen kẽ trắng/đen, mỗi hàng chỉ có 2 khả năng và cả bảng do cột đầu quyết định: $2f(n)$ cách.
Bàn cờ (2 cách) thuộc cả hai trường hợp nên bị đếm 2 lần: $$\text{đáp án} = 2f(m) + 2f(n) - 2.$$

Em chọn $n, m$ nhỏ rồi bấm Tiếp để xem lần lượt mọi cách tô hợp lệ, kèm loại của nó: A = có hai ô kề ngang cùng màu (mỗi hàng là hàng trên đảo màu), B = có hai ô kề dọc cùng màu (mỗi cột là cột trái đảo màu), bàn cờ = thuộc cả hai:

n = m =

Ví dụ nhanh:

Cách 1Quay lui tô từng ô (Subtask 1)

Tô lần lượt từng ô theo thứ tự hàng (ô thứ $k$ ở hàng $k / m$, cột $k \bmod m$), mỗi ô thử 2 màu. Mảng cung[i][j] đếm số ô kề cùng màu đã tô của ô $(i, j)$. Khi tô ô mới, chỉ ô bên trên và ô bên trái là đã tô, nên chỉ cần cập nhật hai ô đó; nếu ô nào có cung vượt quá 1 thì cắt nhánh ngay.

C++▶ Chạy tay từng dòng codeCách 1: quay lui tô từng ô theo hàng, cắt nhánh khi có ô có 2 ô kề cùng màu (ô viền đỏ).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Sau khi thử xong một màu phải hoàn tác (trả lại cung của ô trên, ô trái) rồi mới thử màu kia – đây là "lui" trong quay lui.
2. Không cần hoàn tác mau[i][j] vì lần thử sau sẽ ghi đè, còn các ô phía sau chưa được đọc tới.
3. Nhờ cắt nhánh sớm, số trạng thái được duyệt tỉ lệ với số cách tô hợp lệ (bảng $5 \times 5$ chỉ có 30 cách) nên rất nhanh. Nhưng với $2 \times 100$ có tới $2(f(2) + f(100) - 1)$ $\approx 1{,}1 \cdot 10^{21}$ cách – đếm từng cách một là không thể.

Không gian$O(nm)$

Thời giantỉ lệ với số cách tô hợp lệ (tối đa $2^{nm}$)

Kết quả chạy thật: Bản C++ đúng 11/25 test, quá thời gian test 11, 13–25 (các test đúng chạy lâu nhất 0.004s). Bản Python đúng 11/25 test, quá thời gian test 11, 13–25 (các test đúng chạy lâu nhất 0.024s). Ăn trọn subtask 1 (42 điểm); test 12 ($2 \times 1$) của subtask 2 cũng qua nhưng các test còn lại của subtask 2 thì không.

Cách 2Quy hoạch động theo cột (Subtask 1, 2, 3)

Đổi chỗ để $n$ là cạnh nhỏ ($n \le 5$). Tô bảng từng cột, mỗi cột là một số $n$ bit (bit $i$ = màu ô hàng $i$). Để biết cột mới có hợp lệ không, ta cần nhớ của cột trước: màu của nó $c$, và mặt nạ $fl$ = các ô của cột trước đã có 1 ô kề cùng màu (không được có thêm).

• doc[d] = mặt nạ các ô của cột $d$ có 1 ô kề dọc cùng màu, hoặc $-1$ nếu có ô có 2 ô kề dọc cùng màu (cột $d$ tự nó đã hỏng).
• Cột mới $d$ đặt cạnh cột $c$: các hàng có ô mới cùng màu ô bên trái là ngang = ~(c ^ d). Hỏng nếu ô bên trái đã có một ô cùng màu (ngang & fl) hoặc ô mới vừa có kề dọc vừa có kề ngang (ngang & doc[d]).
• Trạng thái mới: dp[d][ngang | doc[d]].

C++▶ Chạy tay từng dòng codeCách 2: QHĐ theo cột, trạng thái (màu cột trước c, các ô đã có 1 ô kề cùng màu fl). Bit viết theo thứ tự hàng 0, 1, ...

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. dp chỉ có $2^5 \cdot 2^5 = 1024$ trạng thái, mỗi trạng thái thử $32$ cột mới, $m \le 100$ cột: khoảng $3 \cdot 10^6$ phép tính.
2. Khi cạnh nhỏ lớn hơn 5 (subtask 4) thì $2^n$ trạng thái quá nhiều – code dừng luôn, không in gì.

Không gian$O(4^n)$

Thời gian$O(m \cdot 8^n)$ với $n \le 5$

Kết quả chạy thật: Bản C++ đúng 23/25 test, sai test 23, 25 (các test đúng chạy lâu nhất 0.004s) – test 24 ($100 \times 1$) vẫn qua vì cạnh nhỏ là 1. Được 90 điểm (subtask 1, 2, 3). Cách này không cần nghĩ ra nhận xét 2, chỉ cần nhận xét 1.

Cách 3Công thức Fibonacci – O(n + m) (full)

Từ nhận xét 2: đáp án $= 2f(n) + 2f(m) - 2$ với $f$ là dãy Fibonacci $f(1) = 1, f(2) = 2$. Mình còn đối chiếu công thức với Cách 1 và Cách 2 trên mọi bảng nhỏ trong bộ test – khớp hết.

C++▶ Chạy tay từng dòng codeCách 3: tính dãy Fibonacci f rồi áp công thức 2f(n) + 2f(m) − 2.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Mảng f cấp phát tới max(n, m) + 2 để f[2] luôn tồn tại kể cả khi $n = m = 1$.
2. + MOD trước khi lấy dư để phép trừ 2 không làm kết quả âm (do f[n] + f[m] đã bị lấy dư nên có thể nhỏ).

Không gian$O(n + m)$

Thời gian$O(n + m)$

Kết quả chạy thật: Bản C++ đúng 25/25 test, chạy lâu nhất 0.003s. Bản Python đúng 25/25 test, chạy lâu nhất 0.019s. Full điểm cho cả hai ngôn ngữ.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
1. Quay lui tô từng ô	C++	11/25	0.004s	42%
	Python	11/25	0.024s	42%
2. QHĐ theo cột (cạnh nhỏ ≤ 5)	C++	23/25	0.004s	90%
3. Công thức Fibonacci	C++	25/25	0.003s	100%
	Python	25/25	0.019s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 0,5 giây). Mẹo làm bài đếm: viết một chương trình quay lui đếm thử các bảng nhỏ (Cách 1), in ra bảng kết quả theo $n, m$ – sẽ thấy ngay các số $6, 8, 10, 14, 16, \dots$ có dạng "Fibonacci nhân 2", từ đó đoán và chứng minh công thức. Và nếu chưa nghĩ ra công thức thì QHĐ bitmask theo cột (Cách 2) đã đủ 90 điểm.

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 😇