Đoạn K

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Dễ Tham lam Max tiền tố

Đề bài

Mảng $A$ gồm $N$ phần tử là hoán vị của các giá trị từ 1 đến $N$. Bạn được phép chia mảng $A$ thành $K$ đoạn, trong đó mỗi đoạn gồm các phần tử liên tiếp có độ dài tùy ý (có thể khác nhau). Ví dụ một phép chia thành 5 đoạn:

Sau khi chia thành $K$ đoạn, bạn được phép sắp xếp các giá trị bên trong mỗi đoạn (độc lập với nhau).

Yêu cầu: hãy xác định số đoạn $K$ lớn nhất có thể sao cho sau khi sắp xếp xong thì mảng $A$ trở thành mảng được sắp xếp tăng dần.

Dữ liệu:

• Dòng đầu ghi số nguyên $N$ là số lượng phần tử của mảng $(1 \le N \le 10^6)$.
• Dòng tiếp theo ghi $N$ số nguyên $A_i$ là giá trị của các phần tử trong mảng $(1 \le A_i \le N)$.

Kết quả: một giá trị duy nhất là số lượng $K$ theo yêu cầu.

Giải thích:

• Ví dụ 1: chỉ có thể chia thành đúng một đoạn gồm tất cả các phần tử rồi sắp xếp: $[4\ 5\ 3\ 2\ 1] \to [1\ 2\ 3\ 4\ 5]$.
• Ví dụ 2: chia được nhiều nhất 3 đoạn: $[1]\ [2]\ [4\ 5\ 3] \to [1]\ [2]\ [3\ 4\ 5]$ – mảng đã được sắp xếp.
• Ví dụ 3: chia được nhiều nhất 2 đoạn: $[4\ 2\ 1\ 5\ 9\ 8\ 7\ 6\ 3]\ [10]$.

Giới hạn: 20% số test đầu có $N \le 20$; 20% tiếp theo có $N \le 10^2$; 20% tiếp theo có $N \le 10^4$; 20% tiếp theo có $N \le 10^5$; 20% còn lại có $N \le 10^6$.

Ví dụ 1 – input

5
4 5 3 2 1

Ví dụ 1 – output

1

Ví dụ 2 – input

5
1 2 4 5 3

Ví dụ 2 – output

3

Ví dụ 3 – input

10
4 2 1 5 9 8 7 6 3 10

Ví dụ 3 – output

2

Lời mở đầu

