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 B)

Nguồn: Tin học trẻ 2023 Độ khó: Dễ Mảng 2 chiều Mô phỏng DSU

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng B (bài Bảng màu). Miền Bắc và miền Nam thi chung một đề, miền Trung có đề riê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).

Alice có một bảng $m$ hàng, $n$ cột. Hàng đánh số $1..m$ từ trên xuống, cột đánh số $1..n$ từ trái sang; ô ở hàng $i$, cột $j$ gọi là ô $(i, j)$.

Lúc đầu mọi ô đều 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 100$);
• tô tất cả các ô trong hình chữ nhật đó thành màu $c$ – màu mới đè lên màu cũ.

Yêu cầu: cho kích thước bảng và $k$ thao tác theo đúng thứ tự, hãy in ra màu của từng ô sau khi Alice tô xong.

Dữ liệu vào:

• Dòng 1: ba số nguyên $m, n, k$ ($1 \le m, n, k \le 100$).
• $k$ dòng tiếp theo, dòng thứ $s$ gồm năm số $x_s, y_s, u_s, v_s, c_s$: $(x_s, y_s)$ là ô góc trái trên, $(u_s, v_s)$ là ô góc phải dưới của hình chữ nhật ở thao tác thứ $s$ ($1 \le x_s \le u_s \le m$, $1 \le y_s \le v_s \le n$), $c_s$ là màu tô.

Kết quả: $m$ dòng, dòng thứ $i$ gồm $n$ số là màu các ô trên hàng $i$.

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

Ví dụ – input

3 3 2
1 1 2 2 2
2 2 3 3 1

Ví dụ – output

2 2 0
2 1 1
0 1 1

Giải thích: thao tác 1 tô hình vuông $2 \times 2$ ở góc trái trên thành màu 2; thao tác 2 tô hình vuông $2 \times 2$ ở góc phải dưới thành màu 1 và đè lên ô $(2, 2)$. Hai ô $(1, 3)$ và $(3, 1)$ không được tô nên vẫn là màu 0.

Lưu ý: đề gốc ghi nhầm "các hàng được đánh số từ 1 đến $n$ theo chiều từ trái sang phải" – ý đúng là các cột. Đề gốc chỉ ghi $m, n, k \le 100$; bộ test dùng $1 \le m, n, k \le 100$.

Lời mở đầu

Đây là bài "khởi động" của đề khu vực bảng B: chỉ cần làm đúng như đề nói là được trọn điểm. Mình vẫn viết 3 cách để các bạn thấy cùng một bài có thể nhìn theo nhiều hướng: tô xuôi, nhìn từng ô, và tô ngược. Cách thứ 3 (tô ngược, nhảy qua ô đã tô) là ý tưởng rất hay dùng khi bảng lớn hơn nhiều.

Bảng C1 cũng có một bài tên Bảng màu nhưng là bài ngược: cho bảng màu cuối cùng, hãy tìm lại các thao tác (bài tối ưu, chấm điểm từng phần) – xem trên CLUE ở bài Bảng màu bảng C1. Hiểu kỹ bài này (đặc biệt là cách nhìn "tô ngược") sẽ giúp ích nhiều cho bài C1.

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ưởngtô sau thắngCách 1mô phỏngCách 2từng ôCách 3tô ngượcTổ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 của đề: 20 test, test 1 là ví dụ của đề. Đề chỉ có một mức giới hạn ($m, n, k \le 100$) nên không chia subtask. Mình cố ý cho đủ kiểu: bảng 1 ô, 1 hàng, 1 cột, tô cả bảng, chỉ tô 1 ô, toàn hình $1 \times 1$, tô cả hàng/cả cột, ít màu (dễ lộ lỗi thứ tự tô)...

