Chia dãy số (Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng C1, C2)

Nguồn: Tin học trẻ 2023 Độ khó: Khó Tham lam Quy hoạch động Cây Fenwick Mex

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng C1, C2 (bài Chia dãy số). Miền Bắc và miền Nam thi chung một đề, miền Trung có đề riêng. Đề 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).

Alice có dãy số nguyên không âm $a_1, a_2, \dots, a_n$. Một cách chia dãy thành $k$ đoạn liên tiếp $(l_1, r_1),$ $(l_2, r_2),$ $\dots,$ $(l_k, r_k)$ gọi là $x$-đẹp nếu:

• mỗi vị trí $i$ ($1 \le i \le n$) thuộc đúng một đoạn;
• với mỗi đoạn, số tự nhiên nhỏ nhất không xuất hiện trong đoạn đó (gọi là mex của đoạn) không vượt quá $x$.

Yêu cầu: với mỗi $x = 0, 1, \dots, n - 1$, tìm số đoạn $k$ nhỏ nhất của một cách chia $x$-đẹp.

Dữ liệu vào: dòng 1 là $n$ ($1 \le n \le 10^6$); dòng 2 gồm $n$ số $a_1, \dots, a_n$ ($0 \le a_i \le 10^6$).

Kết quả: $n$ dòng, dòng thứ $x + 1$ là số đoạn ít nhất của cách chia $x$-đẹp; nếu không có cách chia nào thì in $-1$.

Subtask:

• Subtask 1 (20%): $n \le 100$;
• Subtask 2 (20%): $n \le 3000$;
• Subtask 3 (20%): $n \le 2 \cdot 10^5$;
• Subtask 4 (20%): $k \le 20$ với mọi $0 \le x \le n - 1$;
• Subtask 5 (20%): không có ràng buộc gì thêm.

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

Ví dụ – input

5
2 0 1 0 3

Ví dụ – output

-1
3
2
2
1

Giải thích (đề gốc không có phần này, mình tự thêm):

• $x = 0$: đoạn chứa số $0$ (phần tử $a_2$) luôn có mex $\ge 1$ → không chia được, in $-1$.
• $x = 1$: chia thành $[2], [0], [1, 0, 3]$? Không được, vì $[1, 0, 3]$ có mex $2$. Cách chia 3 đoạn đúng là $[2, 0], [1], [0, 3]$ (mex lần lượt $1, 0, 1$).
• $x = 2$: $[2, 0], [1, 0, 3]$ (mex $1$ và $2$).
• $x = 3$: $[2, 0, 1, 0], [3]$ (mex $3$ và $0$).
• $x = 4$: để nguyên cả dãy, mex bằng $4$.

Lời mở đầu

Bài này có hai lớp: lớp thứ nhất là nhận ra tham lam đúng (kéo mỗi đoạn dài nhất có thể), lớp thứ hai là làm tham lam đó cho tất cả $n$ giá trị $x$ cùng lúc mà vẫn nhanh. Mình đi từ quy hoạch động $O(n^3)$, tới tham lam $O(n^2)$, rồi tới lời giải $O(n \log n)$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test20 testÝ tưởngtham lamCách 1QHĐ – 20đCách 2tham lam – 40đCách 3song song – 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ệ điểm subtask của đề: 20 test (test 1 là ví dụ). Mình hiểu subtask 4 "$k \le 20$ với mọi $x$" là mọi đáp án khác $-1$ đều không quá 20 (đáp án của $x = 0$ có thể là $-1$). Cột $M$ (mex của cả dãy) rất quan trọng: như phần ý tưởng sẽ thấy, chỉ các $x < M$ mới cần tính.

Subtask	Test	$n$	$\max a_i$	mex cả dãy $M$	Đáp án lớn nhất	Số đáp án $-1$
Subtask 1	1	5	3	4	3	1
	2	1	0	1	-1	1
	3	100	6	7	10	1
	4	100	1	2	100	1
Subtask 2	5	3.000	2.999	3.000	2	1
	6	3.000	5	6	491	1
	7	3.000	6	7	656	1
	8	3.000	3	0	1	0
Subtask 3	9	200.000	20	21	9.594	1
	10	200.000	299	300	1.013	1
	11	200.000	240	162	9.716	1
	12	200.000	199.999	200.000	2	1
Subtask 4	13	1.000.000	1.000.000	50.000	11	1
	14	1.000.000	999.999	1.000.000	2	1
	15	1.000.000	999.999	300.000	3	1
	16	1.000.000	1.000.000	10	14	1
