Chia dãy (Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B, C2)

Nguồn: Tin học trẻ 2024 Độ khó: Khó Quy hoạch động Ngăn xếp đơn điệu Hàng đợi 2 đầu Hai con trỏ

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B và Bảng C2 (bài Chia dãy). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho dãy số nguyên dương $a_1, a_2, \dots, a_n$ và số nguyên $s$. Hãy chia dãy thành các đoạn liên tiếp (mỗi phần tử thuộc đúng một đoạn) sao cho tổng mỗi đoạn không vượt quá $s$.

Đoạn bắt đầu ở vị trí $l$, kết thúc ở vị trí $r$ có chi phí

$$c(l, r) = \max(a_l, a_{l+1}, \dots, a_r) + (r - l).$$

Hãy tìm cách chia có tổng chi phí nhỏ nhất.

Ví dụ dãy $[3, 1, 5, 2, 1, 4]$ với $s = 7$ chia thành $[3, 1]$, $[5]$, $[2, 1, 4]$ có tổng chi phí $(3 + 1) + (5 + 0) + (4 + 2) = 15$.

Dữ liệu vào:

Dòng 1: hai số nguyên $n, s$ ($1 \le n \le 2 \cdot 10^6$; $1 \le s \le 10^{18}$).
Dòng 2: $n$ số nguyên $a_1, \dots, a_n$ ($1 \le a_i \le \min(s, 10^9)$).

Kết quả: một số nguyên là tổng chi phí nhỏ nhất.

Subtask:

Subtask 1 (20%): $n \le 500$;
Subtask 2 (20%): $n \le 5000$;
Subtask 3 (30%): $n \le 2 \cdot 10^5$;
Subtask 4 (30%): không có ràng buộc gì thêm.

Giới hạn thời gian: 0,5 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

6 7
3 1 5 2 1 4

Ví dụ – output

Lời mở đầu

Đây là bài khó nhất Bảng B vòng chung kết 2024. Công thức quy hoạch động thì ai cũng viết được ngay ($O(n^2)$, 40 điểm). Cái khó nằm ở chỗ tăng tốc tới $n = 2 \cdot 10^6$ trong 0,5 giây: mình sẽ đổi lại hàm chi phí một chút, dùng ngăn xếp đơn điệu gom các vị trí cắt cùng "max", rồi lấy min các ứng viên bằng multiset ($O(n \log n)$) và cuối cùng là hàng đợi hai đầu có min ($O(n)$). Bài gốc kiểu này còn có tên "Cut the Sequence" (POJ 3017).

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ộ test25 test Cách 1O(n²) – 40đ Ý tưởngđổi chi phí Cách 2multiset Cách 3O(n) – 100đ Tổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 25 test (test 1 là ví dụ của đề). Có dãy ngẫu nhiên, dãy tăng, dãy giảm, dãy "răng cưa", dãy hầu hết nhỏ xen vài đỉnh lớn, dãy hằng; $s$ có thể rất chặt ($s = \max a$, mỗi đoạn chỉ 1–2 phần tử) hoặc rất rộng ($s \ge$ tổng cả dãy).

Nhóm	Test	$n$ lớn nhất	$s \ge$ tổng dãy (1 đoạn là đủ)	$s = \max a$ (đoạn rất ngắn)	Đoạn dài $\ge 1000$ phần tử	Đáp án lớn nhất
Subtask 1	1–6	500	test 5	test 3	không có	128.785.396.927
Subtask 2	7–11	5.000	test 10	không có	không có	554.062.625.153
Subtask 3	12–18	200.000	test 18	test 13	test 16	87.698.340.778.283
Subtask 4	19–25	2.000.000	test 23	test 24	test 21	20.103.001.781.246

Các test $n = 2 \cdot 10^6$ có dữ liệu vào tới khoảng 20 MB – đọc bằng cin thường cũng mất cả trăm mili giây, nên lời giải cuối dùng fread. Đáp án tới khoảng $2 \cdot 10^{15}$, cần long long.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng trong bài mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 $O(n^2)$ C++	Cách 1 Python	Cách 2 multiset C++	Cách 2 Python	Cách 3 $O(n)$ C++
Subtask 1 (20%)	$n \le 500$	1–6	6/6	6/6	6/6	6/6	6/6
Subtask 2 (20%)	$n \le 5000$	7–11	5/5	4/5	5/5	5/5	5/5
Subtask 3 (30%)	$n \le 2 \cdot 10^5$	12–18	4/7	1/7	7/7	7/7	7/7
Subtask 4 (30%)	$n \le 2 \cdot 10^6$	19–25	3/7	0/7	7/7	0/7	7/7

