Chọn sách

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Khá Quy hoạch động Dãy con tăng dài nhất Tìm kiếm nhị phân

Đề bài

Thư viện trường học của bạn An có $n$ quyển sách, mỗi quyển sách có dạng hình chữ nhật. Các quyển sách được đánh số thứ tự từ 1 đến $n$. Quyển sách thứ $i$ $(i = 1, 2, \ldots, n)$ có chiều dài là $d_i$, chiều rộng là $r_i$ (đơn vị độ dài). Bạn An muốn chọn một số quyển sách trong $n$ quyển sách để xếp thành một chồng sao cho quyển sách được xếp ở trên có kích thước nhỏ hơn quyển sách được xếp ở dưới, tức là nếu quyển sách $i$ được xếp trên quyển sách $j$ thì $d_i < d_j$ và $r_i < r_j$.

Yêu cầu: hãy đưa ra số sách lớn nhất mà bạn An có thể chọn để xếp được chồng sách theo yêu cầu trên. Ta gọi số quyển sách nhiều nhất có thể chọn được là $S$.

Dữ liệu: vào từ bàn phím gồm:

• Dòng đầu tiên ghi số nguyên dương $n$ $(2 \le n \le 2 \times 10^5)$ là số lượng quyển sách.
• Dòng thứ $i$ trong $n$ dòng tiếp theo ghi 2 số nguyên dương $d_i$ và $r_i$ $(1 \le d_i, r_i \le 10^8)$ tương ứng là chiều dài và chiều rộng của quyển sách thứ $i$.

Kết quả: ghi ra màn hình số nguyên $S$ tìm được.

Subtask:

• 20% số test đầu tiên có $N \le 20$.
• 60% số test tiếp theo có $N \le 10^4$.
• 20% số test còn lại không có điều kiện gì thêm.

Ví dụ 1 – input

2
6 3
5 3

Ví dụ 1 – output

1

Ví dụ 2 – input

5
3 2
4 1
10 6
8 4
7 5

Ví dụ 2 – output

3

Ví dụ 3 – input

2
5 4
3 1

Ví dụ 3 – output

2

Giải thích: ví dụ 1 hai quyển cùng chiều rộng 3 nên không quyển nào đặt lên quyển kia được → chỉ chọn 1 quyển. Ví dụ 2 chọn quyển 1, 5, 3, xếp từ trên xuống dưới: quyển 1 $(3 \times 2)$ → quyển 5 $(7 \times 5)$ → quyển 3 $(10 \times 6)$. Ví dụ 3 chọn cả 2 quyển: quyển 2 $(3 \times 1)$ đặt trên quyển 1 $(5 \times 4)$.

Lời mở đầu

Nếu mỗi quyển sách chỉ có một kích thước thì đây chính là bài dãy con tăng dài nhất (LIS). Ở đây có hai kích thước $d$ và $r$ phải cùng tăng. Mẹo kinh điển: sắp xếp theo $d$ để "khử" một chiều, khi đó chỉ còn phải lo chiều $r$ – và bài quay về LIS. Mình sẽ đi 3 nấc: đệ quy thử chọn/bỏ → QHĐ $O(n^2)$ → LIS bằng tìm kiếm nhị phân $O(n \log n)$, kèm một cái bẫy rất hay gặp khi có nhiều quyển trùng chiều 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ộ test3 subtaskÝ tưởngSắp xếp + dpCách 1Đệ quyCách 2O(n²)Cách 3O(n log n)

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

Test	$n$	$d, r$ lớn nhất	Số quyển trùng chiều dài (nhiều nhất)	Đáp án
1–20	2 … 19	996	1	1 … 7
21–40	23 … 94	9.997	2	6 … 16
41–60	103 … 884	32.767	16	15 … 54
61–80	1.361 … 9.792	32.768	1.335	72 … 189
81–90	10.042 … 40.461	32.768	17.217	192 … 404
91–100	101.405 … 200.000	32.768	167.308	615 … 875

