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)
Đề bài
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.
5
2 0 1 0 3-1
3
2
2
1Giả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à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 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 |
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ó):
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).
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.
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]$).
- 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 qualink). Tới $s$, lấy từng $x$ trong danh sách, tính $p$, rồi chuyển $x$ sang danh sáchhead[p]. - 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)$. - 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 nhanh bằng fread và in một lần bằng fwrite vì dữ liệu tới $10^6$ số.
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% |