Dãy số 7

Nguồn: CLUE OJ Độ khó: Khá Map / Set (multiset) Tổng tiền tố

Đề bài

Dãy số

Cho dãy số nguyên $a_1, a_2, \ldots, a_n$ $(1 \le n \le 2 \cdot 10^6)$, phạm vi mỗi phần tử có giá trị tuyệt đối không quá $10^4$. Dãy số này được viết trên một vòng tròn, nghĩa là khi cắt dãy số đã cho tại vị trí $j$ bất kì ta thu được dãy số như sau: $a_j, a_{j+1},$ $\ldots,$ $a_n,$ $a_1,$ $a_2,$ $\ldots,$ $a_{j-1}$.

Vị trí $j$ được gọi là vị trí tốt nếu các điều kiện dưới đây đều được thỏa mãn:

• $a_j > 0$
• $a_j + a_{j+1} > 0$
• $\ldots$
• $a_j + a_{j+1} + \cdots + a_n > 0$
• $a_j + a_{j+1} + \cdots + a_n + a_1 > 0$
• $\ldots$
• $a_j + a_{j+1} + \cdots$ $+ a_n + a_1 + a_2$ $+ \cdots + a_{j-2} > 0$
• $a_j + a_{j+1} + \cdots$ $+ a_n + a_1 + a_2$ $+ \cdots + a_{j-2}$ $+ a_{j-1} > 0$

Yêu cầu: Hãy đếm số lượng vị trí tốt có trong dãy số nguyên $a_1, a_2, \ldots, a_n$.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $n$;
• Dòng thứ hai chứa dãy số nguyên $a_1, a_2, \ldots, a_n$.

Dữ liệu ra: một số nguyên duy nhất là số lượng vị trí tốt tìm được.

Subtask:

• 50% điểm có $n \le 10^4$.
• 30% điểm tiếp theo có $n \le 10^5$.
• 20% điểm còn lại không có giới hạn gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.

Ví dụ 1 – input

5
0 1 -2 10 3

Ví dụ 1 – output

2

Ví dụ 2 – input

7
1 -2 0 5 -4 1 -2

Ví dụ 2 – output

0

Lời mở đầu

Nói gọn lại: cắt vòng tròn tại $j$, đi một vòng và cộng dần – mọi tổng cộng dồn (gồm $n$ tổng) đều phải dương. Ở ví dụ 1 với dãy $0, 1, -2, 10, 3$: cắt tại $j = 4$ ta được $10, 3, 0, 1, -2$ với các tổng cộng dồn $10, 13, 13, 14, 12$ đều dương → tốt. Cắt tại $j = 5$: $3, 0, 1, -2, 10$ → $3, 3, 4, 2, 12$ → tốt. Các vị trí còn lại đều có một tổng $\le 0$ (ví dụ $j = 1$ có ngay $a_1 = 0$). Vậy đáp án là 2.

Để ý điều kiện cuối cùng chính là tổng cả dãy phải dương. Ở ví dụ 2, tổng cả dãy là $-1$ nên không vị trí nào tốt, đáp án 0.

Bài có 3 subtask rất "chuẩn" cho 3 mức thuật toán: $O(n^2)$, $O(n \log n)$ và $O(n)$. Mình sẽ đi lần lượt cả 3 và chạy thật trên bộ test.

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ưởngdãy gấp đôiCách 1O(n²)Cách 2multisetCách 3O(n)

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

Bộ test có 100 test:

Test	n	Giá trị $a_i$	|Tổng| lớn nhất	Số test đáp án 0	Tỉ lệ vị trí tốt
1–30	5 … 20	-30 … 30	120	12/30	17%
31–50	1.461 … 8.846	-9.999 … 9.999	377.414	14/20	0%
51–80	100.000	-9.998 … 9.999	153.179.473	0/30	99%
81–90	500.000	-9.976 … 9.999	763.992.284	0/10	100%
91–95	1.000.000	-998.338.343 … 999.999.485	67.787.053.902.242	0/5	100%
96–100	2.000.000	-988.956.816 … 999.999.459	135.824.833.271.121	0/5	100%

Đề ghi $|a_i| \le 10^4$ nhưng test 91–100 thì không!

Ở 10 test cuối, $a_i$ lên tới gần $10^9$ và tổng của cả dãy lên tới khoảng $1{,}36 \cdot 10^{14}$. Nếu tin đề mà dùng int cho tổng (với $|a_i| \le 10^4$, $n \le 2 \cdot 10^6$ thì tổng chỉ tới $2 \cdot 10^{10}$ – vốn đã vượt int rồi!) thì chắc chắn sai. Mọi tổng trong bài này mình đều dùng long long.

Ngoài ra: ở các test nhỏ (1–50), khoảng một nửa số test có tổng cả dãy $\le 0$ nên đáp án bằng 0; còn từ test 51 trở đi gần như mọi vị trí đều tốt – đây là ác mộng của cách thử từng vị trí vì nó không thể dừng sớm.

Subtask (theo $n$) khớp với bộ test. Số test đúng của từng cách:

Subtask	Đề ghi	Test	Cách 1 (thử từng j)	Cách 2 (multiset)	Cách 3 (min tiền tố/hậu tố)
1 (50%)	$n \le 10^4$	1–50	50/50	50/50	50/50
2 (30%)	$n \le 10^5$	51–80	0/30	30/30	30/30
3 (20%)	$n \le 2 \cdot 10^6$	81–100	0/20	15/20	20/20

Ý tưởngDuỗi vòng tròn thành dãy gấp đôi

Mẹo quen thuộc với vòng tròn: viết dãy hai lần liên tiếp $a_1, \ldots, a_n, a_1, \ldots, a_n$. Khi đó cắt tại $j$ chính là lấy đoạn $j, j+1, \ldots, j+n-1$ của dãy gấp đôi. Gọi $P_k$ là tổng tiền tố của dãy gấp đôi ($P_0 = 0$). Tổng cộng dồn từ $j$ tới $k$ là $P_k - P_{j-1}$, nên:

Điều kiện vị trí tốt

$j$ tốt $\iff$ $P_k - P_{j-1} > 0$ với mọi $k = j, \ldots, j+n-1$ $\iff$ $\min\left(P_j, P_{j+1}, \ldots, P_{j+n-1}\right) > P_{j-1}$.

Nhìn bằng hình: vẽ các điểm $P_0, P_1, \ldots, P_{2n-1}$. Vị trí $j$ tốt khi cả "cửa sổ" $n$ điểm $P_j..P_{j+n-1}$ đều nằm hẳn phía trên đường ngang vẽ ở độ cao $P_{j-1}$. Bài toán trở thành: với mỗi cửa sổ độ dài $n$ trượt dần sang phải, tìm giá trị nhỏ nhất của cửa sổ.

Em nhập dãy rồi bấm Tiếp để xem từng vị trí cắt $j$ (điểm xanh: trên đường ngang, điểm đỏ: không trên đường ngang):

Dãy a:

Ví dụ nhanh:

Có hai cách tìm min của cửa sổ trượt:

• Dùng multiset chứa $n$ giá trị trong cửa sổ: trượt sang phải thì xoá $P_j$, thêm $P_{j+n}$, min là phần tử đầu – $O(n \log n)$ (cách 2).
• Tách cửa sổ thành 2 phần: $P_j..P_n$ (min hậu tố của mảng tiền tố $S$ gốc) và $P_{n+1}..P_{n+j-1}$ $= S_n + S_1,$ $\ldots,$ $S_n + S_{j-1}$ (bằng $S_n$ cộng min tiền tố) – $O(n)$ (cách 3).

Cách 1Thử từng vị trí cắt – Subtask 1

Làm đúng như đề: với mỗi $j$, đi một vòng, cộng dồn và dừng ngay khi gặp tổng $\le 0$.

C++▶ Chạy tay từng dòng codeCách 1: thử cắt tại từng j, cộng dồn một vòng, gặp tổng ≤ 0 thì dừng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Vị trí thứ $k$ (đếm từ 0) tính từ $j$ trên vòng tròn là (j - 1 + k) % n + 1: chuyển về chỉ số từ 0, cộng $k$, lấy dư cho $n$ rồi đổi lại về chỉ số từ 1.
2. Gặp tổng $\le 0$ thì break luôn – nếu dữ liệu có nhiều vị trí xấu thì chạy khá nhanh. Nhưng ở test 51–100 gần như vị trí nào cũng tốt, vòng trong luôn chạy đủ $n$ bước.

Không gian$O(n)$

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

Kết quả chạy thật: Bản C++ đúng 50/100 test, quá thời gian ở test 51–100; test đúng chạy lâu nhất 0.01s. Bản Python đúng 50/60 test (mình chỉ chạy test 1–60), quá thời gian ở test 51–60; test đúng chạy lâu nhất 0.37s. Bản C++ ăn trọn subtask 1 (50% điểm).

Cách 2Cửa sổ trượt với multiset – Subtask 1, 2

Cài đặt trực tiếp ý tưởng dãy gấp đôi: multiset giữ đúng $n$ giá trị $P_j, \ldots, P_{j+n-1}$ (dùng multiset vì các tổng tiền tố có thể trùng nhau).

C++▶ Chạy tay từng dòng codeCách 2: multiset giữ cửa sổ P[j..j+n-1] của dãy gấp đôi, so min với P[j-1].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. *ms.begin() là phần tử nhỏ nhất của multiset.
2. ms.erase(ms.find(P[j])) chỉ xoá một bản sao của $P_j$. Nếu viết ms.erase(P[j]) thì sẽ xoá tất cả các phần tử bằng $P_j$ – lỗi rất hay gặp!
3. Mảng P dài $2n$ nên khai báo $4 \cdot 10^6 + 5$ phần tử.
4. Python không có multiset, mình dùng heapq kèm "xoá lười": phần tử nào có chỉ số đã ra khỏi cửa sổ thì khi nó nổi lên đỉnh heap mới bỏ đi.

Không gian$O(n)$

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

Kết quả chạy thật: Bản C++ đúng 95/100 test, quá thời gian ở test 96–100; test đúng chạy lâu nhất 0.66s. Bản Python đúng 80/100 test, quá thời gian ở test 81–100; test đúng chạy lâu nhất 0.31s. Với $n = 2 \cdot 10^6$ thì cần khoảng $4 \cdot 10^6$ thao tác trên multiset, mỗi thao tác cỡ $\log_2(2 \cdot 10^6) \approx 21$ bước so sánh và rất nhiều lần cấp phát bộ nhớ – không kịp 1 giây.

Cách 3Min tiền tố và min hậu tố – Full điểm

Gọi $S_i = a_1 + \cdots + a_i$ là tổng tiền tố của dãy gốc. Các tổng cộng dồn khi cắt tại $j$ chia làm 2 nhóm:

• Đi từ $j$ tới $n$: tổng là $S_k - S_{j-1}$ với $k = j..n$. Tất cả dương $\iff$ $\text{suf}_j$ $= \min(S_j, \ldots, S_n) > S_{j-1}$.
• Vòng qua đầu dãy, đi từ $1$ tới $j-1$: tổng là $S_n - S_{j-1} + S_k$ với $k = 1..j-1$. Tất cả dương $\iff$ $S_n + \text{pre}_{j-1} > S_{j-1}$ với $\text{pre}_{j-1} = \min(S_1, \ldots, S_{j-1})$. (Khi $j = 1$ nhóm này rỗng.)

Mảng pre và suf tính trước bằng 2 vòng for, sau đó mỗi $j$ kiểm tra trong $O(1)$.

C++▶ Chạy tay từng dòng codeCách 3: min hậu tố suf và min tiền tố pre của tổng tiền tố S, mỗi j kiểm tra O(1).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. pre[0] = LLONG_MAX và suf[n + 1] = LLONG_MAX là "lính canh" để công thức min chạy đúng ở 2 đầu.
2. Điều kiện (j == 1) || đặt trước để khi $j = 1$ không cần dùng pre[0] (cộng LLONG_MAX sẽ tràn số).
3. Bản Python dùng itertools.accumulate để tính tổng tiền tố và min tiền tố/hậu tố cho nhanh.

Không gian$O(n)$

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.18s. Bản Python đúng 95/100 test, quá thời gian ở test 96–100; test đúng chạy lâu nhất 0.97s.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Thử từng vị trí $O(n^2)$	C++	50/100	> 1s	Qua subtask 1; quá thời gian test 51–100
	Python	50/60	> 1s	Mình chỉ chạy test 1–60; quá thời gian test 51–60
2. Cửa sổ trượt + multiset	C++	95/100	> 1s	Quá thời gian test 96–100 (n = 2·10^6)
	Python	80/100	> 1s	heap + xoá lười; quá thời gian test 81–100
3. Min tiền tố / hậu tố $O(n)$	C++	100/100	0.18s	Full điểm
	Python	95/100	> 1s	Quá thời gian test 96–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. multiset là công cụ rất tiện để lấy min/max của cửa sổ trượt, nhưng với $n$ cỡ vài triệu thì hằng số của nó lớn; khi cửa sổ có cấu trúc đặc biệt (như ở đây: luôn dài đúng $n$ trên dãy gấp đôi) thì min tiền tố/hậu tố cho lời giải $O(n)$ gọn và nhanh hơn hẳ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 😇