Hình chữ nhật 0 1 ver 2

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Khó Ngăn xếp đơn điệu Mảng 2 chiều

Đề bài

Cho một bảng $a$ gồm $N$ hàng, $M$ cột. Ô ở hàng thứ $i$ và cột thứ $j$ được gọi là ô $(i, j)$, các ô trong bảng nhận giá trị $0$ hoặc $1$. Hình chữ nhật $(x_1, y_1, x_2, y_2)$ bao gồm các ô $(i, j)$ mà $x_1 \le i \le x_2$ và $y_1 \le j \le y_2$.

Yêu cầu: Hãy tính diện tích của hình chữ nhật lớn nhất bao gồm toàn số 0 và số lượng hình chữ nhật có diện tích như vậy.

Dữ liệu:

• Dòng đầu tiên gồm hai số nguyên dương $N, M$ $(1 \le N, M \le 1000)$ là số hàng và số cột của bảng $a$.
• $N$ dòng tiếp theo, mỗi dòng chứa $M$ số $0$ hoặc $1$ biểu diễn giá trị của các ô trong bảng.

Kết quả: Gồm một dòng duy nhất chứa hai số nguyên, lần lượt là diện tích của hình chữ nhật thỏa mãn và số hình chữ nhật như vậy.

Ràng buộc: $1 \le N \le 1000$; $1 \le M \le 1000$; các ô của bảng có giá trị $0$ hoặc $1$.

Chấm điểm:

Subtask	Ràng buộc thêm	% số điểm
1	$N, M \le 100$	50
2	Không có	50

Hạn chế thời gian: 1 giây. Hạn chế bộ nhớ: 256 MB.

Ví dụ – input

5 4
1 0 0 1
0 0 0 0
0 1 1 0
1 1 0 0
1 0 0 0

Ví dụ – output

4 4

Giải thích ví dụ: bốn hình chữ nhật thỏa mãn (viết theo dạng $(x_1, y_1, x_2, y_2)$) là $(1, 2, 2, 3)$, $(2, 1, 2, 4)$, $(2, 4, 5, 4)$ và $(4, 3, 5, 4)$ – mỗi hình có diện tích $4$.

Lời mở đầu

Bài này giống hệt Hình chữ nhật 0 1 ver 1 nhưng khó hơn một bậc: ngoài diện tích lớn nhất còn phải đếm có bao nhiêu hình chữ nhật đạt diện tích đó. Cái khó nằm ở chỗ cách ngăn xếp của ver 1 có thể "nhìn thấy" cùng một hình chữ nhật nhiều lần – nếu cứ thế mà đếm thì sẽ đếm trùng. Mình sẽ nhắc lại nhanh ý tưởng của ver 1 rồi tập trung vào phần khác biệt: làm sao để mỗi hình được đếm đúng một lần.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test100 test, 2 subtaskÝ tưởngchống đếm trùngCách 1vét cạn O(N²M²)Cách 2ngăn xếp O(N·M)

Bộ testBộ test chính thức có gì?

Test	N	M	Tỉ lệ số 0	Diện tích lớn nhất	Số hình
1 – 20	1 … 10	1 … 10	0% … 61%	0 … 8	0 … 5
21 – 50	10 … 98	11 … 97	47% … 52%	6 … 18	1 … 6
51 – 80	117 … 975	112 … 997	49% … 50%	15 … 30	1 … 6
81 – 100	1.000	1.000	49% … 49%	18 … 25	1 … 16

• Bộ test có 100 test: test 1–50 thuộc subtask 1 ($N, M \le 100$), test 51–100 thuộc subtask 2 (test 81–100 đều là bảng $1000 \times 1000$ – một triệu ô).
• Mọi bảng đều sinh ngẫu nhiên với khoảng một nửa số ô là 0, nên hình chữ nhật toàn 0 lớn nhất rất nhỏ (không quá 30 ô). Bộ test không có bảng toàn 0 hay các khối 0 lớn.
• Test lạ: test 18 là bảng $1 \times 1$ chỉ có một ô số 1 → không có hình toàn 0 nào, đáp án 0 0. Code phải xử lý được trường hợp này.
• Số hình đạt diện tích lớn nhất thường là 1 (69/100 test), nhiều nhất là 16. Bộ test của ver 2 khác bộ test của ver 1 (sinh lại với kích thước khác).

