Cặp đôi
Đề bài
CẶP ĐÔI (PAIRS.CPP)
Có $n$ người xếp hàng dọc đánh số từ 1 tới $n$ từ đầu hàng tới cuối hàng, người thứ $i$ có chiều cao là $h_i$. Ta nói hai người $i, j$ nhìn thấy nhau nếu giữa hai người đó không tồn tại người nào khác có chiều cao $\ge \min\{h_i, h_j\}$, hay nói cách khác, tất cả những người đứng giữa người $i$ và người $j$ (nếu có) đều có chiều cao thấp hơn cả hai người này.
Yêu cầu: Đếm số cặp chỉ số $i, j$ $(i < j)$ mà hai người $i, j$ nhìn thấy nhau.
Dữ liệu:
- Dòng 1 chứa số nguyên dương $n \le 5 \cdot 10^5$.
- Dòng 2 chứa $n$ số nguyên dương $h_1, h_2, \ldots, h_n$ $(\forall i: h_i \le 10^6)$ cách nhau bởi dấu cách.
Kết quả: Ghi ra một số nguyên duy nhất là số cặp chỉ số $i, j$ $(i < j)$ mà hai người $i, j$ nhìn thấy nhau.
Subtask:
- 30% điểm đầu tiên có $n \le 10^2$.
- 30% điểm tiếp theo có $n \le 10^4$.
- 40% điểm còn lại không có giới hạn gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Dữ liệu vào/ra chuẩn (bàn phím, màn hình) dù tên đề ghi PAIRS.CPP.
6
2 1 4 3 6 575
2 2 2 2 24Lời mở đầu
Ở ví dụ 1 ($2, 1, 4, 3, 6, 5$), 7 cặp nhìn thấy nhau là: 5 cặp đứng cạnh nhau, cộng thêm cặp $(1, 3)$ (chiều cao 2 và 4, giữa là người cao 1) và cặp $(3, 5)$ (chiều cao 4 và 6, giữa là người cao 3). Cặp $(1, 5)$ thì không được vì người thứ 3 cao 4 $\ge \min(2, 6)$ che mất.
Ở ví dụ 2, năm người cao bằng nhau: hai người cạnh nhau thì luôn thấy nhau (giữa không có ai), còn hai người cách nhau thì bị người ở giữa cao bằng che mất – vì đề ghi "$\ge$". Nên đáp án chỉ là $4$. Chi tiết "bằng nhau cũng che" này rất quan trọng, lát nữa sẽ quyết định cách ta xử lý ngăn xếp.
Đây là bài kinh điển của ngăn xếp đơn điệu (monotonic stack). Mình sẽ đi từ cách vét cạn theo đúng định nghĩa, tối ưu dần, rồi tới lời giải $O(n)$ bằng ngăn xếp; cả 3 cách đều chạy thật trên bộ test chính thức.
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:
| Test | n | Chiều cao $h_i$ | Kiểu dãy | Đáp án |
|---|---|---|---|---|
| 1–20 | 5 … 15 | 1 … 30 | ngẫu nhiên, có số trùng | 5 … 24 |
| 21–30 | 100 | 1 … 997.369 | ngẫu nhiên | 186 … 192 |
| 31–60 | 10.000 | 1 … 999.962 | ngẫu nhiên, nhiều số trùng | 19.926 … 19.953 |
| 61–70 | 500.000 | 1 … 999.998 | ngẫu nhiên, nhiều số trùng | 998.002 … 998.134 |
| 71–85 | 500.000 | 1 … 500.000 | hoán vị tăng dần 1, 2, …, n | 499.999 |
| 86–100 | 500.000 | 1 … 500.000 | hoán vị giảm dần n, …, 2, 1 | 499.999 |
- Subtask trong đề khớp đúng với bộ test: test 1–30 có $n \le 100$, test 31–60 có $n = 10^4$, test 61–100 có $n = 5 \cdot 10^5$.
- 30 test cuối là dãy tăng dần $1, 2, \ldots, n$ (test 71–85) và giảm dần $n, \ldots, 2, 1$ (test 86–100). Đáp án của chúng đều là $n - 1$ (chỉ các cặp đứng cạnh nhau), nhưng như các bạn sẽ thấy ở cách 2, dãy giảm dần là "sát thủ" của các cách dừng sớm.
- Đáp án lớn nhất trong bộ test chỉ khoảng $10^6$. Thật ra với điều kiện "bằng nhau cũng che", đáp án không bao giờ vượt quá $2n$ (sẽ thấy ở cách 3), nên
intlà đủ – mình vẫn dùnglong longcho chắc tay.
Số test đúng của từng cách theo subtask (chạy thật, giới hạn 1 giây):
| Subtask | Đề ghi | Test | Cách 1 $O(n^3)$ | Cách 2 (dừng sớm) | Cách 3 (ngăn xếp) |
|---|---|---|---|---|---|
| 1 (30%) | $n \le 10^2$ | 1–30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $n \le 10^4$ | 31–60 | 30/30 | 30/30 | 30/30 |
| 3 (40%) | $n \le 5 \cdot 10^5$ | 61–100 | 0/40 | 25/40 | 40/40 |
Ý tưởngAi còn "lộ mặt" khi nhìn từ cuối hàng?
Thay vì hỏi "cặp $(i, j)$ có thấy nhau không", ta đi lần lượt từng người $j$ từ đầu hàng tới cuối hàng và hỏi: người $j$ nhìn về phía trước thấy được bao nhiêu người? Cộng tất cả lại là đáp án.
Vậy tại mỗi thời điểm, các người chưa bị gạch tên có chiều cao giảm dần nghiêm ngặt theo thứ tự đứng (người đứng sau thấp hơn hẳn người đứng trước, nếu không thì người trước đã bị gạch). Ta cất họ trong một ngăn xếp: đáy là người cao nhất đứng trước, đỉnh là người vừa vào.
- Những người thấp hơn $h$ ở đỉnh: đều thấy người mới (người đứng giữa họ và người mới đã bị gạch, tức thấp hơn họ). Đếm mỗi người 1 cặp, rồi gạch tên (pop) vì từ giờ họ bị người mới che.
- Người tiếp theo (cao $\ge h$), nếu còn: cũng thấy người mới, đếm thêm 1 cặp. Nếu người này cao bằng $h$ thì cũng bị che từ nay → pop luôn. Những người sâu hơn thì bị người này che, không thấy.
- Cuối cùng đẩy (push) người mới vào ngăn xếp.
Mỗi người được push 1 lần và pop tối đa 1 lần, nên tổng thời gian là $O(n)$. Mỗi cặp được đếm hoặc ứng với một lần pop, hoặc ứng với một người mới (tối đa 1 cặp "người cao hơn gần nhất") – vì thế đáp án $\le 2n$.
Em nhập dãy chiều cao rồi bấm Tiếp để xem ngăn xếp hoạt động. Cột xanh là người đang ở trong ngăn xếp, cột vàng là người mới tới, cột đỏ là người vừa bị gạch tên; mỗi cung nối hai người là một cặp nhìn thấy nhau (cung cam là cặp vừa đếm):
Cách 1Vét cạn theo định nghĩa – Subtask 1 (và "ăn may" subtask 2)
Duyệt mọi cặp $(i, j)$, với mỗi cặp kiểm tra từng người $k$ đứng giữa: chỉ cần một người có $h_k \ge \min(h_i, h_j)$ là cặp đó bị che.
- Biến
thayban đầu làtrue, gặp người che thì đổi thànhfalsevàbreakluôn. - Với hai người đứng cạnh nhau ($j = i + 1$) vòng
kkhông chạy lần nào, nênthaygiữ nguyêntrue– đúng như đề.
Có khoảng $\frac{n^2}{2}$ cặp, mỗi cặp tốn tới $O(n)$ bước nên tổng là $O(n^3)$: với $n = 100$ là vài trăm nghìn phép tính, nhưng $n = 10^4$ thì là $10^{12}$ – quá chậm.
Kết quả chạy thật: Bản C++ đúng 60/100 test, quá thời gian ở test 61–100; test đúng chạy lâu nhất 0.23s. Bản Python đúng 30/40 test (mình chỉ chạy test 1–40), quá thời gian ở test 31–40; test đúng chạy lâu nhất 0.02s.
Bất ngờ chưa: cách $O(n^3)$ lại qua luôn cả subtask 2, test $n = 10^4$ chỉ mất khoảng 0.2 giây! Lý do là lệnh break: với dãy ngẫu nhiên, người đứng ngay sau $i$ thường đã che rồi, nên vòng k gần như dừng ngay ở bước đầu, thực tế chỉ còn khoảng $rac{n^2}{2} = 5 \cdot 10^7$ bước. Nhưng đừng vội mừng: mình thử thêm một test tự tạo hình "thung lũng" $5000,$ $4999,$ $\ldots,$ $1,$ $1,$ $2,$ $\ldots,$ $5000$ ($n = 10^4$) – ở đó rất nhiều cặp nhìn thấy nhau qua cả thung lũng, vòng k phải chạy hết – và cách 1 chạy hơn 10 giây chưa xong. Bộ test của bài chỉ "nương tay" thôi. Còn với $n = 5 \cdot 10^5$ thì riêng số cặp $(i, j)$ đã là $1{,}25 \cdot 10^{11}$, không thể kịp.
Cách 2Giữ max ở giữa, dừng sớm – Subtask 1, 2 chắc chắn
Cố định $i$, cho $j$ chạy sang phải và giữ biến mx = chiều cao lớn nhất của những người đứng giữa $i$ và $j$. Không cần vòng $k$ nữa: cặp $(i, j)$ thấy nhau khi và chỉ khi mx < min(h[i], h[j]). Thêm nữa, theo nhận xét 1, một khi mx >= h[i] thì $i$ bị che với mọi người phía sau → break.
- Thứ tự trong vòng $j$ rất quan trọng: kiểm tra cặp $(i, j)$ trước, rồi mới đưa $h_j$ vào
mx(vì $j$ chỉ là "người đứng giữa" đối với các $j$ sau). - Ban đầu
mx = 0(giữa chưa có ai) – mọi $h_i \ge 1$ nên cặp đứng cạnh nhau luôn được đếm.
Không có break thì đây là $O(n^2)$ tròn trịa, đủ cho $n = 10^4$ với mọi kiểu dữ liệu (test "thung lũng" ở trên chạy chưa tới 0.1 giây). Có break thì với dãy ngẫu nhiên hay dãy tăng dần, vòng $j$ dừng rất sớm (gặp ngay người cao hơn $h_i$), nên chạy gần như $O(n)$. Nhưng với dãy giảm dần, không ai phía sau cao hơn $h_i$, vòng $j$ luôn chạy tới cuối hàng → vẫn là $O(n^2) \approx 1{,}25 \cdot 10^{11}$ phép tính.
Kết quả chạy thật: Bản C++ đúng 85/100 test, quá thời gian ở test 86–100; test đúng chạy lâu nhất 0.06s. Bản Python đúng 75/100 test, quá thời gian ở test 61–70, 86–100; test đúng chạy lâu nhất 0.45s. Đúng như dự đoán: dừng sớm giúp "ăn ké" thêm các test lớn ngẫu nhiên và tăng dần, nhưng gục ở 15 test giảm dần.
Cách 3Ngăn xếp đơn điệu – Full điểm
Cài đặt đúng nhận xét 2. Ngăn xếp chỉ cần lưu chiều cao (không cần chỉ số), và ta có thể đọc tới đâu xử lý tới đó, không cần lưu mảng $h$.
- Vòng
while: các người ở đỉnh thấp hơn $h$ thấy người mới →dem++, rồi pop vì từ nay bị che. - Sau vòng
while, nếu ngăn xếp còn người thì người ở đỉnh cao $\ge h$ – người cao hơn hoặc bằng gần nhất phía trước – cũng thấy người mới →dem++. - Dòng
if(st.top() == h) st.pop();xử lý trường hợp cao bằng nhau: người đó thấy người mới nhưng từ nay bị người mới che (vì "$\ge$"). Nếu quên dòng này, ví dụ 2 sẽ ra $1 + 2 + 2 + 2 = 7$ thay vì $4$. Nhờ dòng này ngăn xếp luôn giảm dần nghiêm ngặt.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.05s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.33s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Vét cạn $O(n^3)$ | C++ | 60/100 | > 1s | quá thời gian test 61–100 |
| Python | 30/40 | > 1s | Chạy test 1–40; quá thời gian test 31–40 | |
| 2. Giữ max ở giữa + dừng sớm | C++ | 85/100 | > 1s | quá thời gian test 86–100 |
| Python | 75/100 | > 1s | quá thời gian test 61–70, 86–100 | |
| 3. Ngăn xếp đơn điệu | C++ | 100/100 | 0.05s | full điểm |
| Python | 100/100 | 0.33s | full điểm |
long long.
Nhận xét
Đăng nhận xét