Che mát cho vườn
Đề bài
Đề thi học sinh giỏi Tin học lớp 9 TP.HCM năm 2021.
Vua có khu vườn hình bàn cờ với $M$ hàng và $N$ cột. Mỗi ô đặt một cây, mỗi cây có chiều cao riêng. Vua đưa cho trạng Tí các tấm lợp vuông kích thước $2 \times 2$ để làm mái lọng và yêu cầu Tí bố cục lại khu vườn, đặt các cây chống mái lọng che mát cho toàn bộ khu vườn.
Đầu tiên, Tí quy hoạch vườn thành từng cụm nhỏ với kích thước $2 \times 2$ vừa với một tấm lợp. Các cụm được đánh số tăng dần theo thứ tự từ trên xuống dưới và từ trái qua phải. Phần ở bìa dưới và bìa phải của khu vườn nếu không đủ kích thước vẫn được tính là một cụm. Ví dụ khu vườn kích thước $3 \times 5$ được quy hoạch thành 6 cụm theo thứ tự:
Tiếp theo, Tí sắp xếp lại cây trong vườn theo chiều cao cây giảm dần, đặt từ trên xuống dưới và từ trái qua phải trong từng cụm. Bắt đầu từ cụm 1, đặt xong sang cụm 2, … cho đến cụm cuối. Ví dụ khu vườn $3 \times 5$ với chiều cao các cây ban đầu (trái) và sau khi sắp xếp (phải):
Sau đó, Tí phải tính được chiều cao của các cây chống lọng. Cây chống lọng phải cao hơn chiều cao của cây cao nhất trong cụm đang che mát 1 đơn vị. Các cây chống lọng lắp đặt theo thứ tự cụm đã quy hoạch.
Tuy nhiên, nếu số hàng hoặc số cột của khu vườn là số lẻ thì các cụm ở bìa dưới hoặc bìa phải của khu vườn sẽ có phần mái lọng che luôn cả những cây ở hàng liền trên hoặc ở cột kế bên. Lúc này, khả năng sẽ có các tấm che chồng lên nhau. Nếu các cây chống lọng chồng lên nhau có chiều cao bằng nhau thì cây chống lọng lắp đặt sau phải tăng chiều cao thêm 1 đơn vị. Ví dụ xét khu vườn sau khi sắp xếp lại các cây như sau:
| 8 | 5 |
| 8 | 3 |
| 2 | 1 |
– Cây chống lọng thứ nhất cao 9 (do che 4 cây có chiều cao 8, 8, 5, 3 → $8 + 1 = 9$).
– Cây chống lọng thứ hai cao 10 (do che 4 cây có chiều cao 8, 2, 3, 1 → ban đầu là $8 + 1 = 9$ nhưng do chồng lên cây chống lọng thứ nhất nên có chiều cao là $9 + 1 = 10$).
Yêu cầu: em hãy giúp trạng Tí sắp xếp lại vườn, cho biết số lượng tấm lợp lọng cần dùng và chiều cao của từng cây chống lọng.
Dữ liệu vào:
- Dòng đầu tiên ghi 2 số nguyên dương $M, N$ $(2 \le M, N \le 10^3)$ tương ứng với số hàng và cột của vườn.
- $M$ dòng tiếp theo, mỗi dòng ghi $N$ số nguyên dương cho biết chiều cao của cây tại vị trí hàng $i$, cột $j$ $(1 \le A_{ij} \le 100)$.
Kết quả:
- $M$ dòng đầu tiên mỗi dòng ghi $N$ số nguyên dương lần lượt là chiều cao của các cây trong khu vườn sau khi đã sắp xếp lại.
- Dòng kế cuối ghi một số nguyên dương $K$ cho biết số tấm lợp lọng cần dùng.
- Dòng cuối cùng ghi $K$ số nguyên dương tương ứng với chiều cao của $K$ cây chống lọng theo thứ tự cụm đã đánh số.
Lưu ý: các số trên cùng dòng cách nhau một khoảng trắng. Đề gốc đọc/ghi file CHEVUON.INP/CHEVUON.OUT, còn trên CLUE OJ bài này đọc từ bàn phím (stdin) và ghi ra màn hình (stdout).
2 2
3 6
5 46 4
5 3
1
73 2
1 3
8 2
5 88 5
8 3
2 1
2
9 10Lời mở đầu
Bài này thuần mô phỏng nhưng đề viết khá "đánh đố": cụm đánh số theo cột (đi xuống trước rồi mới sang phải), trong mỗi cụm cây cũng đặt theo cột, và tấm lợp ở bìa thì bị dời đi. Mình sẽ "giải mã" từng câu chữ của đề bằng ví dụ, kiểm chứng trên toàn bộ 100 test, rồi đi từ cách sắp xếp đơn giản tới cách đếm phân phối chạy trong chớp mắt.
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ì?
Bộ test có 100 test, đề không chia subtask. Theo kích thước có 3 nhóm rõ rệt:
| Test | Số test | $M \times N$ lớn nhất | $A_{ij}$ | Có $M$ hoặc $N$ lẻ | Cả $M$ và $N$ lẻ (có cụm góc) |
|---|---|---|---|---|---|
| 1 – 40 | 40 | 10 × 9 | 1 – 10 | 27 | 7 |
| 41 – 60 | 20 | 96 × 97 | 1 – 100 | 15 | 5 |
| 61 – 100 | 40 | 1000 × 1000 | 1 – 100 | 18 | 5 |
- Test 1 – 40: vườn nhỏ (tối đa $10 \times 10$), chiều cao chỉ từ 1 tới 10 nên có rất nhiều cây cao bằng nhau – tức là rất nhiều tình huống cây chống lọng bằng nhau phải +1.
- Test 41 – 60: tới $100 \times 100$, chiều cao 1 – 100.
- Test 61 – 100: tới $1000 \times 1000$ (20 test cuối đều đúng $1000 \times 1000$, tức $10^6$ cây và $250\,000$ tấm lợp). Output dài tới $10^6$ số nên cần in nhanh.
- 17 test có cả $M$ và $N$ đều lẻ (test 4, 11, 12, 19, 29, 37...) – có một cụm góc chỉ gồm 1 cây, trường hợp mà đề không mô tả rõ (xem phần ý tưởng).
Mình tự chia 3 mức theo kích thước; kết quả chạy thật (giới hạn 1 giây):
| Nhóm | Test | Điều kiện | Cách 1 sắp xếp chọn | Cách 2sort | Cách 3 đếm phân phối | Python cách 2 | Python cách 3 |
|---|---|---|---|---|---|---|---|
| Nhóm 1 | 1 – 40 | $M, N \le 10$ | ✔ | ✔ | ✔ | ✔ | ✔ |
| Nhóm 2 | 41 – 60 | $M, N \le 100$ | ✔ | ✔ | ✔ | ✔ | ✔ |
| Nhóm 3 | 61 – 100 | $M, N \le 1000$ | ✘ đúng 1/40 còn lại TLE | ✔ | ✔ | ✘ đúng 19/40 còn lại TLE | ✘ đúng 18/40 còn lại TLE |
Ý tưởngGiải mã đề bằng ví dụ
1. Thứ tự cụm. Hình $3 \times 5$ ở trên đánh số cụm 1, 2 ở cột đầu rồi 3, 4 ở cột giữa… nghĩa là các cụm được duyệt theo cột: với vườn có $R = \lceil M/2 \rceil$ hàng cụm và $C = \lceil N/2 \rceil$ cột cụm, cụm ở hàng cụm $ci$, cột cụm $cj$ (đếm từ 0) có số thứ tự $cj \cdot R + ci + 1$.
2. Thứ tự trong cụm. Cụm 3 của ví dụ nhận 4 cây 5, 4, 3, 3 và đáp án đặt chúng thành 5 3 / 4 3: số 4 nằm dưới số 5. Vậy trong cụm cũng đặt theo cột: ô trên trái, ô dưới trái, ô trên phải, ô dưới phải. Ví dụ 1 của đề (3 6 / 5 4 → 6 4 / 5 3) cũng khẳng định điều này.
3. Tấm lợp ở bìa. Cụm ở bìa dưới khi $M$ lẻ chỉ có 1 hàng, tấm lợp $2 \times 2$ của nó được dời lên 1 hàng (che cả hàng $M-1$) và chồng lên tấm lợp của cụm ngay trên. Tương tự cụm ở bìa phải khi $N$ lẻ được dời sang trái 1 cột và chồng lên tấm lợp của cụm ngay bên trái. Chiều cao cây chống lọng = cây cao nhất dưới tấm lợp + 1; nếu bằng chiều cao cây chống lọng mà nó chồng lên thì +1 (lặp lại cho tới khi khác).
4. Cụm góc dưới phải (khi cả $M$ và $N$ lẻ, cụm chỉ có 1 cây). Đề không nói rõ, mình thử nhiều cách hiểu và đối chiếu với đáp án của bộ test thì cách duy nhất khớp cả 17 test là: tấm lợp của cụm góc chỉ dời sang trái (che cây góc và cây bên trái nó trên hàng cuối), và chiều cao được so với cây chống lọng của cả cụm trên lẫn cụm trái. Ví dụ vườn $3 \times 3$ 4 6 2 / 8 1 3 / 5 7 2, sau sắp xếp là 8 6 2 / 7 5 2 / 4 3 1, theo cách hiểu này có đáp án 9 8 7 4: cây chống lọng của cụm góc là $\max(3, 1) + 1 = 4$. Nếu dời tấm lợp góc cả lên trên lẫn sang trái thì sẽ ra $\max(5, 2, 3, 1) + 1 = 6$ – cách hiểu đó làm sai nhiều test có cụm góc.
Em sửa khu vườn rồi bấm Tiếp để xem từng bước rót cây vào cụm và lắp cây chống lọng (viền xanh là tấm lợp đang lắp):
Cách 1Sắp xếp chọn – O((MN)²)
Đưa cả $M \cdot N$ chiều cao vào một mảng v, sắp xếp giảm dần bằng sắp xếp chọn (mỗi lượt tìm số lớn nhất còn lại đưa lên đầu), rồi làm đúng 3 bước ở phần ý tưởng.
- 4 vòng lặp
cj → ci → c → rrót cây theo đúng thứ tự: cụm theo cột, trong cụm cũng theo cột.min(2 * cj + 1, N - 1)xử lý cụm thiếu cột ở bìa phải, tương tự với hàng. day= cụm ở bìa dưới và thiếu hàng ($2 \cdot ci = M - 1$),phai= cụm ở bìa phải và thiếu cột. Cụm bìa phải dời tấm lợp sang trái; chỉ khi không ở bìa phải mới dời lên (cụm góc chỉ dời sang trái).- Cụm thứ
k(đếm từ 0): cụm ngay trên làk - 1, cụm ngay bên trái làk - Rvì mỗi cột cụm có $R$ cụm. - Sắp xếp chọn tốn khoảng $\frac{(MN)^2}{2}$ phép so sánh: với $10^6$ cây là $5 \cdot 10^{11}$ – không thể chạy kịp.
Kết quả chạy thật: đúng 61/100 test (39 test có vườn lớn nhất bị quá thời gian), test đúng chậm nhất 0.90 giây.
Cách 2Dùng sort – O(MN log MN)
Chỉ cần thay đoạn sắp xếp chọn bằng hàm sort của thư viện với greater<int>() để sắp giảm dần:
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.22 giây. Bản Python: đúng 79/100 test (21 test có vườn lớn nhất bị quá thời gian), test đúng chậm nhất 0.92 giây.
Cách 3Đếm phân phối – O(MN + 100)
Chiều cao chỉ từ 1 tới 100, nên không cần sắp xếp: đếm cnt[x] = số cây cao $x$. Khi rót cây, giữ biến cao bắt đầu từ 100; ô nào cần cây thì bỏ qua các chiều cao đã hết (cnt[cao] == 0) rồi lấy một cây cao cao.
- Biến
caochỉ giảm, tổng cộng giảm tối đa 100 lần, nên phần rót cây chỉ tốn $O(MN + 100)$. - Không cần lưu mảng
v$10^6$ phần tử, chỉ cần mảng đếm 101 ô.
Kết quả chạy thật: đúng 100/100 test, test đúng chậm nhất 0.18 giây. Bản Python: đúng 78/100 test (22 test có vườn lớn nhất bị quá thời gian), test đúng chậm nhất 0.82 giây.
Nhận xét
Đăng nhận xét