Cách 1Quy hoạch động thẳng – O(n²) (Subtask 1, 2)

Gọi $dp[i]$ = tổng chi phí nhỏ nhất khi chia xong $i$ phần tử đầu ($dp[0] = 0$). Đoạn cuối là $[l, i]$:

$$dp[i] = \min_{l:\ a_l + \dots + a_i \le s} \Big( dp[l-1] + \max(a_l..a_i) + (i - l) \Big).$$

Cho $l$ lùi dần từ $i$, cộng dồn tổng và max; tổng vượt $s$ thì dừng (vì $a_i > 0$, lùi tiếp tổng càng lớn).

C++▶ Chạy tay từng dòng codeCách 1: dp[i] = min theo đoạn cuối [l, i] có tổng ≤ s.

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

Dữ liệu mẫu:

Không gian$O(n)$

Thời gian$O(n^2)$ (đúng hơn: $O(n \cdot L)$)

Kết quả chạy thật: Bản C++ đúng 18/25 test, quá thời gian test 14, 16, 18–21, 23 (các test đúng chạy lâu nhất 0.345s). Bản Python đúng 11/25 test, quá thời gian test 10, 12, 14–25 (các test đúng chạy lâu nhất 0.160s). Bản C++ ăn trọn subtask 1, 2 (40 điểm). Thú vị là nó còn qua nhiều test lớn khi $s$ chặt (mỗi đoạn chỉ vài phần tử nên vòng $l$ dừng sớm) – độ phức tạp thật là $O(n \cdot L)$ với $L$ là độ dài đoạn dài nhất có thể. Các test $s$ rộng thì quá thời gian.

Ý tưởngĐổi chi phí, gom các vị trí cắt cùng max

Bước 1 – đổi chi phí. Tổng các $(r - l)$ của mọi đoạn bằng $n - (\text{số đoạn})$. Vậy

$$\text{tổng chi phí} = n + \sum_{\text{đoạn}} \big(\max - 1\big).$$

Gọi $g[i]$ = min $\sum (\max - 1)$ khi chia $i$ phần tử đầu, đáp án là $g[n] + n$, và

$$g[i] = \min_{lo_i \le j < i} \Big( g[j] + \max(a_{j+1}..a_i) - 1 \Big),$$

với $lo_i$ là $j$ nhỏ nhất thoả $P_i - P_j \le s$ ($P$ là tổng tiền tố). Khi $i$ tăng, $lo_i$ chỉ tăng – hai con trỏ.

Nhận xét 1: $g$ không giảm

Bỏ phần tử $i$ khỏi đoạn cuối của một cách chia tối ưu cho $i$ phần tử: max của đoạn không tăng (hoặc đoạn biến mất, bớt đi một số hạng $\max - 1 \ge 0$). Ta được một cách chia $i - 1$ phần tử không tệ hơn, nên $g[i-1] \le g[i]$. (Đây là lý do phải đổi chi phí: với $dp$ gốc có thêm số hạng $-j$ nên không dùng được nhận xét này một cách gọn gàng.)

Nhận xét 2: gom các $j$ cùng max bằng ngăn xếp đơn điệu

Giữ ngăn xếp các vị trí $st_1 < st_2 < \dots$ trong cửa sổ có $a$ giảm dần (khi thêm $i$, bỏ các đỉnh có $a \le a_i$). Với $j$ thuộc khối $[st_{k-1}, st_k - 1]$ thì $\max(a_{j+1}..a_i) = a_{st_k}$ – không đổi trong khối. Vì $g$ không giảm, trong khối chỉ cần $j$ nhỏ nhất: ứng viên của khối là $$g[st_{k-1}] + a_{st_k} - 1.$$ Riêng khối đầu bị cửa sổ cắt nên dùng $j = lo$: ứng viên $g[lo] + a_{st_{head}} - 1$.

Vậy $g[i]$ = min của tất cả ứng viên. Các ứng viên chỉ bị thêm/bớt ở cuối (khi đẩy/bỏ đỉnh ngăn xếp) và bớt ở đầu (khi cửa sổ dịch) – cần một cấu trúc lấy min nhanh: multiset (Cách 2) hoặc hàng đợi hai đầu có min (Cách 3).

Em nhập dãy rồi bấm Tiếp: mỗi bước thêm một phần tử $i$, các ô cùng màu nền là một khối $j$ chung max (đỉnh khối viền đậm), vùng mờ là các $j$ ngoài cửa sổ:

s = Dãy a =

Ví dụ nhanh:

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

Dùng deque<int> q làm ngăn xếp đơn điệu (bỏ ở cuối khi thêm, bỏ ở đầu khi cửa sổ dịch) và multiset chứa ứng viên của mọi đỉnh trừ đỉnh đầu.