Test	$m \times n$	$k$	Kiểu thao tác	Màu lớn nhất	Tổng số ô bị tô (cộng mọi thao tác)	Số ô trắng lúc cuối
1	$3 \times 3$	2	ví dụ của đề	2	8	2
2	$1 \times 1$	1	bảng 1 ô	100	1	0
3	$1 \times 100$	100	bảng 1 hàng	100	3.424	0
4	$100 \times 1$	100	bảng 1 cột	100	3.545	0
5	$5 \times 7$	10	hình nhỏ, ô lẻ	86	37	13
6	$100 \times 100$	1	tô cả bảng 1 lần	86	10.000	0
7	$100 \times 100$	1	chỉ tô 1 ô	42	1	9.999
8	$10 \times 10$	20	ngẫu nhiên, 3 màu	3	422	7
9	$37 \times 52$	60	ngẫu nhiên + hình nhỏ	100	5.668	259
10	$100 \times 100$	100	cả hàng / cả cột	99	10.000	3.904
11	$100 \times 100$	100	toàn ô lẻ $1 \times 1$	100	100	9.900
12	$100 \times 100$	100	hình nhỏ	99	570	9.453
13	$100 \times 100$	100	ngẫu nhiên	100	111.578	142
14	$100 \times 100$	100	ngẫu nhiên, 2 màu	2	129.349	458
15	$100 \times 100$	100	cả bảng + ngẫu nhiên	99	372.675	0
16	$99 \times 100$	100	ngẫu nhiên + cả hàng	97	39.041	626
17	$100 \times 73$	100	ngẫu nhiên + cả cột	99	55.909	361
18	$100 \times 100$	100	tô cả bảng 100 lần	100	1.000.000	0
19	$64 \times 100$	77	trộn nhiều kiểu	99	11.923	2.390
20	$100 \times 100$	100	trộn nhiều kiểu	99	248.289	0

Trường hợp nặng nhất là test 18: 100 lần tô cả bảng $100 \times 100$, tổng cộng $1\,000\,000$ lượt gán ô – vẫn rất nhỏ với máy tính.

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

Lời giải mô phỏng (cách 1) 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ả 3 cách trên bộ test của CLUE:

Subtask	Điều kiện	Test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++	Cách 3 Python
Subtask duy nhất (100%)	$m, n, k \le 100$	1–20	20/20	20/20	20/20	20/20	20/20	20/20

Ý tưởngAi tô sau thì thắng

Mấu chốt của bài chỉ có một câu: màu cuối cùng của ô $(i, j)$ là màu của thao tác cuối cùng có hình chữ nhật chứa ô đó (không thao tác nào chứa thì là 0). Từ câu này có 3 cách làm:

1. Tô xuôi (cách 1): làm đúng thứ tự $1, 2, \dots, k$, mỗi lần gán màu cho cả hình chữ nhật. Thao tác sau tự động đè thao tác trước.
2. Nhìn từng ô (cách 2): với mỗi ô, duyệt các thao tác từ $k$ về $1$, gặp thao tác đầu tiên chứa ô thì đó là màu của ô.
3. Tô ngược (cách 3): làm từ thao tác $k$ về $1$, chỉ tô những ô chưa được tô; ô đã tô rồi là đã có "màu cuối" nên giữ nguyên. Mỗi ô chỉ bị tô đúng một lần.

Ba cách đều có độ phức tạp $O(k \cdot m \cdot n) \le 10^6$ trong trường hợp xấu nhất (riêng cách 3 còn nhanh hơn – xem bên dưới). Em nhập bảng và các thao tác rồi bấm Tiếp để xem từng lần tô (khung vàng = hình chữ nhật đang tô):

m = n = Các thao tác x y u v c (cách nhau bởi ;) =

Ví dụ nhanh:

Cách 1Mô phỏng: tô đè từng thao tác

Dùng mảng a[105][105] khai báo toàn cục (tự bằng 0 = màu trắng). Đọc thao tác nào thì tô ngay thao tác đó bằng 2 vòng lặp lồng nhau. Cuối cùng in bảng.

C++▶ Chạy tay từng dòng codeCách 1: đọc thao tác nào tô đè ngay thao tác đó, cuối cùng in bảng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Hai vòng for(int i = x; i <= u; i++) và for(int j = y; j <= v; j++) đi qua đúng các ô của hình chữ nhật; dùng chỉ số từ 1 cho khớp đề.
• Khi in, (j < n ? ' ' : '\n'): giữa các số là dấu cách, cuối hàng xuống dòng.