Subtask 5	17	1.000.000	3	4	250.643	1
	18	1.000.000	999	1.000	1.493	1
	19	1.000.000	19	20	500.001	1
	20	1.000.000	1.465	769	9.885	1

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

Lời giải cuối cùng (cách 3) 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 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++
Subtask 1 (20%)	$n \le 100$	1–4	4/4	4/4	4/4	4/4	4/4
Subtask 2 (20%)	$n \le 3000$	5–8	0/4	0/4	4/4	4/4	4/4
Subtask 3 (20%)	$n \le 2 \cdot 10^5$	9–12	0/4	0/4	3/4	1/4	4/4
Subtask 4 (20%)	$k \le 20$ với mọi $x$	13–16	0/4	0/4	1/4	1/4	4/4
Subtask 5 (20%)	không ràng buộc thêm ($n \le 10^6$)	17–20	0/4	0/4	2/4	1/4	4/4

Ý tưởngĐoạn hợp lệ là đoạn thiếu ít nhất một số trong 0..x

mex của đoạn $\le x$ $\iff$ đoạn không chứa đủ các giá trị $0, 1, \dots, x$. Từ đây:

• Đóng với đoạn con: đoạn hợp lệ thì mọi đoạn con của nó cũng hợp lệ (đã thiếu một giá trị thì đoạn con càng thiếu).
• Tham lam đúng: đi từ trái sang, kéo dài đoạn hiện tại tới khi thêm phần tử tiếp theo sẽ làm đoạn chứa đủ $0..x$ thì cắt, mở đoạn mới tại phần tử đó. Lý do: so với một cách chia tối ưu bất kỳ, đoạn tham lam thứ $t$ luôn kết thúc ở vị trí không sớm hơn đoạn thứ $t$ của cách kia (vì phần đuôi một đoạn hợp lệ cũng hợp lệ) – nên tham lam không dùng nhiều đoạn hơn.
• $x = 0$: đoạn chứa số $0$ có mex $\ge 1$, nên có số 0 trong dãy thì in $-1$, không thì in $1$ (cả dãy có mex $= 0$).
• $x \ge M$ ($M$ = mex cả dãy): cả dãy là một đoạn hợp lệ → in $1$.

Em nhập dãy và $x$ rồi bấm Tiếp để xem tham lam cắt đoạn (ô xanh = các giá trị $0..x$ đoạn hiện tại đã có):

Dãy a = x =

Ví dụ nhanh:

Cách 1Quy hoạch động + mex mọi đoạn (Subtask 1)

Chưa cần nghĩ tham lam: mex[j][i] = mex của đoạn $a_j..a_i$ (cố định $j$, kéo $i$ dần, con trỏ m chỉ tăng). Với mỗi $x$: dp[i] = số đoạn ít nhất để chia $a_1..a_i$, thử mọi đoạn cuối $a_j..a_i$ hợp lệ: dp[i] = min(dp[j - 1] + 1).

C++▶ Chạy tay từng dòng codeCách 1: tính mex mọi đoạn, rồi với mỗi x quy hoạch động dp[i] = min(dp[j − 1] + 1).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Vòng lặp j bên trong của dp[i] được gộp thành một bước (lời giải thích liệt kê các j hợp lệ).

Không gian$O(n^2)$

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

Kết quả chạy thật: Bản C++ đúng 4/20 test, sai test 5–20 (các test đúng chạy lâu nhất 0.004s) → 20 điểm. Mảng chỉ khai báo cho $n \le 100$ nên từ test 5 trở đi chương trình chạy sai (tràn mảng) – cách này vốn chỉ nhắm subtask 1. Bản Python đúng 4/20 test, quá thời gian test 5–20 (các test đúng chạy lâu nhất 0.060s) – với $n = 100$ bản Python vẫn chạy nhanh, nhưng từ test 5 thì $n$ lớn nên quá thời gian.

Cách 2Tham lam O(n) cho mỗi x (Subtask 1, 2)

Với mỗi $x$ ($1 \le x < M$), quét dãy một lần, đếm dem = số giá trị khác nhau trong $[0, x]$ mà đoạn hiện tại đã có. Gặp giá trị $v \le x$ chưa có trong đoạn: nếu dem == x thì thêm $v$ sẽ đủ $x + 1$ giá trị $0..x$ → mở đoạn mới bắt đầu từ $v$. Để "xoá" đoạn cũ trong $O(1)$, mỗi đoạn có một mã ma riêng, lan[v] == ma nghĩa là $v$ đã có trong đoạn hiện tại.

