Tuyển sinh 🎓 Mình nhận đào tạo lập trình giải thuật thi đấu: thi vào lớp 10 chuyên tin · thi học sinh giỏi tin học cấp tỉnh/thành · thi vào đội tuyển quốc gia · Olympic tin học sinh viên / ICPC · phỏng vấn thuật toán. Bấm vào đây để xem thông tin khóa học → Xem khóa học
Việt Nam Sơn
ZaloĐăng ký họcNhắn Zalo cho thầy

Triển lãm

Triển lãm
Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Trung bình Sắp xếp Tổng tiền tố Max chạy

Đề bài

Bảo tàng thành phố có $N$ bức tranh được đánh số thứ tự từ 1 đến $N$. Bức tranh thứ $i$ $(1 \le i \le N)$ có kích thước là $A_i$ và được định giá là $B_i$.

Bảo tàng sẽ trưng bày các bức tranh và muốn chọn một số bức tranh trưng bày để thu được lợi nhuận lớn nhất thoả mãn các tiêu chí:

  1. Phải trưng bày ít nhất một bức tranh;
  2. Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt;
  3. Tổng giá trị các bức tranh được trưng bày là lớn nhất.

Gọi $A_{min}$ là kích thước nhỏ nhất, $A_{max}$ là kích thước lớn nhất, $S$ là tổng giá trị của các bức tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức $H = S - (A_{max} - A_{min})$.

Yêu cầu: hãy giúp giám đốc bảo tàng tìm $H$ lớn nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên $N$ $(2 \le N \le 500000)$ là số lượng các bức tranh;
  • $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $A_i$ $(1 \le A_i \le 10^{15})$ và $B_i$ $(1 \le B_i \le 10^9)$ là kích thước và định giá của bức tranh thứ $i$.

Kết quả: số nguyên $H$ lớn nhất tìm được.

Ràng buộc: 25% số test có $n \le 16$; 25% số test có $n \le 300$; 25% số test có $n \le 5000$; 25% số test còn lại không có ràng buộc gì thêm.

Giải thích ví dụ: chọn các bức tranh 1 và 3 thì $H = (3 + 5) - (4 - 2) = 6$ là lớn nhất.

Ví dụ – input
3
2 3
9 2
4 5
Ví dụ – output
6

Lời mở đầu

Đây là một bài rất hay (gốc là bài Art Exhibition của kỳ thi JOI 2018). Hai bước mấu chốt: sắp xếp để thấy rằng chỉ cần chọn một đoạn liên tiếp, rồi tách công thức thành hai phần độc lập để chỉ cần giữ một giá trị max chạy. Mình đi từ vét cạn tập con (25%) → thử mọi cặp $O(n^2)$ (75%) → $O(n \log n)$ full điểm.

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ộ test100 testÝ tưởngsắp xếp + táchCách 12ⁿCách 2O(n²)Cách 3O(n log n)

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

Bộ test có 100 test, chia đúng 4 mức của đề (mỗi mức 25 test):

TestN$A_i$ lớn nhất$B_i$ lớn nhấtSố test có $A_i$ trùngĐáp án H
1–252 … 16202020/256 … 169
26–50300≈ 1.00·1015999.535.07025/255.163.592.268 … 18.028.652.137
51–755.000≈ 1.00·1015999.989.30125/25200.944.440.846 … 243.839.407.721
76–100500.000≈ 1.00·1015999.998.66525/2525.905.678.702.595 … 26.322.309.977.626
  • Test 1 là ví dụ của đề; test 1–25 có $A_i, B_i \le 20$ nên rất dễ kiểm tra tay.
  • Từ test 26 trở đi $A_i$ lên tới gần $10^{15}$ và có nhiều kích thước trùng nhau – code phải xử lý được $A_i$ bằng nhau (sắp xếp vẫn đúng, không cần làm gì đặc biệt).
SubtaskĐề ghiTest thậtCách 1
$O(2^n n)$		Cách 2
$O(n^2)$		Cách 3
$O(n \log n)$
25%$n \le 16$1–2525/2525/2525/25
25%$n \le 300$26–500/2525/2525/25
25%$n \le 5000$51–750/2525/2525/25
25%không ràng buộc thêm ($n \le 5 \cdot 10^5$)76–1000/250/2525/25
Bắt buộc long long
$A_i$ tới $10^{15}$ (vượt xa int), tổng giá trị tới $5 \cdot 10^5 \cdot 10^9 = 5 \cdot 10^{14}$. Đáp án lớn nhất trong bộ test là 26.322.309.977.626. Mọi biến $A$, tổng, đáp án đều phải là long long.

Ý tưởngChọn một đoạn liên tiếp sau khi sắp xếp

Bước 1 – sắp xếp. Sắp xếp các bức tranh tăng dần theo kích thước $A$. Giả sử ta đã quyết định bức nhỏ nhất là bức thứ $i$ và bức lớn nhất là bức thứ $j$ (theo thứ tự đã sắp, $i \le j$). Mọi bức nằm giữa $i$ và $j$ đều có kích thước trong $[A_i, A_j]$ nên thêm vào không làm tăng $A_{max} - A_{min}$, lại làm tăng $S$ (vì $B \ge 1$). Vậy tham lam lấy hết các bức từ $i$ đến $j$:

$$H(i, j) = (B_i + \ldots + B_j) - (A_j - A_i) = P_j - P_{i-1} - A_j + A_i$$