Subtask	Điều kiện	Các test	Cách 1 C++	Cách 2 C++	Cách 1 Python	Cách 2 Python
1 (50%)	$N, M \le 100$	1 – 50	50/50	50/50	43/50	50/50
2 (50%)	Không có	51 – 100	4/50	50/50	0/50	50/50

Ý tưởngĐếm mỗi hình đúng một lần

Nhắc lại ver 1. Cố định hàng đáy $i$, gọi $h[j]$ = số ô 0 liên tiếp từ ô $(i, j)$ đi lên. Khi đó mỗi hàng là một bài Hình chữ nhật lớn nhất (histogram): với mỗi cột $j$, tìm $L[j]$ (cột gần nhất bên trái thấp hơn) và $R[j]$ (bên phải) bằng ngăn xếp, hình của cột $j$ có diện tích $h[j] \times (R[j] - L[j] - 1)$.

Nhận xét 1 – hình lớn nhất luôn "không nới được". Nếu hình chữ nhật toàn 0 có diện tích lớn nhất (và $> 0$) thì không thể nới nó thêm sang trái, phải, lên hay xuống (nới được thì diện tích tăng). Hình như vậy có một hàng đáy duy nhất $i$, chiều cao đúng bằng cột thấp nhất $\min(h[l..r])$, và hai bên $l - 1$, $r + 1$ là cột thấp hơn (hoặc mép bảng). Tức là nó chính là "hình của cột $j$" với $j$ là một cột thấp nhất trong $[l, r]$.

Vấn đề – đếm trùng. Nếu trong $[l, r]$ có nhiều cột cùng thấp nhất (ví dụ $h = [2, 2]$), thì ở ver 1 mỗi cột đó đều "nhìn thấy" cùng một hình $2 \times 2$. Ver 1 chỉ cần max nên không sao, nhưng ở đây cộng cnt nhiều lần là sai.

Cách sửa: một bên "thấp hơn hẳn", một bên "thấp hơn hoặc bằng"

Lấy $L[j]$ = cột gần nhất bên trái có $h < h[j]$ (như cũ), nhưng $R[j]$ = cột gần nhất bên phải có $h \le h[j]$. Khi đó trong một nhóm cột bằng nhau, chỉ cột phải nhất có hình kéo dài hết cỡ; các cột còn lại bị "cắt" ở cột bằng nó ngay bên phải, nên hình của chúng nhỏ hơn hẳn diện tích lớn nhất và không được đếm. Mỗi hình lớn nhất được đếm đúng một lần.

Trong code chỉ khác ver 1 đúng một ký tự: vòng while của lần duyệt phải dùng > thay vì >=. Ngoài ra phải bỏ qua cột $h[j] = 0$ (hình diện tích 0 không phải hình toàn 0) – nếu bảng toàn số 1 thì in 0 0.

Em nhập bảng (các hàng cách nhau bởi dấu /) rồi bấm Tiếp để xem từng cột được tính hình nào, khi nào cnt tăng. Thử ví dụ "Hai cột bằng nhau" để thấy hình bị cắt:

Bảng (hàng cách nhau bởi /):

Ví dụ nhanh:

Cách 1Vét mọi hình chữ nhật – O(N²M²)

Một hình chữ nhật được xác định bởi hàng trên $x_1$, hàng dưới $x_2$, cột trái $y_1$, cột phải $y_2$. Để biết nó có toàn 0 hay không, ta đếm số ô 1 bên trong bằng tổng tiền tố 2 chiều: $s[i][j]$ = số ô 1 trong hình $(1, 1)$ – $(i, j)$, khi đó số ô 1 của hình $(x_1, y_1, x_2, y_2)$ là

$s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1]$ $+ s[x_1 - 1][y_1 - 1]$