C++▶ Chạy tay từng dòng codeCách 2: với mỗi x, quét tham lam: thêm giá trị sẽ làm đủ 0..x thì mở đoạn mới.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n \cdot \min(n, M))$

Kết quả chạy thật: Bản C++ đúng 14/20 test, quá thời gian test 12–15, 18, 20 (các test đúng chạy lâu nhất 0.195s) → 40 điểm (subtask 1, 2). Nó còn qua được nhiều test lớn có $M$ nhỏ (vì chỉ $x < M$ mới phải quét), nhưng test 12, 13, 14, 15, 18, 20 có $M$ lớn nên quá thời gian. Bản Python đúng 11/20 test, quá thời gian test 10–15, 18–20 (các test đúng chạy lâu nhất 0.640s).

Cách 3Chạy song song mọi x + Fenwick max (full)

Viết lại bước tham lam dưới dạng "nhảy": đoạn bắt đầu ở $s$, gọi $nxt(v, s)$ là vị trí đầu tiên $\ge s$ có giá trị $v$. Đoạn chứa đủ $0..x$ lần đầu tại vị trí $p = \max_{v \le x} nxt(v, s)$, nên đoạn tham lam là $[s, p - 1]$ và đoạn sau bắt đầu ở $p$ (không có $p \le n$ thì đoạn cuối là $[s, n]$).

1. Quét $s$ từ 1 tới $n$ một lần cho tất cả $x$: head[s] là danh sách các $x$ có đoạn hiện tại bắt đầu đúng tại $s$ (danh sách liên kết qua link). Tới $s$, lấy từng $x$ trong danh sách, tính $p$, rồi chuyển $x$ sang danh sách head[p].
2. Fenwick max theo giá trị: khi $s$ tăng, $nxt(v, s)$ chỉ tăng (đi qua vị trí $s$ thì $nxt(a_s, \cdot)$ nhảy sang lần xuất hiện kế tiếp nextOcc[s]). Cây Fenwick lưu $nxt(v, s)$ tại chỉ số $v + 1$, chỉ cập nhật tăng nên lấy max tiền tố $\max_{v \le x}$ trong $O(\log M)$.
3. Vì sao tổng số lần nhảy nhỏ? Mỗi lần nhảy của $x$ dùng một "cửa sổ" chứa đủ $0..x$, các cửa sổ chỉ chung nhau điểm mút, nên số lần nhảy của $x$ không quá $2 \cdot \min_{v \le x} cnt(v) + 1$ ($cnt(v)$ = số lần $v$ xuất hiện). Tổng theo mọi $x$ là $O(n)$ (giá trị hiếm nhất trong $0..x$ "chia" các vị trí cho nhau).

C++▶ Chạy tay từng dòng codeCách 3: quét s một lần, mỗi x nhảy từ đầu đoạn sang p = max nxt(v, s) (Fenwick max).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Hàm upd/qry của cây Fenwick được tính gọn trong một bước; hình "nxt" là các giá trị cây đang giữ.

Đọc nhanh bằng fread và in một lần bằng fwrite vì dữ liệu tới $10^6$ số.

Không gian$O(n + \max a)$

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

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.188s. Full điểm. Mình không viết bản Python cho cách này: đọc $10^6$ số và chạy Fenwick bằng Python chắc chắn vượt 1 giây.

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. Quy hoạch động + mex mọi đoạn	C++	4/20	0.004s	20%
	Python	4/20	0.060s	20%
2. Tham lam O(n) cho mỗi x	C++	14/20	0.195s	40%
	Python	11/20	0.640s	40%
3. Chạy song song mọi x + Fenwick max	C++	20/20	0.188s	100%

Ghi chú của mình: thời gian là thời gian CPU trên máy mình (giới hạn 1 giây, test quá giờ bị dừng ở khoảng 4 giây). Hai kỹ thuật đáng nhớ: (1) với tính chất "đóng với đoạn con", tham lam kéo dài đoạn là tối ưu; (2) khi cần trả lời cho mọi tham số $x$, thử chạy song song các tiến trình của mọi $x$ trên cùng một lần quét – chi phí chung (ở đây là cây Fenwick) được dùng lại.

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 😇