• 100 test, khớp với 3 subtask của đề: test 1–20 có $n \le 20$, test 21–80 có $n < 10^4$, test 81–100 lớn hơn (có 5 test đúng $n = 2 \cdot 10^5$).
• Dù đề cho $d, r \le 10^8$, bộ test chỉ dùng giá trị tới 32.768. Vì vậy ở các test lớn có rất nhiều quyển trùng chiều dài (và trùng chiều rộng) – cột thứ 4 đếm số quyển có chiều dài đã xuất hiện ở quyển khác. Code nào xử lý sai trường hợp trùng sẽ lộ ngay.
• Ví dụ của đề không nằm trong bộ test.

Ba subtask và số test đúng của từng cách (chạy thật):

Subtask	Điều kiện	Các test	Cách 1 đệ quy	Cách 2 $O(n^2)$	Cách 3 $O(n \log n)$
1 (20%)	$n \le 20$	1 – 20	20/20	20/20	20/20
2 (60%)	$n \le 10^4$	21 – 80	21/60	60/60	60/60
3 (20%)	$n \le 2 \cdot 10^5$	81 – 100	0/20	5/20	20/20

(Số test đúng của bản C++, chạy thật với giới hạn 1 giây/test.)

Ý tưởngSắp theo chiều dài, rồi làm LIS

Trong một chồng sách hợp lệ, đi từ trên xuống dưới thì chiều dài tăng ngặt. Vậy nếu ta sắp xếp các quyển theo chiều dài tăng dần, mọi chồng sách đều là một dãy con (giữ thứ tự) của dãy đã sắp – quyển ở trên luôn đứng trước quyển ở dưới. Bài toán trở thành:

Trạng thái quy hoạch động

Sắp xếp các quyển theo $d$ tăng dần. $dp[i]$ = số quyển nhiều nhất của một chồng mà quyển $i$ nằm dưới cùng.

dp[i] = 1 + max{ dp[j] : j < i, d[j] < d[i], r[j] < r[i] }

(không có $j$ nào thì $dp[i] = 1$). Đáp án $S = \max dp[i]$.

Em nhập các quyển sách (mỗi quyển 2 số $d\ r$) rồi bấm Tiếp. Bước đầu sắp xếp, sau đó tính $dp$ từng quyển: ô tím là các quyển đặt lên trên được, ô xanh là quyển có $dp$ lớn nhất được chọn. Bước cuối vẽ chồng sách nhìn từ trên xuống – các hình chữ nhật lồng nhau:

Các quyển (d r ...)

Ví dụ nhanh:

Cách 1Đệ quy chọn / bỏ từng quyển (subtask 1)

Sau khi sắp xếp theo chiều dài, đi qua từng quyển và quyết định có đặt nó xuống dưới chồng đang xếp hay không. Chỉ được đặt khi nó to hơn hẳn (cả 2 chiều) quyển vừa đặt trước đó (last).

C++▶ Chạy tay từng dòng codeCách 1: sau khi sắp xếp, Try(i, last, cnt) đặt hoặc bỏ từng quyển.

Dữ liệu vào (stdin) – sửa thoải mái5 3 2 4 1 10 6 8 4 7 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Con trỏ last trên mảng chỉ quyển vừa đặt vào chồng.

Không gian$O(n)$

Thời gianSố chồng sách hợp lệ – hàm mũ

Kết quả chạy thật: đúng 41/100 test, quá thời gian ở các test 41–44, 46–100; test đúng chạy lâu nhất 0,115 s. Đệ quy duyệt qua mọi chồng sách hợp lệ – số chồng này tăng theo hàm mũ: qua trọn subtask 1 và cả các test $n < 100$ đầu subtask 2, nhưng từ $n$ vài trăm trở lên thì quá thời gian.

Cách 2Quy hoạch động dp[i] – O(n²) (subtask 1, 2)

C++▶ Chạy tay từng dòng codeCách 2: dp[i] = 1 + max dp[j] với quyển j nhỏ hơn hẳn quyển i.

Dữ liệu vào (stdin) – sửa thoải mái5 3 2 4 1 10 6 8 4 7 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Mỗi lần kiểm tra của vòng j dừng ở dòng if (gộp với dòng for).