Hình toàn 0 khi và chỉ khi con số này bằng 0. Lần này ngoài diện tích lớn nhất best ta đếm luôn số hình cnt đạt diện tích đó.

C++▶ Chạy tay từng dòng codeCách 1: tổng tiền tố s rồi vét mọi hình (x1, y1, x2, y2), hình nào có 0 ô số 1 thì cập nhật (best, cnt).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vét cạn có rất nhiều bước, nên khung này giới hạn bảng tối đa 5 × 5. Ô đỏ đậm: ô số 1 nằm trong hình đang xét.

1. Gặp hình có số 1 thì continue bỏ qua ngay.
2. Gặp diện tích lớn hơn best thì đặt lại cnt = 1 (hình đầu tiên đạt diện tích mới); bằng thì cnt++. Mỗi bộ $(x_1, y_1, x_2, y_2)$ là một hình khác nhau nên không lo đếm trùng.
3. Bảng toàn số 1 thì không có hình nào → in 0 0.

Không gian$O(N \cdot M)$

Thời gian$O(N^2 M^2)$

Kết quả chạy thật: bản C++ đúng 54/100 test (quá 1 giây ở các test 51–62, 64–65, 67, 69–73, 75–100), test đúng chạy lâu nhất 0.602s; bản Python đúng 43/100 test (quá thời gian ở các test 24, 29, 38, 40, 42–43, 45, 51–100), lâu nhất 0.40s.

Với $N = M = 100$ có khoảng $(100 \cdot 101 / 2)^2 \approx 2{,}5 \cdot 10^7$ hình – C++ chạy kịp. Với $N = M = 1000$ thì con số này là $2{,}5 \cdot 10^{11}$ – không thể.

Cách 2Chiều cao cột + ngăn xếp – O(N·M)

Giống Cách 2 của ver 1, chỉ khác 3 chỗ: điều kiện > ở vòng duyệt phải, bỏ qua cột cao 0, và cập nhật cặp (best, cnt) thay cho một biến ans.

C++▶ Chạy tay từng dòng codeCách 2: mỗi hàng cập nhật h[j], rồi dùng ngăn xếp tìm L[j], R[j] (trái: thấp hơn hẳn, phải: thấp hơn hoặc bằng) và đếm hình diện tích lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Lần duyệt trái: h[st.top()] >= h[j] → bỏ cả cột bằng → L[j] là cột thấp hơn hẳn.
2. Lần duyệt phải: h[st.top()] > h[j] → giữ lại cột bằng → R[j] là cột thấp hơn hoặc bằng. Đây là chỗ chống đếm trùng.
3. if(h[j] == 0) continue; – không có hình toàn 0 nào ở cột này. Nhờ vậy bảng toàn 1 cho kết quả 0 0 (bộ test có đúng trường hợp này).
4. Hai hình có cùng diện tích lớn nhất nhưng khác hàng đáy, hoặc khác cột, là hai hình khác nhau → mỗi hình được đếm một lần ở đúng hàng đáy của nó.

Không gian$O(M)$ (không lưu cả bảng)

Thời gian$O(N \cdot M)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.086s; bản Python đúng 100/100 test, lâu nhất 0.57s.

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)	Ghi chú
1. Vét mọi hình + tổng tiền tố – $O(N^2 M^2)$	C++	54/100	0.602s	Quá thời gian ở test 51–62, 64–65, 67, 69–73, 75–100
	Python	43/100	0.401s	Quá thời gian ở test 24, 29, 38, 40, 42–43, 45, 51–100
2. Chiều cao cột + ngăn xếp – $O(N \cdot M)$	C++	100/100	0.086s	Full điểm
	Python	100/100	0.568s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây/test). Cách 2 với C++ chạy mọi test dưới 0,09 giây (phần lớn thời gian là đọc một triệu số). Bản Python của Cách 2 cũng qua hết. Điểm mấu chốt của ver 2 so với ver 1: một bên so sánh <, một bên ≤ – kỹ thuật này dùng cho mọi bài "đếm theo phần tử nhỏ nhất" (ví dụ tính tổng min của mọi đoạn con) để không đếm trùng.

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 😇