Tóm tắt đề bài

Cho một dãy số \(a_1, a_2, \dots, a_n\) được sắp xếp trên một vòng tròn. Một vị trí \(j\) được gọi là "vị trí tốt" nếu khi bắt đầu từ \(a_j\) và đi dọc theo vòng tròn, tất cả các tổng tích lũy (tổng các phần tử từ điểm bắt đầu đến vị trí hiện tại) đều lớn hơn \(0\). Cụ thể, các tổng sau phải dương:

• \(a_j > 0\)
• \(a_j + a_{j+1} > 0\)
• ...
• \(a_j + a_{j+1} + \dots + a_n + a_1 + \dots + a_{j-1} > 0\)

Yêu cầu: Đếm số lượng vị trí tốt trong dãy.

Phân tích

• Điều kiện: \(n \le 10^5\), \(|a_i| \le 10^4\).
• Nhận xét: Với mỗi vị trí \(j\), ta cần kiểm tra \(n\) tổng tích lũy. Nếu làm một cách trực tiếp cho mọi \(j\), độ phức tạp sẽ là \(O(n^2)\), không thể vượt qua giới hạn thời gian với \(n = 10^5\).
• Mảng cộng dồn: Gọi \(S_i = a_1 + a_2 + \dots + a_i\) là mảng cộng dồn của dãy gốc (với \(S_0 = 0\)).
• Tổng các phần tử từ \(a_j\) đến \(a_k\) (với \(j \le k \le n\)) là \(S_k - S_{j-1}\).

• Nếu tổng đi qua điểm cuối mảng \(n\) và quay lại đầu mảng (với \(1 \le k < j\)), tổng đó là:

  \[(a_j + \dots + a_n) + (a_1 + \dots + a_k) = (S_n - S_{j-1}) + S_k\]

Để \(j\) là vị trí tốt, ta cần:

1. Với mọi \(k\) từ \(j\) đến \(n\): \(S_k - S_{j-1} > 0 \Rightarrow S_k > S_{j-1}\). Điều này tương đương với \(\min(S_j, S_{j+1}, \dots, S_n) > S_{j-1}\).
2. Với mọi \(k\) từ \(1\) đến \(j-1\): \((S_n - S_{j-1}) + S_k > 0 \Rightarrow S_k + S_n > S_{j-1}\). Điều này tương đương với \(\min(S_1, S_2, \dots, S_{j-1}) + S_n > S_{j-1}\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Với mỗi vị trí \(j\) từ \(1\) đến \(n\), ta mô phỏng việc tính các tổng tích lũy. Nếu gặp bất kỳ tổng nào \(\le 0\), vị trí đó không tốt.

Độ phức tạp

• Thời gian: \(O(n^2)\)
• Đánh giá: Chỉ phù hợp với \(n \le 5000\).

Code Brute Force

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int count = 0;
    for (int j = 0; j < n; j++) {
        long long current_sum = 0;
        bool ok = true;
        for (int k = 0; k < n; k++) {
            current_sum += a[(j + k) % n];
            if (current_sum <= 0) {
                ok = false;
                break;
            }
        }
        if (ok) count++;
    }
    cout << count << endl;
    return 0;
}

n = int(input())
a = list(map(int, input().split()))

ans = 0
for j in range(n):
    current_sum = 0
    ok = True
    for k in range(n):
        current_sum += a[(j + k) % n]
        if current_sum <= 0:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Hướng giải quyết (Tối ưu)

Thuật toán

Dựa trên phân tích ở trên, để kiểm tra nhanh điều kiện cho vị trí \(j\), ta cần tìm giá trị nhỏ nhất của mảng cộng dồn trong các khoảng nhất định. Ta có thể sử dụng kỹ thuật Tiền tố/Hậu tố cực tiểu (Prefix/Suffix Minimum) để giải quyết trong \(O(n)\).

1. Tính mảng cộng dồn \(S_i\) với \(i = 1 \dots n\).
2. Xây dựng mảng \(minSuf[i] = \min(S_i, S_{i+1}, \dots, S_n)\).
3. Xây dựng mảng \(minPre[i] = \min(S_1, S_2, \dots, S_i)\).
4. Duyệt \(j\) từ \(1\) đến \(n\):
   • Điều kiện 1: \(minSuf[j] - S_{j-1} > 0\)
   • Điều kiện 2: Nếu \(j > 1\), cần thêm \(minPre[j-1] + S_n - S_{j-1} > 0\)
   • Nếu cả hai thỏa mãn, \(j\) là vị trí tốt.

Ví dụ minh họa

Dãy: 0 1 -2 10 3 (\(n=5\))

• \(S = [0, 1, -1, 9, 12]\) (với \(S_0 = 0\))
• \(minPre = [0, 0, -1, -1, -1]\) (xét từ \(S_1\) đến \(S_i\)) \(\rightarrow minPre = [0, 1, -1, -1, -1]\)
• \(minSuf = [12, 12, 12, 9, -1]\) (xét từ \(S_i\) đến \(S_5\)) \(\rightarrow minSuf = [-1, -1, -1, 9, 12]\)

Xét \(j=4\) (số 10):

• \(S_{j-1} = S_3 = -1\).
• \(minSuf[4] = 9\). Điều kiện 1: \(9 - (-1) = 10 > 0\) (Đúng).
• \(minPre[3] = -1, S_n = 12\). Điều kiện 2: \(-1 + 12 - (-1) = 12 > 0\) (Đúng).
  \(\Rightarrow\) \(j=4\) là vị trí tốt.

Độ phức tạp

• Thời gian: \(O(n)\) do chỉ sử dụng các vòng lặp đơn lẻ để tính tiền tố, hậu tố và duyệt kết quả.
• Bộ nhớ: \(O(n)\) để lưu trữ các mảng phụ trợ.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    vector<long long> S(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        S[i] = S[i - 1] + a[i];
    }

    // minSuf[i] = min(S[i], S[i+1], ..., S[n])
    vector<long long> minSuf(n + 1);
    minSuf[n] = S[n];
    for (int i = n - 1; i >= 1; i--) {
        minSuf[i] = min(S[i], minSuf[i + 1]);
    }

    // minPre[i] = min(S[1], S[2], ..., S[i])
    vector<long long> minPre(n + 1);
    minPre[1] = S[1];
    for (int i = 2; i <= n; i++) {
        minPre[i] = min(minPre[i - 1], S[i]);
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        bool ok = true;

        // Kiểm tra đoạn từ j đến n: min(S[j...n]) - S[j-1] > 0
        if (minSuf[j] - S[j - 1] <= 0) ok = false;

        // Kiểm tra đoạn từ 1 đến j-1: min(S[1...j-1]) + S[n] - S[j-1] > 0
        if (ok && j > 1) {
            if (minPre[j - 1] + S[n] - S[j - 1] <= 0) ok = false;
        }

        if (ok) ans++;
    }

    cout << ans << endl;

    return 0;
}

import sys

def solve():
    input = sys.stdin.read().split()
    if not input:
        return
    n = int(input[0])
    a = list(map(int, input[1:]))

    s = [0] * (n + 1)
    for i in range(n):
        s[i+1] = s[i] + a[i]

    min_suf = [0] * (n + 1)
    min_suf[n] = s[n]
    for i in range(n - 1, 0, -1):
        min_suf[i] = min(s[i], min_suf[i+1])

    min_pre = [0] * (n + 1)
    min_pre[1] = s[1]
    for i in range(2, n + 1):
        min_pre[i] = min(min_pre[i-1], s[i])

    ans = 0
    for j in range(1, n + 1):
        ok = True
        # Điều kiện 1: các tổng tích lũy từ j đến n
        if min_suf[j] - s[j-1] <= 0:
            ok = False

        # Điều kiện 2: các tổng tích lũy sau khi quay vòng về 1 đến j-1
        if ok and j > 1:
            if min_pre[j-1] + s[n] - s[j-1] <= 0:
                ok = False

        if ok:
            ans += 1

    print(ans)

solve()