C++▶ Chạy tay từng dòng codeCách 2: deque q là ngăn xếp đơn điệu (a giảm dần), multiset ms chứa ứng viên của các đỉnh trừ đỉnh đầu (ô xanh = nhỏ nhất).

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

Dữ liệu mẫu:

Khi bỏ đỉnh b ở cuối, ứng viên của nó là g[đỉnh trước] + a[b] - 1 – xoá đúng một bản sao bằng ms.erase(ms.find(...)) (viết ms.erase(giá_trị) sẽ xoá hết các bản sao bằng nhau – sai!).
Khi bỏ đỉnh đầu f, đỉnh đầu mới mất ứng viên "chuẩn" của nó (vì khối của nó giờ bị cửa sổ cắt) – xoá g[f] + a[q.front()] - 1.
Mỗi chỉ số vào/ra deque và multiset tối đa một lần: $O(n \log n)$.

Không gian$O(n)$

Thời gian$O(n \log n)$

Kết quả chạy thật: Bản C++ đúng 25/25 test, chạy lâu nhất 0.402s – trên máy mình vẫn full, nhưng test lớn nhất mất 0,40 giây so với giới hạn 0,5 giây: khá sát, trên máy chấm chậm hơn có thể bị quá thời gian. Bản Python đúng 18/25 test, quá thời gian test 19–25 (các test đúng chạy lâu nhất 0.461s) (Python không có multiset nên mình dùng heap với "xoá lười") – qua subtask 1, 2, 3.

Cách 3Hàng đợi hai đầu có min bằng hai ngăn xếp – O(n) (full, an toàn)

Thay multiset bằng một hàng đợi hai đầu có lấy min: ghép hai ngăn xếp "có min" quay lưng vào nhau – ngăn trước (đỉnh là đầu hàng đợi) và ngăn sau (đỉnh là cuối hàng đợi). Mỗi phần tử lưu kèm min của ngăn tính từ đáy tới nó, nên min cả hàng đợi là min(fm.back(), bm.back()).

push_back: đẩy vào ngăn sau. pop_back / pop_front: lấy ở đỉnh ngăn tương ứng.
Nếu ngăn cần lấy đang rỗng, chia đôi các phần tử của ngăn kia sang hai ngăn (hàm chia). Chia đôi (chứ không dồn hết sang) là mấu chốt để tổng chi phí vẫn là $O(n)$ khấu trừ, kể cả khi pop_front và pop_back xen kẽ nhau.

C++▶ Chạy tay từng dòng codeCách 3: ngăn xếp đơn điệu st[head..top] + hàng đợi hai đầu dq ghép từ hai ngăn xếp có min (fv/fm: ngăn trước, bv/bm: ngăn sau).

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

Dữ liệu mẫu:

readInt đọc cả file một lần bằng fread rồi tự tách số – nhanh hơn cin nhiều lần với 2 triệu số.
Ngăn xếp đơn điệu cài bằng mảng st với hai đầu head, top; trong dq lần lượt là ứng viên của st[head+1..top] (đỉnh đầu không có ứng viên trong dq).
Khi bỏ đỉnh đầu (head++), đỉnh đầu mới cũng phải bỏ ứng viên của nó ra khỏi dq – đó chính là phần tử đầu của dq.

Không gian$O(n)$

Thời gian$O(n)$ khấu trừ

Kết quả chạy thật: Bản C++ đúng 25/25 test, chạy lâu nhất 0.148s. Nhanh gần gấp 3 lần Cách 2 – full điểm với khoảng dư thời gian thoải mái.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
1. QHĐ thẳng $O(n^2)$	C++	18/25	0.345s	40%
	Python	11/25	0.160s	20%
2. Ngăn xếp đơn điệu + multiset $O(n \log n)$	C++	25/25	0.402s	100%
	Python (heap)	18/25	0.461s	70%
3. Ngăn xếp đơn điệu + hàng đợi 2 đầu có min $O(n)$	C++	25/25	0.148s	100%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 0,5 giây). Mình còn đối chiếu ba cách với nhau trên 400 bộ dữ liệu ngẫu nhiên nhỏ – kết quả khớp hoàn toàn. Chuỗi kỹ thuật của bài rất đáng học: biến đổi hàm chi phí để có tính đơn điệu → ngăn xếp đơn điệu gom các trạng thái cùng max → cấu trúc lấy min trên tập ứng viên thay đổi ở hai đầu. Trong phòng thi, Cách 2 (multiset) là lựa chọn dễ cài hơn; Cách 3 là "bảo hiểm" khi giới hạn thời gian chặ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 😇

Lập Trình Thuật Toán