Dãy Số (CAU3)

Nguồn: Đề thi HSG Tin học Độ khó: Khá Prefix sum Map Tham lam

Đề bài

Câu 3 (5,0 điểm) DÃY SỐ

Bob gửi cho Alice một dãy số nguyên gồm $n$ phần tử: $a_1, a_2, \ldots, a_n$, đây là thông tin về một kho báu. Một đoạn con $(L, R)$ của dãy là một dãy gồm các phần tử liên tiếp $a_L, a_{L+1}, \ldots, a_R$ với $1 \le L \lt R \le n$, đoạn con $(L, R)$ được gọi là chứa thông tin quan trọng nhất nếu:

• Phần tử đầu tiên và cuối cùng của đoạn con là bằng nhau $(a_L = a_R)$;
• Tổng các phần tử của đoạn là lớn nhất.

Yêu cầu: hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Dữ liệu vào: từ tệp văn bản CAU3.INP:

• Dòng đầu tiên chứa một số nguyên dương $n$;
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9, i = 1, 2, \ldots, n)$.

Kết quả: đưa ra tệp văn bản CAU3.OUT một dòng chứa duy nhất một số nguyên là kết quả tìm được.

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có $n \le 10^2$;
• Có 30% số test khác ứng với 30% số điểm của bài có $n \le 10^3$;
• Có 30% số test còn lại ứng với 30% số điểm của bài có $n \le 10^5$.

(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé.)

CAU3.INP

7
3 3 3 3 1 11 1

CAU3.OUT

13

Giải thích: đoạn con chứa thông tin quan trọng nhất là $(5, 7)$ có tổng lớn nhất là $13$.

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải chi tiết để các bạn tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ cho bạn nào chưa hiểu đề: dãy là $3, 3, 3, 3, 1, 11, 1$ (vị trí tính từ 1). Các đoạn có hai đầu bằng nhau gồm:

• Hai đầu là số $3$: ví dụ đoạn $(1, 4)$ là $3 + 3 + 3 + 3 = 12$ – lớn nhất trong các đoạn hai đầu là $3$.
• Hai đầu là số $1$: chỉ có đoạn $(5, 7)$ là $1 + 11 + 1 = 13$.

So ra $13 \gt 12$ nên đáp án là 13. Chú ý là các phần tử có thể âm nên đáp án cũng có thể âm. Ví dụ test mà em học viên của mình làm sai:

6
3 -2 -2 -3 -5 -5  → đáp án -4

Đoạn $(2, 3)$ là $-2 + (-2) = -4$; đoạn $(5, 6)$ là $-5 + (-5) = -10$ không lớn hơn $-4$, nên đáp án là $-4$ chứ không phải $0$ nha. Nên biến lưu kết quả phải khởi tạo là giá trị rất nhỏ (LLONG_MIN) chứ đừng khởi tạo bằng $0$.

Nếu không có cặp nào bằng nhau?

Đề bài không hề nói đến trường hợp đó nên các bạn yên tâm là test sẽ luôn có ít nhất 1 cặp $a_L = a_R$ (và vì vậy $n \ge 2$).

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Prefix sum + 2 vòng for · O(N²) · 70%Cách 2Gom vị trí + min prefix · O(N) · 100%

Cách 1Prefix sum + duyệt mọi cặp (L, R) – O(N²)

Trước tiên với bài này các bạn thấy cái ràng buộc ở cuối bài không? Mình thử lấy trước 70% số điểm, tức là với trường hợp $n \le 10^3$.

Cách làm theo đề: duyệt mọi cặp $(i, j)$ với $i \lt j$, nếu $a_i = a_j$ thì tính tổng đoạn $(i, j)$ rồi cập nhật lớn nhất. Nếu tính tổng bằng một vòng for nữa thì thành $O(N^3)$; với $n = 10^3$ là $10^9$ – không ổn. Nên ta dùng mảng cộng dồn (prefix sum):

Prefix sum

$pre[0] = 0$, $\ pre[i] = pre[i-1] + a[i]$. Khi đó tổng đoạn $(L, R)$ là $a_L + \ldots + a_R = pre[R] - pre[L-1]$, tính ra ngay lập tức trong $O(1)$.

Hai vòng for thì với $n = 10^3$ là $10^6$ phép, so với time limit 1 giây (tầm $10^8$) vẫn thỏa nên yên tâm không sợ bị TLE.

Vài góp ý nhỏ mình đã nói với em học viên khi xem code của em ấy, các bạn cũng lưu ý nhé:

1. Kết hợp tạo prefix sum ngay lúc nhập để khỏi phải làm riêng một vòng lặp. Và không cần if(i == 1) ... else ... làm gì cho rối: khi $i = 1$ thì pre[i - 1] chính là pre[0] = 0 rồi. Mảng pre khai báo toàn cục thì mặc định đã bằng $0$ hết, nhưng nếu sợ thì cứ gán pre[0] = 0 lại cho chắc.
2. Mảng a cho kiểu long long luôn cho khỏe, tội gì cứ phải ép kiểu (long long)a[i] hoài.
3. Vòng for i cứ để i <= n, khỏi phải n - 1: khi $i = n$ thì $j = i + 1$ không thỏa $j \le n$ nên vòng trong tự dừng.

