Đoạn Con (DPSUBSEG)
Đề bài
DPSUBSEG – Đoạn Con · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Cho dãy $A$ gồm $N$ số nguyên $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$. Một đoạn con $a[i..j]$ có độ dài là $j - i + 1$ $(1 \le i \le j \le N)$. Đoạn con được gọi là đoạn xen kẽ nếu hai phần tử bất kỳ nào đứng cạnh nhau đều trái dấu.
Yêu cầu: Với mỗi vị trí $i$ $(1 \le i \le N)$ hãy tính độ dài dãy con xen kẽ dài nhất của dãy $A$ bắt đầu ở vị trí $i$.
Dữ liệu nhập:
- Dòng đầu ghi $T$ là số lượng bộ test $(1 \le T \le 20)$.
- Trong $2T$ dòng tiếp theo ghi thông tin về các bộ test: dòng đầu ghi $N$, dòng hai ghi dãy $A$.
Kết quả:
- Gồm $T$ dòng, mỗi dòng ghi $N$ số nguyên lần lượt là độ dài dãy con xen kẽ dài nhất tìm được tương ứng với mỗi test trong input.
Ràng buộc:
- 50% test: $1 \le N \le 1000$.
- 50% test: $N \le 100.000$.
1
6
-5 -4 -3 1 -2 -11 1 3 2 1 1Lời mở đầu
Bài này nhìn đề thì đơn giản, cách "làm theo đề" ai cũng nghĩ ra được ngay. Nhưng chính vì vậy mà nó là một bài rất hay để các bạn thấy được cái dở của cách làm ngây thơ nằm ở đâu, và chỉ cần một nhận xét nhỏ là ta đã kéo được độ phức tạp từ $O(T \cdot N^2)$ xuống còn $O(T \cdot N)$ 😎.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Dãy là -5 -4 -3 1 -2 -1:
- Bắt đầu ở
-5: ngay sau nó là-4cùng dấu âm ⇒ đoạn xen kẽ chỉ có mỗi-5⇒ độ dài 1. - Bắt đầu ở
-4: sau nó là-3cũng âm ⇒ 1. - Bắt đầu ở
-3:-3, 1trái dấu,1, -2trái dấu,-2, -1cùng dấu thì dừng ⇒ đoạn-3 1 -2⇒ 3. - Bắt đầu ở
1: đoạn1 -2⇒ 2. Bắt đầu ở-2: 1. Bắt đầu ở-1(phần tử cuối): 1.
Vậy output là 1 1 3 2 1 1. Lưu ý một chỗ: số 0 thì sao? Code của mình coi 0 là "không âm" (nhóm $\ge 0$), tức là cùng phe với số dương – đây là cách hiểu đã được nộp AC trên hệ thống.
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 1Làm theo đề, xét từng vị trí – O(T·N²)
Theo mô tả của đề thì một cách xử lý hết sức đơn giản đó là: cứ xét lần lượt từng vị trí $i$ của mảng, rồi từ vị trí đó đi tiếp lên trên, đếm xem có bao nhiêu phần tử còn trái dấu với phần tử đứng trước nó; chỉ dừng lại khi gặp cặp cùng dấu. In kết quả đếm đó ra, rồi lặp lại y chang quy trình trên cho vị trí $i + 1$, cứ thế xét hết mảng.
for j chạy từ i + 1 và bản chất ta so sánh a[j] với a[j - 1]. Ví dụ $i = 0$ thì $j$ bắt đầu từ 1: so a[1] với a[0], rồi j++ lên 2 thì so a[2] với a[1], rồi a[3] với a[2], a[4] với a[3]…Hai số "trái dấu" nghĩa là một số
< 0 và số kia >= 0.main giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài giải thích). Bài này có tối đa 20 bộ test, mỗi bộ tối đa $10^5$ số ⇒ có thể phải đọc tới $20 \cdot 10^5 = 2 \cdot 10^6$ số, nên nhớ thêm 2 dòng này vào. Mình thử với cùng code tối ưu: có 2 dòng này thì AC dưới 200 ms, bỏ đi thì vẫn AC nhưng hơn 700 ms – để các bạn thấy nó giúp nhanh hơn thế nào.Trong bài gốc trên Facebook mình có để thêm 2 dòng
freopen("doancon.inp", ...) / freopen("doancon.out", ...) để đọc/ghi file; còn trên hệ thống chấm online thì đọc/ghi chuẩn nên ở code dưới đây mình bỏ 2 dòng đó đi.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(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n; ++i){
int cnt = 1;
for(int j = i + 1; j < n; ++j){
if((a[j] < 0 && a[j - 1] >= 0) || (a[j] >= 0 && a[j - 1] < 0)){
cnt++;
}
else{
break;
}
}
cout << cnt << " ";
}
cout << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
n = int(data[p]); p += 1
a = [int(x) for x in data[p:p + n]]; p += n
res = []
for i in range(n):
cnt = 1
for j in range(i + 1, n):
if (a[j] < 0 and a[j - 1] >= 0) or (a[j] >= 0 and a[j - 1] < 0):
cnt += 1
else:
break
res.append(cnt)
out.append(' '.join(map(str, res)))
print('\n'.join(out))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ để lưu mảng $a$.
- Thời gian: chạy $T$ lần cho $T$ bộ test; mỗi bộ test tốn $N$ lần đọc dữ liệu, sau đó 2 vòng lặp lồng nhau – trong tình huống xấu nhất mọi cặp kề nhau đều trái dấu thì bước này chạy đủ $\dfrac{N(N-1)}{2}$ lần. Tổng cộng $T \cdot \left(N + \dfrac{N(N-1)}{2}\right)$ lần lặp.
Về lý thuyết: $\dfrac{N(N-1)}{2} = (N^2 - N) \cdot 0.5$, theo quy tắc nhân Big-O bỏ hằng số còn $N^2 - N$, theo quy tắc cộng chỉ lấy thành phần lớn nhất là $N^2$ (cái $+N$ của bước đọc input cũng bỏ qua luôn). Vậy độ phức tạp là $O(T \cdot N^2)$.
Cách 2Tận dụng đoạn đã xét, in lùi – O(T·N)
Cách làm ở trên có chỗ dở mà ta dễ dàng nhìn ra. Giả sử khi xét tại vị trí $i = 3$, ta đi lên tới vị trí $8$ và thấy $8$ là vị trí cuối cùng thoả mãn (vì a[8] và a[9] cùng dấu). Vậy từ vị trí 3 đến 8 là một đoạn mà mọi cặp kề nhau đều trái dấu, tại vị trí 3 ta in ra $8 - 3 + 1 = 6$.
Rồi các bạn xem nhé: chắc chắn tại các vị trí $4, 5, 6, 7, 8$ sẽ lần lượt in ra $5, 4, 3, 2, 1$ đúng không? Vì từ 3 đến 8 có 6 phần tử thì từ 4 đến 8 có 5 phần tử, từ 5 đến 8 có 4 phần tử… Vậy mà cách 1 sau khi xét xong vị trí 3 lại sang vị trí 4 và lặp lại quy trình cũ: so 4 với 5, 5 với 6, 6 với 7… chẳng tận dụng gì kết quả trước đó. Đó là cái dở!
start là vị trí bắt đầu của đoạn xen kẽ hiện tại. Cho $i$ chạy lên, tới khi gặp vị trí $i$ mà a[i] và a[i + 1] cùng dấu (đoạn bị "gãy" ngay sau $i$) thì ta in ra các kết quả từ i - start + 1 giảm dần về 1 – đó chính là đáp án của các vị trí start, start + 1, ..., i. Sau đó cập nhật start = i + 1 và đi tiếp.Ví dụ trên:
start = 3, gặp $i = 8$ gãy ⇒ in 6 5 4 3 2 1, rồi start = 9.a[N] = a[N - 1]. Khi xét tới $i = N - 1$ thì so với a[N] chắc chắn cùng dấu ⇒ luôn gãy ở cuối ⇒ in được đoạn cuối. Ví dụ mảng 10 phần tử (chỉ số 0..9), start = 3 và từ 3 tới 9 đều xen kẽ: tới $i = 9$ thấy a[9] cùng dấu với a[10] ⇒ in từ $9 - 3 + 1 = 7$ về 1 cho các vị trí 3..9, rồi vòng for kết thúc.Minh hoạ cắt dãy thành các đoạn xen kẽ
Các bạn nhập dãy rồi bấm Tiếp để xem $i$ chạy, chỗ nào "gãy" thì cả đoạn từ start tới $i$ được điền đáp án giảm dần về 1:
if(a[i] * a[i + 1] >= 0) là xong. Nhưng mình không làm vậy vì sợ tình huống 1 số là 0, 1 số âm thì tích vẫn ra 0 ⇒ thoả điều kiện "cùng dấu", trong khi thực tế (theo quy ước 0 thuộc nhóm không âm) thì 2 số này trái dấu. Chưa kể $|a_i| \le 10^9$ thì tích lên tới $10^{18}$, kiểu int sẽ tràn số. Nên thôi mình cứ ghi rõ ra như code cho chắc hihi.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(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n + 1];
for(int i = 0; i < n; ++i){
cin >> a[i];
}
a[n] = a[n - 1];
int start = 0;
for(int i = 0; i < n; ++i){
if((a[i] < 0 && a[i + 1] < 0) || (a[i] >= 0 && a[i + 1] >= 0)){
for(int j = i - start + 1; j >= 1; --j){
cout << j << " ";
}
start = i + 1;
}
}
cout << endl;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
t = int(data[p]); p += 1
out = []
for _ in range(t):
n = int(data[p]); p += 1
a = [int(x) for x in data[p:p + n]]; p += n
a.append(a[n - 1])
start = 0
res = []
for i in range(n):
if (a[i] < 0 and a[i + 1] < 0) or (a[i] >= 0 and a[i + 1] >= 0):
for j in range(i - start + 1, 0, -1):
res.append(j)
start = i + 1
out.append(' '.join(map(str, res)))
print('\n'.join(out))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: vẫn là $O(N)$ do dùng mảng $a$.
- Thời gian: tuy cũng là 2 vòng lặp lồng nhau nhưng các bạn tính kỹ sẽ thấy cả thảy chỉ chạy $2 \cdot N$ lần chứ không phải $\dfrac{N(N-1)}{2}$ lần. Vì sao? Giả sử mảng 100 phần tử, xét từ phần tử thứ 1 và tới phần tử thứ 30 thì gãy: vòng ngoài đã đi 30 bước, rồi vòng trong lại "lần ngược" in ra 30 giá trị ⇒ quãng 1..30 bị đi 2 lần (xuôi rồi ngược). Rồi từ 31 tới 80 gãy, lại in lùi 50 giá trị; từ 81 tới 100 cũng vậy ⇒ tổng cộng chỉ $2 \cdot N$ lần.
Vậy tổng số lần lặp là $T \cdot (N + 2N) = 3 \cdot T \cdot N$. Với $T = 20$, $N = 10^5$ thì là $6\,000\,000$ (6 triệu) lần – ít hơn ngưỡng 1 giây từ 5 đến 16 lần ⇒ yên tâm không TLE. Tổng quát bỏ hằng số thì là $O(T \cdot N)$.
Đến đây các bạn đã thấy cái hay của giải thuật chưa? Ta tối ưu từ $O(T \cdot N^2)$ xuống còn $O(T \cdot N)$: từ hơn 100 tỷ lần lặp rút xuống chỉ còn 6 triệu 😍.
- 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