Không gian$O(m \cdot n)$

Thời gian$O(k \cdot m \cdot n)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.006s. Bản Python đúng 20/20 test, chạy lâu nhất 0.032s. Full điểm.

Cách 2Từng ô: tìm thao tác cuối cùng phủ nó

Lưu hết $k$ thao tác vào mảng. Với mỗi ô $(i, j)$, duyệt $s$ từ $k$ giảm về 1: thao tác đầu tiên có $x_s \le i \le u_s$ và $y_s \le j \le v_s$ chính là thao tác tô ô này sau cùng → break. Không có thao tác nào thì ô màu 0.

C++▶ Chạy tay từng dòng codeCách 2: với mỗi ô, duyệt ngược các thao tác, gặp thao tác đầu tiên chứa ô thì lấy màu đó.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Cách này không cần mảng bảng màu, và cho thấy rõ "ai tô sau thì thắng". Nó có ích khi đề chỉ hỏi màu của vài ô (mỗi ô $O(k)$) thay vì cả bảng.

Không gian$O(k)$

Thời gian$O(m \cdot n \cdot k)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.061s. Full điểm.

Cách 3Tô ngược và nhảy qua ô đã tô

Đi từ thao tác $k$ về $1$. Ô nào đã được tô bởi một thao tác sau thì màu cuối của nó đã xác định, không được tô nữa. Nếu chỉ thêm if kiểm tra "ô đã tô chưa" thì vẫn phải đi qua từng ô, chưa nhanh hơn. Mẹo là với mỗi hàng $i$, dùng mảng nxt[i][j] = ô chưa tô đầu tiên ở hàng $i$ tính từ cột $j$, cài đặt như DSU (hợp nhất – tìm gốc) có nén đường đi:

• Lúc đầu nxt[i][j] = j (ô nào cũng chưa tô). Cột $n + 1$ làm "lính canh".
• Tô ô $(i, j)$ xong thì đặt nxt[i][j] = j + 1: lần sau ai hỏi tới cột $j$ sẽ được chuyển sang phải.
• Hàm timO(i, j) đi theo nxt tới khi gặp ô chưa tô và nén đường đi, nên đoạn ô đã tô dài bao nhiêu cũng chỉ bị nhảy qua rất nhanh.

C++▶ Chạy tay từng dòng codeCách 3: tô ngược từ thao tác cuối, dùng nxt (kiểu DSU) để nhảy qua các ô đã tô.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi ô bị tô đúng 1 lần, mỗi hàng của mỗi thao tác chỉ tốn thêm một lần timO. Tổng thời gian khoảng $O(m \cdot n + k \cdot m \cdot \alpha)$ – với $m, n$ lên tới vài nghìn cách 1 sẽ chậm còn cách này vẫn nhanh. Đây cũng là cách nhìn "ngược thời gian" mà bài Bảng màu bảng C1 dùng: thao tác cuối cùng hiện ra trọn vẹn, các thao tác trước bị che dần.

Không gian$O(m \cdot n)$

Thời giankhoảng $O(m \cdot n + k \cdot m \cdot \alpha)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.026s (bản Python dùng vòng while thay cho đệ quy để tìm gốc).

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. Mô phỏng: tô đè từng thao tác	C++	20/20	0.006s	100%
	Python	20/20	0.032s	100%
2. Từng ô: tìm thao tác cuối phủ nó	C++	20/20	0.004s	100%
	Python	20/20	0.061s	100%
3. Tô ngược + nhảy qua ô đã tô (DSU)	C++	20/20	0.004s	100%
	Python	20/20	0.026s	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 1 giây). Với giới hạn 100 thì cả 3 cách đều thừa sức, kể cả Python. Điều đáng nhớ: khi các thao tác ghi đè lên nhau, hãy thử nghĩ ngược thời gian – thao tác cuối cùng luôn "thắng", và mỗi ô chỉ cần xử lý một lần.

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 😇