Dãy Số 4 (SEQ4)
Đề bài
SEQ4 – Dãy số 4
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 512 megabyte
Cho dãy số dương $a_1, a_2, \ldots, a_n$ và số nguyên $k$.
Yêu cầu: Tìm dãy con liên tiếp dài nhất có tổng bằng $k$.
Dữ liệu:
- Dòng đầu tiên chứa hai số nguyên $n$ $(0 \lt n \le 10^6)$ và $k$ $(0 \lt k \le 10^9)$.
- Dòng thứ 2 là các số nguyên dương $a_1, a_2, \ldots, a_n$.
Kết quả: Một dòng duy nhất ghi độ dài của dãy con tìm được.
7 7
4 3 2 1 1 1 64Lời mở đầu
Bài này là "người anh em" của bài Dãy Số 3 (SEQ3) cùng series trên NTUCoder: cũng xoay quanh dãy con liên tiếp, nhưng thay vì tìm tổng lớn nhất thì giờ ta phải tìm đoạn dài nhất có tổng đúng bằng $k$. Bài này mình sẽ đi một chặng khá dài: từ vét cạn, qua cửa sổ trượt, mảng cộng dồn, rồi mới tới tìm kiếm nhị phân và cấu trúc cây set. Mỗi bước đều là một kỹ thuật rất hay gặp nên các bạn kiên nhẫn đọc hết nha 😇.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy 4 3 2 1 1 1 6 với $k = 7$ có 3 đoạn liên tiếp có tổng bằng 7:
- $a_1 + a_2 = 4 + 3 = 7$ → độ dài 2;
- $a_2 + a_3 + a_4 + a_5 = 3 + 2 + 1 + 1 = 7$ → độ dài 4;
- $a_6 + a_7 = 1 + 6 = 7$ → độ dài 2.
Đoạn dài nhất có độ dài 4 nên in ra 4. Lưu ý chữ "liên tiếp" nha: chọn $1 + 1 + 1 + 4$ cũng ra 7 nhưng các số đó không nằm liền nhau nên không tính.
3 100 / 1 2 3 thì đáp án là 0. Tất cả code trong bài đều theo quy ước này.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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn mọi dãy con liên tiếp – O(N²)
Một ý tưởng cơ bản và dễ dàng nhất mà nhiều người nghĩ ra đó là: xét tất cả các dãy con liên tiếp, với mỗi dãy con tính tổng rồi so sánh với $K$. Nếu bằng $K$ thì tính độ dài dãy con đó và so với biến Max đang có (ban đầu Max = 0), lớn hơn thì cập nhật. Sau cùng in Max.
Với ví dụ của đề ($K = 7$), mình liệt kê một phần để các bạn thấy quy trình:
4 ⇒ 4 ≠ K, Max = 0
4, 3 ⇒ 7 = K ⇒ Max = 2
4, 3, 2 ⇒ 9 ≠ K, Max = 2
… (4, 3, 2, 1 ⇒ 10; … ; cả dãy ⇒ 18)
Bắt đầu tại vị trí 2:
3 ⇒ 3 · 3, 2 ⇒ 5 · 3, 2, 1 ⇒ 6
3, 2, 1, 1 ⇒ 7 = K ⇒ Max = 4
3, 2, 1, 1, 1 ⇒ 8 · 3, 2, 1, 1, 1, 6 ⇒ 14
Bắt đầu tại vị trí 3, 4, 5: không đoạn nào ra 7
Bắt đầu tại vị trí 6: 1 ⇒ 1 · 1, 6 ⇒ 7 = K nhưng độ dài 2 < 4 ⇒ Max vẫn = 4
Bắt đầu tại vị trí 7: 6 ⇒ 6
⇒ In ra Max = 4.
Cài đặt: tại mỗi vị trí $i$, ta lần lượt cộng vào biến sum các phần tử từ $i$ đến cuối mảng; khi đó sum lần lượt là tổng của các dãy con bắt đầu tại $i$. Thấy sum == k thì độ dài đoạn từ $i$ đến $j$ là $j - i + 1$, so sánh cập nhật Max.
Source code để các bạn tham khảo nếu làm theo hướng này (code thứ 1):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int Max = 0;
for(int i = 1; i <= n; ++i){
long long sum = 0;
for(int j = i; j <= n; ++j){
sum += a[j];
if(sum == k){
Max = max(Max, j - i + 1);
}
}
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
Max = 0
for i in range(1, n + 1):
s = 0
for j in range(i, n + 1):
s += a[j]
if s == k:
Max = max(Max, j - i + 1)
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- 2 dòng đầu hàm main (
ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất khi code C++. Bài này input có thể lên tới 1 triệu số nên kinh nghiệm là nên thêm 2 dòng này vào (các bạn gõ mấy từ này lên Google sẽ ra rất nhiều bài giải thích nhé). - Mình dùng
vectorthay vì mảng thường. Kinh nghiệm của mình: số phần tử từ khoảng $3 \cdot 10^5$ trở lên thì đừng khai báo mảng tĩnh bên trong hàm vì dễ bị tràn bộ nhớ stack (stack overflow). Dùng mảng động (vector) để lấy bộ nhớ heap, hoặc khai báo mảng là biến toàn cục cũng được.
Các bạn bấm Tiếp ▶ để xem từng đoạn $[i, j]$ được xét như thế nào nhé (vàng = $a_j$ vừa cộng vào, tím = đoạn đang xét, xanh = đoạn tốt nhất hiện tại):
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho mảng $a$ (thực ra là $N + 1$ phần tử vì bỏ index 0, nhưng $O(N + 1)$ cũng là $O(N)$ theo quy tắc cộng Big-O).
- Thời gian: $O(N)$ đọc input cộng với bước xử lý. Vòng
for ilặp $N$ lần, với mỗi $i$ thìfor jlặp từ $i$ đến cuối mảng: $i = 1$ lặp $N$ lần, $i = 2$ lặp $N - 1$ lần, …, $i = N$ lặp 1 lần. Tổng là $1 + 2 + \ldots + N = \dfrac{N(N+1)}{2}$, bỏ hằng số và thành phần nhỏ ⇒ $O(N^2)$.
Tận dụng "số dương": dừng sớm
Code ở trên là cho trường hợp tổng quát (dãy có thể có số âm). Còn bài này đề nói rõ dãy toàn số nguyên dương, nên ta tối ưu thêm được một chút: hễ sum >= k thì dừng luôn đoạn bắt đầu tại $i$ để chuyển sang $i + 1$. Vì các số đều dương, cộng thêm vào thì sum chỉ có lớn hơn nữa, đã $\ge k$ rồi thì không bao giờ quay lại bằng $k$ được. (Nếu dãy có số âm thì không dừng sớm như vậy được nha.)
Code thứ 2:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<long long> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
int Max = 0;
for(int i = 1; i <= n; ++i){
long long sum = 0;
for(int j = i; j <= n; ++j){
sum += a[j];
if(sum >= k){
if(sum == k){
Max = max(Max, j - i + 1);
}
break;
}
}
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
Max = 0
for i in range(1, n + 1):
s = 0
for j in range(i, n + 1):
s += a[j]
if s >= k:
if s == k:
Max = max(Max, j - i + 1)
break
print(Max)
main()Và thật bất ngờ là code này nộp lên lại Accepted, thời gian chạy còn thuộc loại nhanh nhất 😂. Thực sự mình cũng bất ngờ, có lẽ là do test của bài này yếu thôi, chứ cách này mà AC là điều mình không bao giờ nghĩ đến.
sum >= k. Nếu điều đó không bao giờ xảy ra thì sao? Ví dụ $N = 10^6$, $K = 10^9$ và toàn bộ phần tử đều bằng 1: cộng lại kiểu gì cũng nhỏ hơn $K$, nên code phải xét đủ mọi đoạn y như code thứ 1, gần 3 tiếng mới in ra 0. Test này vẫn nằm trong giới hạn đề ⇒ test của bài đúng là yếu.Với riêng tình huống đó ta có thể vá thêm: lúc đọc input cộng hết vào một biến tổng; nếu tổng cả dãy mà còn $\lt K$ thì kết luận 0 luôn. Nhưng mẹo vặt kiểu này chỉ đúng khi dãy toàn số dương và cũng không cứu được mọi trường hợp. Ta nên cố gắng tìm cách xử lý được cả trường hợp tổng quát, đó mới là code tối ưu.
Cách 2Xét độ dài từ lớn về bé – cửa sổ trượt & mảng cộng dồn
Ta vẫn xét trường hợp tổng quát (dãy có thể có số âm). Đề cần độ dài dài nhất, vậy sao ta không xét các đoạn theo độ dài từ lớn về bé? Khi đó đoạn đầu tiên có tổng bằng $K$ chắc chắn là đoạn dài nhất, ta in ra và dừng ngay, không cần xét đến tận cùng như cách 1.
Với ví dụ của đề:
Độ dài 6: 4, 3, 2, 1, 1, 1 ⇒ 12 · 3, 2, 1, 1, 1, 6 ⇒ 14
Độ dài 5: 4, 3, 2, 1, 1 ⇒ 11 · 3, 2, 1, 1, 1 ⇒ 8 · 2, 1, 1, 1, 6 ⇒ 11
Độ dài 4: 4, 3, 2, 1 ⇒ 10 · 3, 2, 1, 1 ⇒ 7 = K ⇒ in 4 và dừng!
(không cần xét 2 đoạn độ dài 4 còn lại, 5 đoạn độ dài 3, 6 đoạn độ dài 2, 7 đoạn độ dài 1)
Bài toán nhỏ: liệt kê các đoạn [L, R] theo độ dài giảm dần
Chia nhỏ vấn đề cho đơn giản: trước hết hãy làm bài toán nhập $N$, in ra vị trí $L, R$ của các đoạn con theo độ dài từ lớn về bé. Ví dụ $N = 3$ thì in ra: L = 1, R = 3 · L = 1, R = 2 · L = 2, R = 3 · L = 1, R = 1 · L = 2, R = 2 · L = 3, R = 3.
Các bạn thử tự làm trước nhé, rồi tham khảo code thứ 3 của mình:
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
int l = 1, r = n;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
cout << "L = " << l << ", R = " << r << endl;
l++;
r++;
}
l = 1;
r = n - i;
cout << endl;
}
return 0;
}n = int(input())
l, r = 1, n
for i in range(1, n + 1):
for j in range(1, i + 1):
print("L = " + str(l) + ", R = " + str(r))
l += 1
r += 1
l = 1
r = n - i
print()Giải thích nhanh: với $N$ bất kỳ có $N$ trường hợp độ dài (từ $N$ về 1), nên for i chạy từ 1 đến $N$. Ứng với $i$ thì có đúng $i$ đoạn có độ dài $N - i + 1$ (khi $i = 1$ có 1 đoạn dài $N$, $i = 2$ có 2 đoạn dài $N - 1$, …), nên for j chạy $i$ lần. Ban đầu $L = 1, R = N$; mỗi lần in xong thì l++, r++ để tịnh tiến đoạn sang phải. Xét xong một độ dài thì reset $L = 1$, $R = N - i$ (độ dài giảm đi 1). Các bạn chạy tay sẽ thấy rõ:
Tính tổng mỗi đoạn bằng cửa sổ trượt (Sliding Window)
Đã có $L, R$ rồi thì đừng có chạy thêm vòng for từ $L$ đến $R$ để tính tổng nhé, như vậy là $O(N^3)$, còn tệ hơn vét cạn ban đầu! Ở đây ta dùng kỹ thuật cửa sổ trượt. Ví dụ $N = 4$:
- $i = 1$: 1 đoạn độ dài 4 là $[1, 4]$, chính là tổng cả mảng, tính luôn lúc đọc input.
- $i = 2$: 2 đoạn độ dài 3. Tổng $[1, 3]$ = tổng $[1, 4]$ bỏ đi $a_4$. Từ $[1, 3]$ sang $[2, 4]$: bỏ $a_1$, nhận thêm $a_4$.
- $i = 3$: 3 đoạn độ dài 2. Tổng $[1, 2]$ = tổng $[1, 3]$ bỏ $a_3$. Rồi $[2, 3]$ = $[1, 2]$ bỏ $a_1$ thêm $a_3$; $[3, 4]$ = $[2, 3]$ bỏ $a_2$ thêm $a_4$.
sum1 là tổng đoạn đầu tiên của mỗi độ dài ($[1, N]$, $[1, N-1]$, …): mỗi lần giảm độ dài thì sum1 -= a[R + 1]. Trong cùng một độ dài, sum2 bắt đầu bằng sum1; mỗi lần trượt L++, R++ thì sum2 -= a[L - 1] (bỏ phần tử vừa rời cửa sổ) và sum2 += a[R] (nhận phần tử mới vào). Gặp sum2 == k thì in độ dài $N - i + 1$ và kết thúc.Em nhập dãy và $k$ rồi bấm Tiếp để xem cửa sổ co lại và trượt như thế nào:
Source code theo tư tưởng này (code thứ 4):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, sum1 = 0, sum2;
cin >> n >> k;
vector<long long> a(n + 2);
for(int i = 1; i <= n; ++i){
cin >> a[i];
sum1 += a[i];
}
a[n + 1] = 0;
int l = 1, r = n;
for(int i = 1; i <= n; ++i){
sum1 -= a[r + 1];
sum2 = sum1;
for(int j = 1; j <= i; ++j){
if(sum2 == k){
cout << n - i + 1;
return 0;
}
l++;
r++;
sum2 -= a[l - 1];
sum2 += a[r];
}
l = 1;
r = n - i;
}
cout << 0;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] * (n + 2)
sum1 = 0
for i in range(1, n + 1):
a[i] = int(data[1 + i])
sum1 += a[i]
a[n + 1] = 0
l, r = 1, n
for i in range(1, n + 1):
sum1 -= a[r + 1]
sum2 = sum1
for j in range(1, i + 1):
if sum2 == k:
print(n - i + 1)
return
l += 1
r += 1
sum2 -= a[l - 1]
sum2 += a[r]
l = 1
r = n - i
print(0)
main()Giải thích một số chỗ trong code ở trên:
- Ví dụ $N = 5$ thì
sum1lần lượt là tổng các đoạn $[1, 5]$, $[1, 4]$, $[1, 3]$, $[1, 2]$, $[1, 1]$. Cònsum2khởi tạo bằngsum1, rồi sau mỗi lầnl++, r++thì trừa[l - 1], cộnga[r]. Chẳng hạnsum1= tổng $[1, 4]$ thì sau khi trượt,sum2 -= a[1]; sum2 += a[5];⇒sum2= tổng $[2, 5]$. - Lần đầu tiên ($R = N$) ta có
sum1 -= a[N + 1], nên vector phải có $N + 2$ phần tử (index $0..N+1$) và nhớ gána[n + 1] = 0để trừ đi 0 thìsum1vẫn là tổng cả mảng. Ngoài ra lần trượt cuối cùng của mỗi độ dài cũng đọc tớia[N + 1](giá trị đó không dùng đến) nên càng cần đủ $N + 2$ phần tử. - Có thể không có đoạn nào tổng bằng $K$, vì vậy cuối hàm main mình để
cout << 0;. Nếu đã tìm thấy thì chương trìnhreturn 0ngay rồi, không chạy xuống tới dòng đó được.
Gọn hơn với mảng cộng dồn (Prefix Sum)
Nếu thấy cửa sổ trượt làm code hơi rối thì ta có cách gọn hơn để tính tổng đoạn $[L, R]$: kỹ thuật Prefix Sum (mảng cộng dồn). Đây cũng chính là hướng mở đường cho cách tối ưu ở phần sau. Với dãy của đề, mảng cộng dồn $P$ là:
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| a[i] | – | 4 | 3 | 2 | 1 | 1 | 1 | 6 |
| P[i] = P[i−1] + a[i] | 0 | 4 | 7 | 9 | 10 | 11 | 12 | 18 |
Vì sao lại trừ $P[L - 1]$ mà không phải $P[L]$? Các bạn kẻ trục số ra là thấy:
$P[R] - P[L]$ chỉ là tổng từ $L + 1$ đến $R$ (mất $a_L$), nên phải trừ $P[L - 1]$ thì phần còn lại mới bắt đầu đúng từ $L$.
Ta cũng không cần tạo mảng $P$ riêng: khởi tạo a[0] = 0, đọc a[i] xong làm luôn a[i] += a[i - 1] là mảng $a$ thành mảng cộng dồn. Ghép với code thứ 3 (liệt kê $L, R$) là xong, code thứ 5:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<long long> a(n + 1);
a[0] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] += a[i - 1];
}
int l = 1, r = n;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
if(a[r] - a[l - 1] == k){
cout << n - i + 1;
return 0;
}
l++;
r++;
}
l = 1;
r = n - i;
}
cout << 0;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] * (n + 1)
for i in range(1, n + 1):
a[i] = int(data[1 + i]) + a[i - 1]
l, r = 1, n
for i in range(1, n + 1):
for j in range(1, i + 1):
if a[r] - a[l - 1] == k:
print(n - i + 1)
return
l += 1
r += 1
l = 1
r = n - i
print(0)
main()a[1] += a[0], nên a[0] phải có giá trị rõ ràng là 0 (vector đã tự khởi tạo 0, nhưng gán rõ ràng cho chắc, nhất là khi dùng mảng thường).Đánh giá độ phức tạp của code thứ 4 và thứ 5:
- Không gian: $O(N)$.
- Thời gian: trường hợp xấu nhất vẫn là $O(N^2)$, đó là khi không có đoạn nào tổng bằng $K$, phải xét hết mọi đoạn mới kết luận 0. Điểm hơn cách 1 là nếu sớm tìm thấy thì dừng ngay, và đáp án chắc chắn là dài nhất.
Mình bật mí trước: trong ngữ cảnh bài này (toàn số dương), từ mảng cộng dồn ta có thể đưa ra cách $O(N \log N)$ để vượt qua mọi test trong giới hạn đề, chứ không phải AC nhờ may mắn như code thứ 2. Các bạn thử nghĩ trước rồi xem tiếp nhé 😉.
Cách 3Mảng cộng dồn + tìm kiếm nhị phân – O(N log N)
Các bạn có để ý: khi dãy toàn số dương thì mảng cộng dồn là dãy tăng dần không? Dãy 4 3 2 1 1 1 6 có mảng cộng dồn 0 4 7 9 10 11 12 18, tăng dần luôn. Mà dãy đã có thứ tự thì ta dùng được tìm kiếm nhị phân (binary search), nhanh hơn hẳn tìm tuần tự.
Vậy với mỗi vị trí $R$, ta tìm trong $P[0], P[1], \ldots, P[R - 1]$ xem có giá trị bằng $P[R] - K$ không. Nếu có ở vị trí $p = L - 1$ thì độ dài đoạn là $R - L + 1 = R - p$. Duyệt mọi $R$, lấy độ dài lớn nhất.
Vì $P$ tăng ngặt (số dương nên không có 2 giá trị trùng nhau), mỗi $R$ có nhiều nhất một vị trí $p$ thoả mãn, tìm bằng nhị phân mất $O(\log N)$. Duyệt $N$ vị trí $R$ ⇒ tổng cộng $O(N \log N)$.
Minh hoạ: tìm P[R] − K bằng tìm kiếm nhị phân
Em nhập $k$ và dãy số rồi bấm Tiếp. Ứng với mỗi $R$ (viền cam), vùng tìm kiếm $[lo, hi)$ tô tím, ô mid tô vàng, tìm thấy thì tô xanh:
Source code để các bạn tham khảo nếu làm theo hướng này (code thứ 6):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, Max = 0;
cin >> n >> k;
vector<long long> a(n + 1);
a[0] = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
a[i] += a[i - 1];
auto it = lower_bound(a.begin(), a.begin() + i, a[i] - k);
if(it != a.begin() + i && *it == a[i] - k){
Max = max(Max, (long long)(i - (it - a.begin())));
}
}
cout << Max;
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
a = [0] * (n + 1)
Max = 0
for i in range(1, n + 1):
a[i] = int(data[1 + i]) + a[i - 1]
p = bisect_left(a, a[i] - k, 0, i) # tìm trong a[0..i-1]
if p != i and a[p] == a[i] - k:
Max = max(Max, i - p)
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- Tại mỗi vị trí $R$ ta chỉ tìm ở bên trái nó, nên kết hợp xử lý ngay trong vòng đọc input: đọc
a[i], cộng dồna[i] += a[i - 1], lúc nàya[i]chính là $P[R]$ với $R = i$. lower_bound(start, end, value)tìm nhị phân trong đoạn[start, end)phần tử đầu tiên $\ge$ value; không có thì trả vềend. Ở đâystart = a.begin()(tính cả $P[0] = 0$),end = a.begin() + i(chỉ tìm bên trái $i$),value = a[i] - k.- Tìm thấy (
it != a.begin() + i) thì vẫn phải kiểm tra thêm*it == a[i] - k, vìlower_boundtrả về phần tử $\ge$ value, có thể là phần tử lớn hơn chứ không bằng. (Dùngbinary_searchcũng được, nhưng mình quenlower_boundvì nó làm được nhiều việc hơn ahihi.) - Vị trí tìm được là
it - a.begin()(con trỏ trừ địa chỉ phần tử đầu ra index), chính là $L - 1$. Độ dài $R - (L - 1)$ =i - (it - a.begin()). Phép trừ iterator trả về kiểulongnên mình ép vềlong longđểmaxcùng kiểu vớiMax.
lower_bound tìm từ a.begin() + 1, tức là bỏ qua $P[0] = 0$. Khi đó những đoạn bắt đầu từ vị trí 1 ($L - 1 = 0$) không bao giờ được xét. Test của đề không bị ảnh hưởng (đoạn dài nhất là $[2, 5]$), nhưng thử 2 7 / 4 3 thì đáp án đúng là 2 (cả dãy), còn bản cũ in 0. Bản trong bài đã sửa thành tìm từ a.begin(), các bạn để ý nha.Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ như các cách trước.
- Thời gian: duyệt $N$ vị trí, mỗi vị trí tìm nhị phân $O(\log N)$ ⇒ $O(N \log N)$. Với $N = 10^6$ thì $\log_2 10^6 \approx 20$ ("nhị" phân là cơ số 2 đó các bạn), tức khoảng $2 \cdot 10^7$ phép tính, yên tâm dưới ngưỡng 1 giây ⇒ Accepted.
Cách 4Nếu dãy có cả số âm? Dùng set – O(N log N)
Cách 3 làm được là nhờ dãy toàn số dương nên mảng cộng dồn tăng dần. Nếu dãy có số âm, ví dụ 2 -3 5 8 -10, thì mảng cộng dồn là 2 -1 4 12 2, chẳng có thứ tự gì cả, không tìm nhị phân được nữa. Vậy trường hợp tổng quát làm sao để vẫn $O(N \log N)$?
Lúc này ta dùng cấu trúc dữ liệu dạng cây: dữ liệu đưa vào lộn xộn thì cây tự sắp xếp lại; thêm một phần tử tốn $O(\log N)$, tìm kiếm cũng $O(\log N)$. Trong C++ có sẵn set (cây đỏ đen). Mỗi phần tử của set là cặp {value, index}: value là tổng cộng dồn, index là vị trí của nó. Ta cũng không cần mảng nữa:
- Đọc từng số vào
x, cộng dồn vàosum(đây là $P[i]$). - Tìm trong set phần tử có
value = sum - k. Có thìi - it->indexlà độ dài một đoạn thoả mãn, so vớiMax. - Đưa
{sum, i}vào set cho các lần tìm sau. Nếu set đã cóvaluenày rồi thì set không nhận nữa, nhờ đó set luôn giữ index nhỏ nhất của mỗi giá trị ⇒i - indexlớn nhất.
Lưu ý: ta phải quy định các phần tử trong set so sánh với nhau theo value, nên cần viết thêm các toán tử so sánh cho struct.
Source code để các bạn tham khảo nếu làm theo hướng này (code thứ 7):
#include <bits/stdc++.h>
using namespace std;
struct Data{
long long value, index;
};
bool operator ==(const Data &a, const Data &b){
return a.value == b.value;
}
bool operator <(const Data &a, const Data &b){
return a.value < b.value;
}
bool operator >(const Data &a, const Data &b){
return a.value > b.value;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k, x, Max = 0, sum = 0;
cin >> n >> k;
set<Data> se;
se.insert(Data{0, 0});
for(long long i = 1; i <= n; ++i){
cin >> x;
sum += x;
auto it = se.find(Data{sum - k});
if(it != se.end()){
Max = max(Max, i - it->index);
}
se.insert(Data{sum, i});
}
cout << Max;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
first = {0: 0} # tổng cộng dồn -> vị trí xuất hiện ĐẦU TIÊN
Max = 0
s = 0
for i in range(1, n + 1):
s += int(data[1 + i])
j = first.get(s - k)
if j is not None:
Max = max(Max, i - j)
if s not in first:
first[s] = i
print(Max)
main()Giải thích một số chỗ trong code ở trên:
- Tham số
const Data &a: truyền tham chiếu (&) để khỏi tạo bản copy của struct (đỡ tốn thời gian), cònconstđể lỡ vô tình sửa dữ liệu thì trình biên dịch báo lỗi. Bỏconstcũng được, do thói quen cẩn thận mình để vậy thôi ^^. se.insert(Data{0, 0})trước vòng lặp: đây là $P[0] = 0$ ở vị trí 0, cùng lý do như cảnh báo ở cách 3, để các đoạn bắt đầu từ vị trí 1 cũng được xét (bản gốc trên Facebook thiếu dòng này nên test2 7/4 3cũng ra 0).- Bản Python không có sẵn cây cân bằng nên mình dùng
dictlưu "tổng cộng dồn → vị trí xuất hiện đầu tiên", ý tưởng y hệt (tra cứu trung bình $O(1)$).
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ do set chứa tối đa $N + 1$ phần tử (chỉ các giá trị phân biệt). Thực tế tốn hơn mảng vì mỗi nút trong cây còn phải lưu thêm các con trỏ liên kết.
- Thời gian: mỗi phần tử gọi
find$O(\log N)$ vàinsert$O(\log N)$, cộng thêm chi phí cân bằng cây (cây đỏ đen phải tự cân bằng để luôn giữ được $O(\log N)$ kể cả khi dữ liệu vào tăng/giảm dần). Tổng quát vẫn kết luận $O(N \log N)$.
Bài này còn có cách với độ phức tạp tốt hơn nữa, khi nào có thời gian mình sẽ update thêm cho các bạn nhé 😉.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét