\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Nếu tổng các phần tử bé hơn \(k\) thì không có cách thỏa mãn

• Mình sẽ kiếm tra từng đoạn \([l, r] (0 \leq l \leq r \leq n - 1)\) và đoạn đối của nó \([0, l) \cup (r, n - 1]\)

• Thay vì duyệt 2 lần mất công, ta có nhận xét như sau

Nếu đoạn \([l, r]\) có \(n1\) phần tử thì đoạn còn lại sẽ có \(n2 = n - n1\) phần tử

Gọi \(S(l, r)\) là tổng tất cả các số trong đoạn \((l, r)\) và \(S = S(0, n - 1)\)

Có \(S = S(l, r) + (S(0, l - 1) + S(r + 1, n - 1))\)

Từ đó suy ra \(S(0, l - 1) + S(r + 1, n - 1)\) hay tổng đoạn \([0, l) \cup (r, n - 1]\) có giá trị \(S - S(l, r)\)

Vậy sau khi tính tổng tất cả các số, ta chỉ cần duyệt các đoạn \([l, r] (0 \leq l \leq r \leq n - 1)\), và đoạn còn lại là (n2 = n - n1, S - S(l, r))

---__ Code

\(\color{orange}{\text{Hint 2 <Dynamic-programming>}}\)

• Thay vì duyệt từng đoạn \([l, r]\) rồi tính tổng, ta có thể tiền xử lí tổng và tính được \(S(l, r)\) trong \(O(1)\)

Tạo thêm một mảng \(S[][]\)

Từ mỗi vị trí \(l\) cố định ta duyệt \(r \in [l, n - 1]\) và tăng giá trị dần vào mảng

Công thức: \(S[l, r] = S[l][r - 1] + a[r]\)

• Tiền xử lí sẽ tốn thêm bộ nhớ \(O(n ^ 2)\) dể tradeoff việc tính \(S(l, r)\) từ \(O(n) \Rightarrow O(1)\)

Ta có thể duyệt trực tiếp theo cách như trên và không lưu vào mảng tổng \(S[][]\) mà dùng trực tiếp biến \(S\)

Từ mỗi vị trí \(l\) cố định ta duyệt \(r \in [l, n - 1]\) và tăng giá trị dần vào mảng

Công thức: \(S = S_{trước} + a[r]\)

\(\color{orange}{\text{Hint 3 <Two-pointers>}}\)

• Với mỗi vị trí \(l \in [0, n)\)

Dùng cách như trên để tính \(S\)

Nếu \(l = r\) thì \(S = 0\) mà \(a_i \geq 1\) nên luôn không thỏa mãn, ta sẽ di chuyển \(r\)

Ta tăng biến \(r\) đến khi nào tổng lớn hơn \(k\) thì dừng \(r\)

Tối thiểu hóa giá trị kết quả với độ dài hiện tại (optimize: \(res = 1\) thì \(break\))

Lưu ý sau mỗi lần chạy, mình di chuyển \(l\) thì mình phải xóa giá trị đó khỏi tổng

Lưu ý trong trường hợp \(r\) ở vị trí cuối, thì sau khi di chuyển, mình phải đưa nó về vị trí đầu

\(\color{goldenrod}{\text{Question}}\)

• Ngoài cách này bạn còn có thể làm cách khác trong \(O(n)\) không ?

\(\color{green}{\text{Preference AC Code }}\): Two-pointers

\(^{^{\color{purple}{\text{Complexity : }} O(n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    ll sum = 0;
    for (int x : a) sum += x;
    if (sum < k) return cout << -1, 0; /// Tong luon be hon k

    int res = n; /// Truong hop xau nhat no co tat ca phan tu
    int len = 0; /// So luong phan tu tinh toi hien tai
    sum = 0;     /// Bien tong
    for (int l = 0, r = 0; l < n; ) /// Two-pointers
    {
        while (l == r || sum < k) /// (i) = constant
        {
            sum += a[r++]; len++; /// Nhan them toi khi (sum >= k)
            if (r == n) r = 0;    /// Neu con tro o cuoi, di chuyen len dau
        }
        minimize(res, len);   /// Toi thieu hoa gia tri
        if (res == 1) break;  /// Da toi uu nhat
        sum -= a[l++]; len--; /// Di chuyen con tro sang gia tri tiep theo, phai xoa no khoi sum
    }

    cout << res; /// Xuat ket qua
    return 0;
}