Dãy hình chữ nhật lồng nhau
Đề bài
Trên mặt phẳng toạ độ cho $N$ hình chữ nhật với các cạnh song song với hệ trục toạ độ, các hình chữ nhật được đánh số từ 1 tới $N$. Hình chữ nhật thứ $i$ được cho bởi 4 số nguyên dương $x_{i1}, y_{i1}, x_{i2}, y_{i2}$, trong đó $(x_{i1}, y_{i1})$ là toạ độ đỉnh trái dưới, còn $(x_{i2}, y_{i2})$ là toạ độ đỉnh phải trên. Ta nói rằng hình chữ nhật thứ $i$ nằm trong hình chữ nhật thứ $j$ nếu trên mặt phẳng toạ độ mọi điểm của hình thứ $i$ đều thuộc hình thứ $j$.
Yêu cầu: với $N$ hình chữ nhật cho trước, hãy tìm $K$ hình chữ nhật với chỉ số $i_1, i_2, \ldots, i_K$ sao cho hình $i_1$ nằm trong hình $i_2$, hình $i_2$ nằm trong hình $i_3$, …, hình $i_{K-1}$ nằm trong hình $i_K$ và $K$ là lớn nhất. Biết rằng hai hình chữ nhật bất kỳ trong $N$ hình chữ nhật đã cho hoặc rời nhau hoặc một trong hai hình nằm trong hình còn lại.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương $N$ $(1 \le N \le 100)$.
- $N$ dòng tiếp theo, dòng thứ $i$ chứa 4 số nguyên dương $x_{i1}, y_{i1}, x_{i2}, y_{i2}$.
Kết quả: số $K$ tìm được.
3
1 1 7 4
3 1 6 6
2 2 5 42Giải thích ví dụ (hình vẽ dưới): hình 3 (vàng) nằm trọn trong hình 1 (xanh lá) nên dãy $3 \to 1$ dài $K = 2$. Hình 2 (xanh dương, nét đứt) cắt ngang cả hình 1 lẫn hình 3 nên không ghép thêm được. Các bạn để ý: hình 1 và hình 2 cắt nhau – tức là chính ví dụ của đề đã không đúng với câu "hoặc rời nhau hoặc lồng nhau"!
Lời mở đầu
Bài này là một biến thể rất đẹp của bài toán kinh điển dãy con tăng dài nhất (LIS): thay vì "số sau lớn hơn số trước" thì ở đây là "hình sau chứa hình trước". Mình sẽ đi theo đúng lộ trình của chương Quy hoạch động: bắt đầu bằng quay lui thử mọi dãy, thấy nó chết ở đâu, rồi thêm bộ nhớ cho hàm đệ quy, cuối cùng viết lại thành bảng quy hoạch động sau khi sắp xếp. Cả 3 cách mình đều nộp thử trên bộ test thật và ghi lại kết quả.
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 chính thức có gì?
| Test | Số hình $N$ | Toạ độ | Đáp án $K$ |
|---|---|---|---|
| 001–020 | 1–10 | 1 → 30 | 1–3 |
| 021–099 | 100 | 1 → 74.489 | 3–14 |
| 100 | 100 | 1 → 101 | 100 |
Đề không chia subtask, nhưng bộ 100 test chia rất rõ thành 3 mức. Có 3 điều mình rút ra khi soi bộ test:
- Cam kết "hai hình bất kỳ hoặc rời nhau hoặc lồng nhau" KHÔNG đúng: ngay ví dụ của đề đã có hình 1 và hình 2 cắt nhau, và 96/100 test có cặp hình cắt nhau. Vậy ta không được dựa vào cam kết này (ví dụ kiểu "chỉ cần so diện tích"), mà phải kiểm tra đúng định nghĩa "nằm trong".
- Hai hình chung cạnh vẫn tính là nằm trong nhau (định nghĩa: mọi điểm của hình $i$ thuộc hình $j$, điểm trên cạnh vẫn thuộc hình). Mình thử đổi các dấu $\le$ thành $<$ thì chỉ còn 47/100 test.
- Test 100 là cái bẫy: 100 hình lồng nhau liên tiếp như búp bê Nga, đáp án là 100. Test này "giết" mọi cách vét cạn.
| Mức | Điều kiện | Test | Cách 1 quay lui | Cách 2 đệ quy có nhớ | Cách 3 QHĐ bảng |
|---|---|---|---|---|---|
| 1 | $N \le 10$ | 001–020 | qua | qua | qua |
| 2 | $N = 100$, ngẫu nhiên | 021–099 | qua | qua | qua |
| 3 | $N = 100$, lồng liên tiếp | 100 | quá thời gian | qua | qua |
Ý tưởngHình to đứng trước, mỗi hình hỏi các hình chứa nó
Gọi $f[i]$ là độ dài dãy lồng nhau dài nhất có hình trong cùng là hình $i$. Dãy đó hoặc chỉ có mỗi hình $i$ (dài 1), hoặc hình ngay bên ngoài hình $i$ là một hình $j$ nào đó chứa $i$ – và phần còn lại chính là một dãy kết thúc ở $j$. Vậy:
Hình $i$ nằm trong hình $j$ $\iff$ $x_{j1} \le x_{i1}$, $y_{j1} \le y_{i1}$, $x_{i2} \le x_{j2}$, $y_{i2} \le y_{j2}$.
Muốn tính $f[i]$ thì mọi $f[j]$ của hình chứa nó phải được tính trước. Mẹo: hình chứa $i$ luôn có diện tích lớn hơn hình $i$ (bộ test không có 2 hình trùng nhau), nên chỉ cần sắp xếp các hình theo diện tích giảm dần rồi tính $f$ từ trái sang phải – y hệt bài LIS: mỗi phần tử nhìn lại các phần tử đứng trước nó.
Em nhập các hình (mỗi hình 4 số) rồi bấm Tiếp. Hình vàng là hình $i$ đang tính, hình viền xanh dương nét đứt là hình $j$ đang được hỏi "có chứa $i$ không?":
Cách 1Quay lui thử mọi dãy lồng nhau
Cách "ngây thơ" nhất: chọn hình ngoài cùng, rồi lần lượt thử nhét một hình vào trong nó, rồi lại nhét tiếp một hình vào trong hình vừa nhét… Hàm Try(cur, len) nghĩa là "hình trong cùng hiện tại là cur, dãy đang dài len". Mỗi lần được gọi thì cập nhật kỷ lục best, rồi thử mọi hình i nằm trong cur.
- Không cần mảng
used[]đánh dấu: hình $i$ nằm trongcurthì $i$ nhỏ hơn hẳncur, không bao giờ quay lại được hình cũ (bộ test không có 2 hình trùng nhau). - Hàm
inside(i, j)dùng dấu<=: chung cạnh vẫn tính là nằm trong.
Kết quả chạy thật: đúng 99/100 test – quá thời gian test 100. Với test ngẫu nhiên thì các hình lồng nhau không nhiều nên quay lui vẫn chạy rất nhanh. Nhưng ở test 100 có 100 hình lồng liên tiếp: mọi dãy con của 100 hình đều là một dãy lồng nhau hợp lệ, tức là có tới khoảng $2^{100}$ dãy – máy chạy đến tận thế cũng không xong.
Cách 2Đệ quy có nhớ – mỗi hình chỉ tính một lần
Vì sao quay lui chậm? Vì cùng một câu hỏi "từ hình $j$ đi vào trong thì được thêm tối đa bao nhiêu hình?" bị hỏi lại rất nhiều lần, mỗi lần lại đi tìm từ đầu. Câu trả lời không phụ thuộc ta đã đi tới $j$ bằng đường nào. Vậy ta đặt hàm $f(j)$ = độ dài dãy dài nhất có hình ngoài cùng là $j$, và lưu kết quả vào memo[j]: lần sau hỏi lại thì trả lời ngay.
f= là hình đã có trong memo. Thử ví dụ "Búp bê Nga" để thấy các lời gọi lặp lại được trả lời ngay.memo[j] = 0nghĩa là chưa tính (đáp án luôn $\ge 1$ nên không lẫn được).- Không cần sắp xếp: đệ quy tự đi tìm các hình nhỏ hơn trước. Độ sâu đệ quy tối đa 100 tầng (test 100), hoàn toàn an toàn.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,005 giây. Mỗi $f(j)$ chỉ thực sự tính một lần, mỗi lần duyệt $N$ hình, tổng cộng $N^2 = 10^4$ phép kiểm tra.
Cách 3Sắp xếp + quy hoạch động bảng
Đây là cách viết "chuẩn" của quy hoạch động, đúng như widget ở phần ý tưởng: sắp xếp theo diện tích giảm dần, $f[i]$ là dãy dài nhất có hình trong cùng là $i$, chỉ cần nhìn các hình $j < i$ đứng trước.
- Diện tích có thể tới $75\,000^2 \approx 5{,}6 \cdot 10^9$ – vượt
int, nên tính bằng1LL * ...và lưulong long. - Sau khi sắp xếp, nếu hình $j$ chứa hình $i$ thì chắc chắn $j$ đứng trước $i$, nên vòng
for j < ikhông bỏ sót hình nào.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,005 giây.
Bản Python (mình viết thêm cho các bạn học Python, chấm trên cùng bộ test): cách 1 được 98/100 test – quá thời gian test 053, 100; cách 2 được 100/100 test, chậm nhất 0,032 giây; cách 3 được 100/100 test, chậm nhất 0,027 giây.
Nhận xét
Đăng nhận xét