Một bài rất gọn nhưng cần "nhìn ra" một tính chất: chỗ nào được phép cắt? Khi trả lời được câu đó, ta chỉ việc tham lam cắt ở mọi chỗ được phép. Mình sẽ đi từ cách $O(N^2)$ (ăn 60% điểm) tới cách $O(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ưởngmax = iCách 1O(N²)Cách 2O(N)

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

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

Test	N	Đúng là hoán vị?	Đáp án K	Số test K = 1
1–20	4 … 20	Có	1 … 17	2/20
21–40	100	Có	2 … 32	0/20
41–60	10.000	Có	8 … 32	0/20
61–80	100.000	Có	2 … 50	0/20
81–100	1.000.000	Có	6 … 36	0/20

• Mình đã kiểm tra: mọi test đều đúng là hoán vị của $1..N$ như đề nói.
• Test 1–3 là 3 ví dụ của đề. Đáp án nhìn chung khá nhỏ (nhiều nhất 50) – các hoán vị ngẫu nhiên rất ít chỗ cắt được.

Đối chiếu giới hạn với test thật và số test đúng của từng cách:

Subtask	Đề ghi	Test thật	Cách 1 $O(N^2)$	Cách 2 $O(N)$
20%	$N \le 20$	1–20	20/20	20/20
20%	$N \le 10^2$	21–40	20/20	20/20
20%	$N \le 10^4$	41–60	20/20	20/20
20%	$N \le 10^5$	61–80	0/20	20/20
20%	$N \le 10^6$	81–100	0/20	20/20

Ý tưởngCắt được sau vị trí i khi max(A[1..i]) = i

Sau khi sắp xếp trong từng đoạn, mảng phải là $1, 2, \ldots, N$. Xét một chỗ cắt ngay sau vị trí $i$: mọi phần tử bên trái chỗ cắt không bao giờ sang được bên phải (sắp xếp chỉ diễn ra trong từng đoạn). Vì vậy:

Nhận xét

Cắt sau vị trí $i$ là hợp lệ $\iff$ $A_1, \ldots, A_i$ đúng là các số $1, 2, \ldots, i$ $\iff$ $\max(A_1, \ldots, A_i) = i$.

Vế sau đúng vì $A$ là hoán vị: $i$ số khác nhau mà số lớn nhất là $i$ thì chúng phải đúng là $1..i$.

Hơn nữa, nếu cắt ở tất cả các chỗ hợp lệ $c_1 < c_2 < \ldots < c_K = N$ thì đoạn thứ $t$ chứa đúng các số $c_{t-1}+1 .. c_t$, sắp xếp xong là đúng vị trí. Ngược lại mọi cách chia hợp lệ chỉ dùng các chỗ cắt hợp lệ. Vậy tham lam cắt ở mọi chỗ hợp lệ là tối ưu:

Đáp án

$K$ = số vị trí $i$ $(1 \le i \le N)$ có $\max(A_1..A_i) = i$. Vị trí $i = N$ luôn thoả nên $K \ge 1$.

Em nhập hoán vị rồi bấm Tiếp để xem max tiền tố "đuổi theo" chỉ số $i$ và mỗi lần bắt kịp là một nhát cắt:

Hoán vị A:

Ví dụ nhanh:

Cách 1Tính lại max mỗi lần – 60% điểm

Với mỗi $i$, duyệt lại $A_1..A_i$ để tính max rồi so với $i$. Đơn giản, đúng, nhưng tốn $1 + 2 + \ldots + N \approx N^2/2$ phép tính.

C++▶ Chạy tay từng dòng codeCách 1: với mỗi i tính lại max(A[1..i]) từ đầu rồi so với i.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

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

Kết quả chạy thật: bản C++ đúng 60/100 test (sai/quá thời gian ở test 61–100), test đúng chạy lâu nhất 0.04s. Bản Python: bản Python đúng 40/100 test (sai/quá thời gian ở test 41–100), test đúng chạy lâu nhất 0.03s. Với $N = 10^5$ cần khoảng $5 \cdot 10^9$ phép so sánh nên quá thời gian.

Cách 2Max tiền tố cập nhật dần – Full điểm

$\max(A_1..A_i)$ $= \max(\max(A_1..A_{i-1}), A_i)$, nên chỉ cần một biến mx cập nhật khi đọc từng số. Không cần lưu mảng.

C++▶ Chạy tay từng dòng codeCách 2: cập nhật max tiền tố khi đọc, đếm các i có mx == i.

Dữ liệu vào (stdin) – sửa thoải mái10 4 2 1 5 9 8 7 6 3 10

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. mx = max(mx, x): sau dòng này mx là max của $A_1..A_i$.
2. if (mx == i) k++: đếm một nhát cắt sau vị trí $i$. Ở $i = N$ thì $mx = N$ nên luôn đếm được ít nhất 1.
3. Đọc $10^6$ số nên nhớ ios::sync_with_stdio(0); cin.tie(0);.

Không gian$O(1)$

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.11s. Bản Python: bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.28s.

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

Cách	Ngôn ngữ	Đúng	Test đúng lâu nhất	Ghi chú
1. Tính lại max mỗi lần $O(N^2)$	C++	60/100	0.04s	Qua $N \le 10^4$
	Python	40/100	0.03s	Chậm hơn C++ rất nhiều
2. Max tiền tố cập nhật dần $O(N)$	C++	100/100	0.11s	Full điểm
	Python	100/100	0.28s	Full điểm

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). Bài này là phiên bản "hoán vị" của bài kinh điển Max Chunks To Make Sorted; nếu mảng có giá trị lặp lại thì điều kiện cắt đổi thành $\max(A_1..A_i) \le \min(A_{i+1}..A_N)$.

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 😇