Bảng màu (Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng C1)
Đề bài
Alice có một bảng $m$ hàng, $n$ cột (hàng $1..m$ từ trên xuống, cột $1..n$ từ trái sang; ô ở hàng $i$, cột $j$ là ô $(i, j)$). Ban đầu mọi ô màu trắng (màu $0$). Alice làm lần lượt $k$ thao tác, mỗi thao tác chọn một hình chữ nhật nằm trọn trong bảng (gồm nguyên các ô) và một màu $c$ ($1 \le c \le 30$), rồi tô đè tất cả các ô của hình đó thành màu $c$.
Bob nhìn thấy bảng màu cuối cùng của Alice nhưng không biết Alice đã tô thế nào. Bob muốn dùng không quá $k$ thao tác cùng loại (bắt đầu từ bảng toàn màu trắng) để tạo ra một bảng giống bảng của Alice nhất có thể.
Yêu cầu: cho bảng màu của Alice và $k$, hãy giúp Bob tìm dãy không quá $k$ thao tác sao cho bảng nhận được càng giống bảng của Alice càng tốt.
Dữ liệu vào:
- Dòng 1: ba số nguyên $m, n, k$ ($k \le 100$).
- $m$ dòng tiếp theo, dòng thứ $i$ gồm $n$ số $a_{i1}, \dots, a_{in}$ ($0 \le a_{ij} \le 30$) – màu các ô trên hàng $i$ của bảng Alice.
Kết quả:
- Dòng 1: số nguyên không âm $h \le k$ – số thao tác của Bob.
- $h$ dòng tiếp theo, mỗi dòng năm số $x, y, u, v, c$: $(x, y)$ là ô góc trái trên, $(u, v)$ là ô góc phải dưới của hình chữ nhật ($1 \le x \le u \le m$, $1 \le y \le v \le n$), $c$ ($1 \le c \le 30$) là màu tô. Các thao tác được thực hiện đúng theo thứ tự in ra.
Giới hạn: 30% số test có $m, n, k \le 5$; 50% số test khác có $m, n \le 50$; 20% số test còn lại có $m, n \le 500$. Giới hạn thời gian: 2 giây.
Cách tính điểm: có 20 test, mỗi test 5 điểm. Gọi $d$ là số ô trên bảng của Bob trùng màu với ô tương ứng trên bảng Alice; điểm của test là $5 \times \left(\dfrac{d}{m \times n}\right)^5$. Output sai định dạng (ví dụ $h > k$, hình chữ nhật ra ngoài bảng, màu ngoài $[1, 30]$) được 0 điểm.
3 3 2
2 2 0
2 2 1
0 1 12
1 1 2 2 2
2 2 3 3 1Giải thích: output mẫu tô màu 2 cho hình $(1,1)$–$(2,2)$ rồi tô màu 1 cho hình $(2,2)$–$(3,3)$. Bảng của Bob:
Alice Bob 2 2 0 2 2 0 2 2 1 2 1 1 0 1 1 0 1 1
Hai bảng trùng $8/9$ ô (chỉ khác ô $(2, 2)$) nên output mẫu được $5 \times (8/9)^5 \approx 2{,}77$ điểm. Nếu tô theo thứ tự ngược lại (màu 1 trước, màu 2 sau) thì trùng hoàn toàn và được trọn 5 điểm – đúng như output của các lời giải bên dưới.
Lời mở đầu
Đây là bài tối ưu (chấm điểm từng phần) của bảng C1, và là bài "ngược" của bài Bảng màu bảng B: bảng B cho các thao tác, hỏi bảng màu; còn bài này cho bảng màu, hỏi lại các thao tác. Không có công thức "đúng tuyệt đối" ở đây – ta cố gắng đạt càng nhiều điểm càng tốt. Mũ 5 trong công thức điểm rất "gắt": sai 2% số ô đã mất khoảng 10% số điểm của test, nên phải nhắm tới tái tạo đúng hoàn toàn.
Mình đi từ cách ngây thơ (mỗi màu một hình) tới ý tưởng chính "bóc lớp ngược thời gian", rồi tới lời giải đầy đủ đã nộp chính thức.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE do mình tự sinh theo đúng tỉ lệ của đề: 20 test (6/10/4 test cho ba nhóm 30%/50%/20%), test 1 là ví dụ. Mỗi bảng được tạo bằng đúng $k$ thao tác tô ngẫu nhiên trên bảng trắng (nhiều kiểu: hình ngẫu nhiên, hình nhỏ, hình lớn, sọc cả hàng/cả cột, ô lẻ), nên về lý thuyết luôn đạt được trọn điểm. Cột "bảng sau khi nén" sẽ giải thích ở phần ý tưởng.
| Nhóm | Test | $m \times n$ | $k$ | Số màu | Bảng sau khi nén | Số ô màu 0 | Kiểu thao tác của Alice |
|---|---|---|---|---|---|---|---|
| Nhóm 1 (30%) | 1 | $3 \times 3$ | 2 | 2 | $3 \times 3$ | 2 | ví dụ của đề |
| 2 | $5 \times 5$ | 5 | 4 | $5 \times 4$ | 9 | ngẫu nhiên, 2 màu, có ô lẻ | |
| 3 | $5 \times 5$ | 5 | 1 | $2 \times 3$ | 2 | bảng $1 \times 1$ | |
| 4 | $1 \times 1$ | 1 | 1 | $1 \times 1$ | 0 | cả hàng/cả cột | |
| 5 | $5 \times 5$ | 4 | 3 | $3 \times 5$ | 13 | ngẫu nhiên, 2 màu | |
| 6 | $4 \times 5$ | 5 | 2 | $4 \times 4$ | 6 | ngẫu nhiên | |
| Nhóm 2 (50%) | 7 | $50 \times 50$ | 100 | 16 | $23 \times 18$ | 57 | ngẫu nhiên, 30 màu |
| 8 | $50 \times 50$ | 100 | 2 | $48 \times 47$ | 1.637 | toàn hình nhỏ, 2 màu | |
| 9 | $50 \times 50$ | 60 | 5 | $30 \times 36$ | 133 | sọc hàng/cột, 5 màu | |
| 10 | $50 \times 50$ | 100 | 19 | $36 \times 34$ | 168 | ngẫu nhiên + ô lẻ | |
| 11 | $37 \times 50$ | 40 | 5 | $14 \times 23$ | 86 | hình lớn + hình nhỏ | |
| 12 | $50 \times 1$ | 20 | 6 | $9 \times 1$ | 3 | một cột | |
| 13 | $1 \times 50$ | 30 | 3 | $1 \times 6$ | 1 | một hàng | |
| 14 | $50 \times 50$ | 100 | 2 | $1 \times 2$ | 0 | toàn hình lớn | |
| 15 | $45 \times 50$ | 80 | 23 | $37 \times 32$ | 117 | sọc hàng/cột, 30 màu | |
| 16 | $50 \times 50$ | 100 | 3 | $25 \times 20$ | 88 | ngẫu nhiên + nhỏ, 3 màu | |
| Nhóm 3 (20%) | 17 | $500 \times 500$ | 100 | 19 | $65 \times 64$ | 6.577 | ngẫu nhiên, 30 màu |
| 18 | $500 \times 500$ | 100 | 29 | $154 \times 158$ | 165.229 | toàn hình nhỏ, 30 màu | |
| 19 | $500 \times 500$ | 100 | 26 | $94 \times 92$ | 20.329 | sọc hàng/cột đan nhau, 30 màu | |
| 20 | $500 \times 480$ | 100 | 5 | $27 \times 26$ | 2.080 | lớn + nhỏ + ô lẻ, 5 màu |
Điểm chạy thật của các cách trên bộ test (chấm bằng checker, điểm mỗi nhóm = tỉ lệ % × trung bình điểm các test trong nhóm):
| Nhóm | Điều kiện | Test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 3 C++ |
|---|---|---|---|---|---|---|
| Nhóm 1 (30%) | $m, n, k \le 5$ | 1–6 | 21.65/30 | 21.65/30 | 30.00/30 | 30.00/30 |
| Nhóm 2 (50%) | $m, n \le 50$ | 7–16 | 12.56/50 | 12.56/50 | 49.76/50 | 50.00/50 |
| Nhóm 3 (20%) | $m, n \le 500$ | 17–20 | 0.04/20 | 0.04/20 | 19.22/20 | 19.80/20 |
Ý tưởngBóc lớp ngược thời gian
Nhận xét 1 – thao tác cuối cùng hiện ra trọn vẹn. Thao tác tô sau cùng của Alice không bị gì đè lên, nên hình chữ nhật của nó trên bảng cuối toàn một màu $c$. Nếu ta đoán đúng thao tác đó và "bóc" nó ra, các ô của nó trở thành ô tự do: thao tác trước đó tô gì lên các ô này cũng không sao (đằng nào cũng bị đè). Thao tác áp chót lúc này là một hình chữ nhật gồm toàn ô màu $c'$ hoặc ô tự do... Cứ thế bóc dần từ thao tác cuối về thao tác đầu, rồi đảo ngược thứ tự là được dãy thao tác tô xuôi. Đây chính là cách nhìn "tô ngược" ở bài bảng B.
Nhận xét 2 – chọn hình nào để bóc? Ở mỗi bước, mọi hình chữ nhật chỉ gồm ô màu $c$ hoặc ô tự do đều là "ứng viên hợp lệ" (bóc nó không làm sai ô nào). Mình chọn tham lam ứng viên giải thích được nhiều ô màu $c$ chưa tự do nhất. Với mỗi màu $c$, các hình chữ nhật "toàn ô hợp lệ" lớn nhất tìm được bằng kỹ thuật histogram + ngăn xếp (giống bài hình chữ nhật lớn nhất trong ma trận 0/1), và số ô màu $c$ bên trong tính bằng mảng cộng dồn 2 chiều.
Nhận xét 3 – nén bảng. Hai hàng liền nhau giống hệt nhau thì có thể gộp thành một (tương tự với cột): mỗi ô của bảng nén có trọng số = số ô gốc nó đại diện. Bảng tạo từ $k \le 100$ hình chữ nhật có tối đa $2k + 1 = 201$ "đường cắt" mỗi chiều, nên bảng $500 \times 500$ nén lại còn nhiều nhất khoảng $201 \times 201$ – nhỏ hơn hẳn.
Em nhập bảng rồi bấm Tiếp để xem bóc lớp: ô mờ có gạch là ô đã tự do, khung vàng là hình vừa bóc. Cuối cùng là dãy thao tác tô xuôi:
Cách 1Mỗi màu một hình bao
Cách đơn giản nhất: với mỗi màu $c$ có trên bảng, tô hình chữ nhật bao các ô màu $c$. Hình bao lớn tô trước, hình bao nhỏ tô sau (hình nhỏ thường là thao tác "nằm trên"). Có hơn $k$ màu thì giữ $k$ màu nhiều ô nhất. Cách này đúng khi mỗi màu chỉ được tô một lần và các hình lồng nhau gọn gàng.
Hai lần sắp xếp dùng stable_sort để các màu bằng nhau giữ thứ tự ban đầu (kết quả ổn định, dễ kiểm tra).
Kết quả chạy thật (chấm bằng checker): Bản C++ được 34.25/100 điểm, trọn điểm 5/20 test, chạy lâu nhất 0.014s. Bản Python được 34.25/100 điểm, trọn điểm 5/20 test, chạy lâu nhất 0.079s. Trọn điểm ở các bảng rất đơn giản, nhưng bảng thật thường có một màu được tô nhiều lần ở nhiều chỗ: hình bao của màu đó phủ lên cả vùng màu khác → mất rất nhiều ô, và mũ 5 làm điểm tụt mạnh.
Cách 2Bóc lớp ngược thời gian (tham lam)
Cài đặt đúng ba nhận xét: nén bảng, rồi lặp: với mỗi màu $c$ còn ô chưa tự do, dựng mảng cộng dồn P của các ô màu $c$ chưa tự do, duyệt mọi hình chữ nhật "toàn ô màu $c$ hoặc tự do" bằng histogram + ngăn xếp, giữ hình có trọng số tw lớn nhất. Bóc hình đó (đánh dấu tự do), lặp tới khi mọi ô khác 0 đều tự do. Cuối cùng đảo ngược. Nếu bóc quá $k$ lần thì giữ $k$ thao tác giải thích nhiều ô nhất.
- Ở hàng
i,h[j]là số ô hợp lệ liên tiếp kết thúc ở hàngitrong cộtj. Khi một cột bị lấy ra khỏi ngăn xếp với chiều caocao, hình chữ nhật caocaorộng từtraitớiphailà hình lớn nhất có đáy ở hàngivới chiều cao đó. tw= tổng trọng số ô màu $c$ chưa tự do trong hình (tính từPtrong $O(1)$). Ô tự do có trong hình không được tính – chúng chỉ "cho phép" hình to ra.- Bóc luôn tồn tại ít nhất một hình có
tw > 0(thao tác còn lại sau cùng của Alice), nên vòng lặp luôn tiến.
Kết quả chạy thật: Bản C++ được 98.98/100 điểm, trọn điểm 16/20 test, chạy lâu nhất 0.413s. Chỉ với ý tưởng tham lam này đã gần trọn điểm! Các test chưa trọn là do tham lam đôi khi bóc nhầm một mảnh của một thao tác bị che (ví dụ một dải hẹp màu $c$ nằm thẳng hàng với một dải màu $c$ khác – thật ra là một hình lớn bị một sọc khác đè ngang qua): bóc nhầm thì tốn thêm thao tác và vượt quá $k$, phải bỏ bớt thao tác.
Cách 3Bóc lớp + vét cạn + nhiều biến thể (lời giải đã nộp)
Đây là lời giải mình đã nộp chính thức. Nó giữ khung của cách 2 và thêm:
- Vét cạn cho bảng nhỏ: bảng nén có không quá 36 ô (luôn đúng với nhóm $m, n, k \le 5$) thì dùng IDDFS (tìm kiếm sâu dần) trên trạng thái "tập ô tự do" (mặt nạ bit 64 bit), chỉ thử các hình chữ nhật hợp lệ tối đại, có nhớ các trạng thái đã thất bại → tìm được số thao tác ít nhất.
- Đánh dấu ứng viên "đáng ngờ": ứng viên có mảnh cùng màu thẳng hàng với nó, hoặc có dải kề/tia (không gặp ô màu 0) dẫn tới ô cùng màu, nhiều khả năng chỉ là mảnh của một thao tác lớn hơn đang bị che → hoãn hoặc phạt điểm khi chọn.
- Nhiều biến thể + nhiễu ngẫu nhiên: chạy nhiều lượt bóc lớp với các cách đánh dấu khác nhau và nhiễu ngẫu nhiên trên khoá chọn, trong khoảng 0,7 giây, giữ kết quả khớp nhiều ô nhất (tính chính xác có trọng số).
- Khi quá $k$ thao tác: thử gộp hai thao tác cùng màu thành hình bao của chúng nếu không làm sai ô nào; vẫn còn thừa thì lần lượt bỏ thao tác làm mất ít ô khớp nhất (tính chính xác nhờ lưu "lớp trên cùng" và "lớp ngay dưới" của mỗi ô).
- Tập ứng viên của mỗi màu được giữ lại giữa các bước, chỉ tính lại khi hình vừa bóc giao với hình bao của màu đó – nhanh hơn cách 2 nhiều lần.
Kết quả chạy thật trên máy mình: Bản C++ được 99.80/100 điểm, trọn điểm 19/20 test, chạy lâu nhất 0.510s. Riêng test 19 (sọc ngang/dọc đan nhau, 30 màu – kiểu khó nhất cho bóc lớp) được $0{,}959$ điểm của test. Vì phần chạy nhiều biến thể dừng theo thời gian thực, kết quả phụ thuộc tốc độ máy: máy của mình lúc đo đang chạy nhiều việc cùng lúc nên chạy được ít biến thể hơn. Trên hệ thống chấm chính thức (tinhoctre.vn) lời giải này được 100/100, trên CLUE được 20/20. Python không phù hợp với cách này (cần chạy rất nhiều lượt trong 0,7 giây) nên mình không viết.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Điểm (/100) | Số test trọn điểm | Lâu nhất | Test chưa trọn điểm |
|---|---|---|---|---|---|
| 1. Mỗi màu một hình bao | C++ | 34.25 | 5/20 | 0.014s | 1 (0.555), 3 (0.659), 6 (0.116), 7 (0.001), 8 (0.000), 9 (0.000), 10 (0.010), 11 (0.072), 13 (0.418), 15 (0.002), 16 (0.008), 17 (0.006), 18 (0.001), 19 (0.000), 20 (0.000) |
| Python | 34.25 | 5/20 | 0.079s | 1 (0.555), 3 (0.659), 6 (0.116), 7 (0.001), 8 (0.000), 9 (0.000), 10 (0.010), 11 (0.072), 13 (0.418), 15 (0.002), 16 (0.008), 17 (0.006), 18 (0.001), 19 (0.000), 20 (0.000) | |
| 2. Bóc lớp ngược thời gian (tham lam) | C++ | 98.98 | 16/20 | 0.413s | 9 (0.976), 15 (0.976), 18 (0.979), 19 (0.866) |
| 3. Bóc lớp + vét cạn + nhiều biến thể | C++ | 99.80 | 19/20 | 0.510s | 19 (0.959) |