LONG_MIN khác LLONG_MIN

Em học viên của mình viết long long ans = LONG_MIN; – chỗ này nguy hiểm đấy. LONG_MIN là giá trị nhỏ nhất của kiểu long, mà long trên nhiều trình biên dịch (ví dụ Windows) chỉ có 4 byte thôi; long khác long long nhé, long long là 8 byte. Nên dòng đó phải là LLONG_MIN (2 chữ L) mới là giá trị nhỏ nhất của kiểu long long.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

long long a[100005], pre[100005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    long long ans = LLONG_MIN;
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            if(a[i] == a[j]){
                ans = max(ans, pre[j] - pre[i - 1]);
            }
        }
    }
    cout << ans;
    return 0;
}

n = int(input())
a = [0] + list(map(int, input().split()))
pre = [0] * (n + 1)
for i in range(1, n + 1):
    pre[i] = pre[i - 1] + a[i]
ans = None
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if a[i] == a[j]:
            s = pre[j] - pre[i - 1]
            if ans is None or s > ans:
                ans = s
print(ans)

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng $a$ và $pre$.
• Thời gian: $O(N^2)$. Với $N$ tối đa $10^5$ thì $(10^5)^2 = 10^{10}$, vượt quá $10^8$ tới $10^{10} / 10^8 = 100$ lần, tức là phải cả 100 giây mới chạy xong ⇒ TLE 30% test cuối.

Không gian$O(N)$

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

Cách 2Gom vị trí theo giá trị + giữ min prefix – O(N)

Giờ để mà ăn được 30% cuối khi $N$ tối đa $10^5$ thì các bạn hiểu thế này: mấu chốt để xác định được 1 đoạn con thỏa là phần tử đầu = phần tử cuối đúng không?

Như vậy nếu ta gom hết lại xem từng phần tử phân biệt xuất hiện tại những vị trí nào. Ví dụ xét số $5$ thấy nó xuất hiện tại các vị trí $2, 5, 8, 10$ (các vị trí tăng dần). Khi có các vị trí rồi thì muốn tính tổng đoạn từ vị trí này đến vị trí kia thì gọi prefix sum ra ngay, ví dụ tổng từ vị trí 2 đến vị trí 8 là $p[8] - p[1]$.

Vấn đề chỗ này các bạn phải hiểu về mặt toán học: ta muốn $p[R] - p[L-1]$ đạt giá trị lớn nhất. Đằng nào cũng xét từng vị trí $R$, như ví dụ trên $R$ lần lượt là $2, 5, 8, 10$:

• khi $R = 2$ thì trước đó không tồn tại vị trí $L$;
• khi $R = 5$ thì trước đó $L = 2$;
• khi $R = 8$ thì trước đó $L = 2, 5$;
• khi $R = 10$ thì trước đó $L = 2, 5, 8$.

Vậy khi xét đến từng vị trí $R$, ta cần tìm ở trước đó vị trí $L$ sao cho $p[R] - p[L-1]$ lớn nhất. Về mặt toán học, $p[R]$ đã cố định, nên ta cố gắng chọn $L$ đứng trước có $p[L-1]$ nhỏ nhất – nhỏ nhất để khi $p[R]$ trừ cho nó thì giá trị sẽ là lớn nhất.

Tóm lại

Với mỗi giá trị có các vị trí $pos_0 \lt pos_1 \lt \ldots \lt pos_{M-1}$: đi lần lượt $k = 1, 2, \ldots$, giữ biến $Min = \min(p[pos_0 - 1], \ldots, p[pos_{k-1} - 1])$; ứng viên là $p[pos_k] - Min$, rồi cập nhật $Min$ bằng $p[pos_k - 1]$. Chọn ra tổng lớn nhất trong tất cả các vị trí $R$ của tất cả các giá trị.

Mỗi giá trị phân biệt xuất hiện ở $M$ vị trí thì chỉ cần 1 vòng for $O(M)$ là ra kết quả. Làm vậy với tất cả các giá trị phân biệt, cộng tổng các $O(M)$ lại thì chính là $O(N)$. Còn việc thống kê các vị trí của từng giá trị thì dùng hash table (unordered_map trong C++, dict trong Python) cũng chỉ cần $O(N)$. Duyệt $i$ từ $1$ đến $n$ và push_back(i) thì danh sách vị trí tự động tăng dần luôn.

Minh hoạ

Em nhập dãy rồi bấm Tiếp: đầu tiên tính mảng $p$, sau đó xét từng giá trị xuất hiện từ 2 lần trở lên. Cột tô tím là các vị trí của giá trị đang xét, vàng là $R$ đang xét, xanh lá là vị trí $L$ cho $p[L-1]$ nhỏ nhất, vùng xanh dương nhạt là đoạn $(L, R)$ ứng viên.

Dãy a

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<long long> a(n + 1), p(n + 1, 0);
    unordered_map<long long, vector<int>> mp;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
        mp[a[i]].push_back(i);
    }
    long long res = LLONG_MIN;
    for(auto it = mp.begin(); it != mp.end(); ++it){
        vector<int> &pos = it->second;
        if(pos.size() > 1){
            long long Min = p[pos[0] - 1];
            for(int k = 1; k < pos.size(); ++k){
                res = max(res, p[pos[k]] - Min);
                Min = min(Min, p[pos[k] - 1]);
            }
        }
    }
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [0] * (n + 1)
    p = [0] * (n + 1)
    mp = {}
    for i in range(1, n + 1):
        a[i] = int(data[i])
        p[i] = p[i - 1] + a[i]
        mp.setdefault(a[i], []).append(i)
    res = None
    for pos in mp.values():
        if len(pos) > 1:
            Min = p[pos[0] - 1]
            for k in range(1, len(pos)):
                cur = p[pos[k]] - Min
                if res is None or cur > res:
                    res = cur
                Min = min(Min, p[pos[k] - 1])
    print(res)

main()

Giải thích một số chỗ trong code:

1. mp[a[i]].push_back(i): với mỗi giá trị, lưu danh sách các vị trí nó xuất hiện. Vì $i$ đi tăng dần nên danh sách này tự tăng dần.
2. Min = p[pos[0] - 1]: ban đầu chỉ có $L = pos[0]$ là ứng viên. Trong vòng for, trước tính ứng viên $p[pos[k]] - Min$ (lúc này $Min$ chỉ gồm các $L$ đứng trước $R = pos[k]$), sau mới đưa $p[pos[k] - 1]$ vào $Min$ để dùng cho các $R$ phía sau. Đảo thứ tự 2 dòng này là sai, vì khi đó có thể lấy $L = R$ (đoạn 1 phần tử), trong khi đề bắt $L \lt R$.
3. Kiểu long long: tổng tối đa $10^5 \cdot 10^9 = 10^{14}$, vượt int, nên $a$, $p$, $res$, $Min$ đều là long long.

C++▶ Chạy tay từng dòng codeGom vị trí theo giá trị bằng unordered_map, với mỗi R lấy p[R] trừ min p[L−1] đứng trước.

Dữ liệu vào (stdin) – sửa thoải mái7 3 3 3 3 1 11 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(false);

6 cin.tie(0); cout.tie(0);

7 int n;

8 cin >> n;

9 vector<long long> a(n + 1), p(n + 1, 0);

10 unordered_map<long long, vector<int>> mp;

11 for(int i = 1; i <= n; ++i){

12 cin >> a[i];

13 p[i] = p[i - 1] + a[i];

14 mp[a[i]].push_back(i);

15 }

16 long long res = LLONG_MIN;

17 for(auto it = mp.begin(); it != mp.end(); ++it){

18 vector<int> &pos = it->second;

19 if(pos.size() > 1){

20 long long Min = p[pos[0] - 1];

21 for(int k = 1; k < pos.size(); ++k){

22 res = max(res, p[pos[k]] - Min);

23 Min = min(Min, p[pos[k] - 1]);

24 }

25 }

26 }

27 cout << res;

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho các mảng $a$, $p$ và hash table chứa tổng cộng $N$ vị trí.
• Thời gian: $O(N)$ nhập dữ liệu và gom vị trí (thao tác trên unordered_map trung bình $O(1)$), cộng $\sum O(M) = O(N)$ để xét tất cả các nhóm ⇒ toàn bài chỉ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Tự làm "tool check" để kiểm tra

Khi code xong cách 2 muốn biết có đúng hay không, các bạn lấy chính code cách 1 (hoặc một code vét cạn $O(N^3)$ viết kiểu gì nhanh gọn đơn giản nhất, không phải nặng đầu suy nghĩ) làm "trọng tài": random test nhỏ ($N \le 500$), chạy cả 2 cách và so kết quả; test nào lệch thì in ra để check lại. Khi random nhớ đảm bảo luôn có ít nhất 1 cặp bằng nhau (ví dụ gán $a[n]$ bằng một phần tử ngẫu nhiên đã có). Đúng rồi thì thử thêm $N = 10^5$ (chỉ chạy cách 2) để xem có bị quá 1 giây không.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên ($n \le 40$, có cả số âm, luôn có ít nhất 1 cặp bằng nhau), so với code vét cạn – khớp hết. Với $n = 10^5$: cách 2 bản C++ chạy khoảng 0.2 giây, bản Python khoảng 0.25 giây; cách 1 (C++) mất khoảng 9 giây ⇒ TLE đúng như phân tích.

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 😇