1. sort(b, b + n) sắp các cặp $(d, r)$ theo $d$ tăng dần (bằng $d$ thì theo $r$). Nhờ vậy mọi quyển đặt được lên trên quyển $i$ đều nằm ở vị trí $j < i$.
2. Vẫn phải kiểm tra cả hai điều kiện b[j].first < b[i].first và b[j].second < b[i].second: hai quyển cùng chiều dài đứng cạnh nhau sau khi sắp, nhưng không được chồng lên nhau.

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 85/100 test, quá thời gian ở các test 83–84, 86–87, 90–100; test đúng chạy lâu nhất 0,875 s. Với $n = 10^4$ có khoảng $5 \cdot 10^7$ cặp $(j, i)$ – chạy vèo; nhưng với $n = 2 \cdot 10^5$ là $2 \cdot 10^{10}$ cặp, không thể kịp 1 giây. Bản Python đúng 67/100 test, quá thời gian ở các test 61–62, 64, 66–70, 74, 77–100; test đúng chạy lâu nhất 0,771 s.

Cách 3LIS bằng tìm kiếm nhị phân – O(n log n) (full điểm)

Để bỏ được điều kiện về $d$ trong vòng lặp, ta sắp xếp khéo hơn: $d$ tăng dần, cùng $d$ thì $r$ giảm dần. Khi đó chỉ cần tìm dãy con tăng ngặt dài nhất của dãy $r$:

• Hai quyển khác chiều dài: quyển đứng trước có $d$ nhỏ hơn hẳn, chỉ cần thêm $r$ tăng là chồng được. ✔
• Hai quyển cùng chiều dài: vì $r$ được xếp giảm dần nên dãy con tăng của $r$ không bao giờ lấy được cả hai. ✔

LIS của dãy $r$ thì tính bằng mảng t quen thuộc:

Mảng t (tails)

$t[k]$ = chiều rộng nhỏ nhất có thể của quyển dưới cùng trong một chồng $k + 1$ quyển (đã gặp). Mảng $t$ luôn tăng ngặt. Gặp quyển có chiều rộng $r$: tìm phần tử đầu tiên $\ge r$ (lower_bound); nếu không có thì nối $r$ vào cuối (chồng dài thêm 1), ngược lại thay phần tử đó bằng $r$ (cùng độ dài nhưng đáy hẹp hơn, dễ đặt lên quyển khác hơn). Đáp án là độ dài của $t$.

C++▶ Chạy tay từng dòng codeCách 3: sắp d tăng (r giảm khi trùng d), rồi LIS tăng ngặt trên r bằng lower_bound.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bộ "Trùng chiều dài" cho thấy vì sao phải xếp r giảm khi trùng d: (5, 4) đứng trước (5, 1) nên không bị nối thành chồng 2 quyển.

Không gian$O(n)$

Thời gian$O(n \log n)$

Kết quả chạy thật: bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0,051 s. Bản Python dùng bisect_left đúng 100/100 test; test đúng chạy lâu nhất 0,575 s.

Cái bẫy: cùng chiều dài mà xếp r tăng dần

Nếu sắp xếp mặc định (cùng $d$ thì $r$ tăng dần) rồi làm LIS trên $r$, hai quyển $(5, 1)$ và $(5, 4)$ sẽ bị đếm thành một chồng 2 quyển – sai vì cùng chiều dài. Mình đã thử nộp bản sai này: chỉ đúng 70/100 test. Phải là lower_bound (tăng ngặt) và $r$ giảm dần khi trùng $d$.

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. Đệ quy chọn / bỏ	C++	41/100	0,115 s	Quá thời gian ở test 41–44, 46–100
2. QHĐ dp[i] O(n²)	C++	85/100	0,875 s	Quá thời gian ở test 83–84, 86–87, 90–100
	Python	67/100	0,771 s	Quá thời gian ở test 61–62, 64, 66–70, 74, 77–100
3. LIS + tìm kiếm nhị phân	C++	100/100	0,051 s	Full điểm
	Python	100/100	0,575 s	Full điểm

Ghi chú của mình: các cách đều được chấm trên đủ 100 test của CLUE (giới hạn 1 giây). Đệ quy ăn subtask 1 (và các test $n < 100$), QHĐ $O(n^2)$ ăn thêm subtask 2 (và vài test nhỏ của subtask 3), LIS $O(n \log n)$ full điểm cả C++ lẫn Python. Kỹ thuật "sắp một chiều, LIS chiều kia, trùng thì xếp ngược" dùng được cho rất nhiều bài lồng hộp, lồng phong bì (Russian Doll Envelopes).

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 😇