Camera

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Khá Ngăn xếp đơn điệu Đọc/ghi file

Đề bài

CAMERA

Có $n$ camera quan sát, đánh số tuần tự từ $1$ đến $n$, được đặt lần lượt thẳng hàng trên đường cao tốc từ Tây (←) sang Đông (→). Camera thứ $i$ được đặt ở độ cao $h_i$ và hướng về một trong hai hướng: Tây hoặc Đông.

Camera thứ $i$ có thể quan sát được camera thứ $j$ nếu camera thứ $i$ nhìn về phía camera thứ $j$ và không có bất kỳ camera nào ở giữa hai camera này có độ cao vượt quá độ cao của camera thứ $j$.

Yêu cầu: Cho biết độ cao và hướng nhìn của $n$ camera. Hãy cho biết mỗi camera có thể quan sát được bao nhiêu camera khác.

Dữ liệu: Vào từ file văn bản CAMERA.INP có khuôn dạng sau:

• Dòng đầu chứa số nguyên dương $n$;
• Dòng thứ hai gồm $n$ số nguyên dương $h_1, h_2, \ldots, h_n$ là độ cao của mỗi camera $(1 \le h_k \le 10^9$ với $1 \le k \le n)$;
• Dòng thứ ba chứa một xâu gồm $n$ ký tự cho biết hướng nhìn của các camera với quy ước: 'W' là nhìn sang hướng Tây, 'E' là nhìn sang hướng Đông.

Kết quả: Ghi ra file văn bản CAMERA.OUT trên một dòng $n$ số tự nhiên, số thứ $k$ cho biết số lượng camera mà camera thứ $k$ $(k = 1, 2, \ldots, n)$ có thể quan sát được.

Chú ý:

• Có $40\%$ số test có $n \le 10^2$;
• Có $20\%$ số test có $n \le 10^3$;
• Có $40\%$ số test còn lại có $n \le 10^5$.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.

Ví dụ – input

5
1 2 2 3 1
EEWWE

Ví dụ – output

3 2 1 2 0

Lưu ý: đề yêu cầu đọc/ghi file CAMERA.INP/CAMERA.OUT. Code bên dưới dùng if (fopen("CAMERA.INP", "r")) ... nên vừa chạy được với file, vừa chạy được với bàn phím/màn hình. Nếu bài này trên web vnoj không nộp được thì các bạn nộp ở link Codeforces bên dưới nhé.

Giải thích ví dụ: độ cao $1\ 2\ 2\ 3\ 1$, hướng EEWWE.

• Camera 1 nhìn Đông: thấy camera 2 (cao 2), camera 3 (cao 2 – ở giữa chỉ có camera 2 cao 2, không vượt quá 2), camera 4 (cao 3). Camera 5 cao 1 bị camera 4 cao 3 che → 3.
• Camera 2 nhìn Đông: thấy 3, 4 → 2. Camera 3 nhìn Tây: thấy 2; camera 1 cao 1 bị camera 2 che → 1.
• Camera 4 nhìn Tây: thấy 3 và 2 (bằng nhau không che nhau), camera 1 bị che → 2. Camera 5 nhìn Đông: không còn camera nào → 0.

Lời mở đầu

Bài này nghe thì giống bài hình học "ai nhìn thấy ai", nhưng thật ra chỉ là đếm trên mảng: camera $i$ nhìn Đông thấy camera $j$ khi $h_j$ không nhỏ hơn mọi độ cao đứng giữa. Đó chính là các "kỷ lục" khi đi từ $i$ ra xa – và đếm kỷ lục cho mọi điểm xuất phát là việc sở trường của ngăn xếp đơn điệu.

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

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngkỷ lụcCách 1O(n²)Cách 2ngăn xếpTổng kếtkết quả

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

Bộ test có 100 test, chia đúng theo phần "Chú ý" của đề:

Test	n	Độ cao $h$	Tỉ lệ nhìn Đông	Đáp án lớn nhất
1–20	1 … 19	1 … 20	50%	6
21–40	100	1 … 997.696.874	50%	12
41–60	1.000	1 … 999.501.588	50%	17
61–100	100.000	1 … 999.998.714	50%	31

• Test 1–20 rất nhỏ ($n \le 19$, độ cao $\le 20$, có test $n = 1$) – nhiều camera bằng độ cao nhau, dễ bắt lỗi dấu > / >=.
• Từ test 21 trở đi độ cao ngẫu nhiên tới $10^9$, hướng nhìn ngẫu nhiên, khoảng một nửa nhìn Đông.
• Đáp án nhỏ (vài chục) vì dữ liệu ngẫu nhiên, nhưng cách vét cạn vẫn phải đi tới hết dãy cho mỗi camera.

Kết quả chạy thật (giới hạn 1 giây):