với $P$ là tổng tiền tố của $B$ (sau khi sắp xếp).

Bước 2 – tách công thức. Gom theo $i$ và theo $j$:

$$H(i, j) = \underbrace{(P_j - A_j)}_{\text{chỉ phụ thuộc } j} + \underbrace{(A_i - P_{i-1})}_{\text{chỉ phụ thuộc } i}$$
Thuật toán
Duyệt $j = 1..N$, giữ tot $= \max_{i \le j} (A_i - P_{i-1})$ (cập nhật thêm $i = j$ trước). Khi đó $\max_i H(i, j) = P_j - A_j + \text{tot}$. Đáp án là max của giá trị này qua mọi $j$.

Em nhập các bức tranh (mỗi bức là một cặp A B, cách nhau dấu phẩy) rồi bấm Tiếp để xem, với mỗi bức lớn nhất $j$, máy chọn bức nhỏ nhất $i$ tốt nhất ra sao:

Ví dụ nhanh:

Cách 1Vét cạn tập con – 25% điểm

Chưa cần nhận xét gì: thử mọi tập con khác rỗng (bằng mask từ 1 đến $2^n - 1$), tính $S$, $A_{min}$, $A_{max}$ rồi lấy $H$ lớn nhất.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi tập con khác rỗng bằng mask.
Dữ liệu mẫu:
Không gian$O(n)$
Thời gian$O(2^n \cdot n)$

Kết quả chạy thật: bản C++ đúng 25/100 test (sai/quá thời gian ở test 26–100), test đúng chạy lâu nhất 0.01s. Bản Python: bản Python đúng 25/100 test (sai/quá thời gian ở test 26–100), test đúng chạy lâu nhất 0.15s. Đúng trọn subtask 1; với $n = 300$ thì $2^{300}$ tập con là không tưởng (và 1 << n bị tràn số nên chương trình in ra kết quả sai).

Cách 2Sắp xếp + thử mọi cặp (i, j) – 75% điểm

Dùng bước 1 của ý tưởng: sau khi sắp xếp, chỉ cần thử mọi cặp $(i, j)$ và tính $H(i, j)$ bằng tổng tiền tố trong $O(1)$.

C++▶ Chạy tay từng dòng codeCách 2: sắp xếp, thử mọi cặp bức nhỏ nhất i – lớn nhất j.
Dữ liệu mẫu:
  1. sort một mảng pair sẽ sắp theo first (kích thước) trước – đúng điều ta cần.
  2. P[j] - P[i - 1] là tổng giá trị các bức từ $i$ đến $j$.
Không gian$O(n)$
Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 75/100 test (sai/quá thời gian ở test 76–100), test đúng chạy lâu nhất 0.02s. Bản Python: bản Python đúng 50/100 test (sai/quá thời gian ở test 51–100), test đúng chạy lâu nhất 0.04s. Với $n = 5 \cdot 10^5$ có khoảng $1{,}25 \cdot 10^{11}$ cặp nên quá thời gian.

Cách 3Sắp xếp + max chạy – Full điểm

Dùng bước 2 của ý tưởng: với mỗi $j$ không cần thử lại mọi $i$, chỉ cần nhớ giá trị $A_i - P_{i-1}$ lớn nhất đã gặp.

C++▶ Chạy tay từng dòng codeCách 3: sắp xếp, H = (P[j] − A[j]) + max(A[i] − P[i−1]), giữ max chạy.
Dữ liệu mẫu:
  1. Thứ tự 3 dòng trong vòng lặp rất quan trọng: cập nhật tot bằng p[j].first - P khi P còn là $P_{j-1}$ (cho phép $i = j$, tức chỉ chọn 1 bức), rồi mới cộng $B_j$ vào P.
  2. Không cần mảng tổng tiền tố – một biến P chạy là đủ.
  3. Độ phức tạp nằm ở bước sắp xếp $O(n \log n)$; vòng lặp chỉ $O(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.18s. Bản Python: bản Python đúng 75/100 test (sai/quá thời gian ở test 76–100), test đúng chạy lâu nhất 0.04s. Với $n = 5 \cdot 10^5$ riêng việc đọc $10^6$ số và sắp xếp đã khá nặng với Python, bản Python mất khoảng 1,3–1,5 giây nên vượt giới hạn 1 giây ở 25 test cuối – thuật toán vẫn đúng (in đúng đáp án), chỉ là Python chậm. Nộp bài thì các bạn dùng bản C++ nhé.

Tổng kếtKết quả chạy thật trên bộ test

CáchNgôn ngữĐúngTest đúng lâu nhấtGhi chú
1. Vét cạn tập conC++25/1000.01sChỉ chạy được $n \le 16$
Python25/1000.15s
2. Sắp xếp + thử mọi cặp (i, j)C++75/1000.02sQua $n \le 5000$
Python50/1000.04sPython chậm hơn nhiều
3. Sắp xếp + max chạyC++100/1000.18sFull điểm
Python75/1000.04sQuá thời gian test 76–100
Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Kỹ thuật "tách $H(i, j)$ thành $f(j) + g(i)$ rồi giữ $\max g$ chạy" dùng rất nhiều (ví dụ bài mua bán cổ phiếu một lần lãi nhất) – các bạn nhớ kỹ nhé.
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 😇

Nhận xét

Đăng nhận xét

Đăng ký: Đăng Nhận xét (Atom)