Subtask	Điều kiện	Test	Cách 1 (nhìn từng camera)	Cách 2 (ngăn xếp)
1 (40%)	$n \le 10^2$	1–40	40/40	40/40
2 (20%)	$n \le 10^3$	41–60	20/20	20/20
3 (40%)	$n \le 10^5$	61–100	0/40	40/40

Ý tưởngCamera nhìn thấy = các "kỷ lục" độ cao

Xét camera $i$ nhìn Đông. Đi lần lượt $j = i + 1, i + 2, \ldots$ và giữ $mx$ = độ cao lớn nhất của các camera đã đi qua (nằm giữa $i$ và $j$). Camera $j$ được nhìn thấy khi và chỉ khi $h_j \ge mx$ – tức là $h_j$ là một kỷ lục (không giảm) tính từ $i + 1$. Đây là cách 1.

Ngăn xếp đơn điệu

Đi từ phải sang trái và giữ một ngăn xếp chứa đúng các camera mà "người đứng ngay bên trái" nhìn Đông sẽ thấy. Khi chuyển sang camera $i$:

1. Nếu $i$ nhìn Đông thì đáp án của $i$ chính là số phần tử trong ngăn xếp.
2. Sau đó $i$ đứng chắn trước: mọi camera có $h < h_i$ trong ngăn xếp sẽ bị $i$ che với mọi người ở bên trái → pop chúng. Rồi push $i$.

Ngăn xếp luôn có độ cao không giảm từ đỉnh xuống đáy. Hướng Tây làm y hệt, đi từ trái sang phải.

Để ý dấu: camera bằng độ cao không che nhau (đề nói "vượt quá"), nên chỉ pop khi $h < h_i$ (nhỏ hơn hẳn).

Em nhập độ cao và hướng rồi bấm Tiếp để xem ngăn xếp (các cột tô xanh) thay đổi:

Độ cao h = Hướng =

Ví dụ nhanh:

Cách 1Với mỗi camera, nhìn lần lượt từng camera – $O(n^2)$

Với mỗi camera $i$, đi theo hướng nhìn và đếm các camera có độ cao không nhỏ hơn $mx$ (cao nhất trong những camera đã đi qua).

C++▶ Chạy tay từng dòng codeCách 1: mỗi camera nhìn theo hướng của nó, đếm camera có độ cao ≥ max đã đi qua – O(n²).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. d = 1 nếu nhìn Đông, d = -1 nếu nhìn Tây – một vòng for dùng chung cho cả hai hướng.
2. mx bắt đầu bằng 0 (mọi độ cao đều $\ge 1$) nên camera kề bên luôn được nhìn thấy.
3. Điều kiện h[j] >= mx: bằng độ cao vẫn thấy, vì camera ở giữa chỉ che khi vượt quá $h_j$.

Không gian$O(n)$

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

Với $n = 10^5$ có khoảng $n^2/2 = 5 \cdot 10^9$ bước – 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.01s. Bản Python đúng 60/100 test, quá thời gian ở test 61–100; test đúng chạy lâu nhất 0.16s.

Cách 2Ngăn xếp đơn điệu – $O(n)$

C++▶ Chạy tay từng dòng codeCách 2: ngăn xếp đơn điệu, lượt phải→trái cho camera nhìn Đông, trái→phải cho camera nhìn Tây – O(n).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Lượt 1 đi từ $n$ về $1$: trước khi cập nhật ngăn xếp, ngăn xếp đang chứa đúng những camera bên phải $i$ mà $i$ thấy khi nhìn Đông → ans[i] = st.size().
2. Vì sao? Camera $j > i$ còn trong ngăn xếp nghĩa là chưa bị ai ở giữa (trong khoảng $i+1..j-1$) cao hơn hẳn che → $i$ thấy $j$. Camera đã bị pop thì đã có người cao hơn hẳn đứng giữa.
3. while(... h[st.top()] < h[i]) st.pop(); – dấu < (không phải <=) để camera bằng độ cao vẫn ở lại.
4. Lượt 2 đi từ $1$ tới $n$ cho các camera nhìn Tây, nhớ làm rỗng ngăn xếp trước.

Không gian$O(n)$

Thời gian$O(n)$

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

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. Nhìn từng camera, giữ max	C++	60/100	> 1s	Quá thời gian test 61–100
	Python	60/100	> 1s	Quá thời gian test 61–100
2. Ngăn xếp đơn điệu	C++	100/100	0.03s	Full điểm
	Python	100/100	0.17s	Full điểm

Ghi chú của mình: cách 1 ăn trọn 60% số test ($n \le 1000$), cách 2 dùng ngăn xếp qua hết 100 test trong khoảng 0,03 giây. Hai lỗi hay gặp nhất: dùng nhầm <= khi pop (làm mất camera bằng độ cao) và quên làm rỗng ngăn xếp giữa hai lượt.

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 😇