Dấu trong đoạn (MULTI)
Đề bài
MULTI – Dấu trong đoạn
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Misaki là một cô gái xinh đẹp, hiền lành, học giỏi. Lớp cô vừa được dạy về dấu của tích 2 số, cô rất hứng thú với bài học và tự hỏi nếu cho một dãy số nguyên thì dấu của tích các số trong đoạn $[L..R]$ bất kì là gì. Do dãy số có thể rất lớn nên Misaki đã nhờ bạn – một cao thủ NTUcoder giải giúp bài toán này.
Dữ liệu nhập:
- Dòng thứ nhất là 2 số nguyên $N, M$ với $N$ là số lượng phần tử và $M$ là số truy vấn ($1 \le N, M \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên, số nguyên $a_i$ là phần tử thứ $i$ trong dãy ($|a_i| \le 10^9$).
- $M$ dòng tiếp theo chứa 2 số $L, R$ là đoạn cần trả lời ($1 \le L \le R \le N$).
Dữ liệu xuất:
Gồm $M$ dòng, mỗi dòng in ra câu trả lời cho mỗi truy vấn, cụ thể: in ra + nếu kết quả là dương, - nếu kết quả là âm, 0 nếu kết quả là 0. (Chú ý: các output phải lược bỏ dấu " ").
4 3
0 1 2 -3
1 2
2 3
3 40
+
-Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy 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ày công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên NTUCoderBài viết đi từ cách vét cạn dễ nghĩ nhất, chỉ ra vì sao nó bị Wrong Answer rồi Time Limit Exceeded, rồi từng bước cải tiến đến cách dùng mảng cộng dồn chạy chỉ khoảng $2 \cdot 10^5$ lần lặp.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn: nhân hết các số trong đoạn
Thì một cách vét cạn rất dễ để nhìn ra cho bài này đó là với mỗi đoạn $L$ $R$ ta sẽ đi xét lần lượt từng giá trị $a[i]$ tương ứng với các vị trí trong đoạn $L$ $R$ đó. Rồi làm theo đúng quy luật của đề bài tính tích tất cả các số trong đoạn $L$ $R$ đó, sau cùng kiểm tra kết quả tích là số dương, số âm hay số 0 và in kết quả ra màn hình, cứ như thế lặp đủ $M$ truy vấn.
Source code nếu làm theo tư tưởng này:
Code cách 1 – nhân trực tiếp (C++ WA test 5, Python TLE test 10)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int a[n + 1];
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
while(m--){
int l, r;
cin >> l >> r;
long long s = 1;
for(int i = l; i <= r; ++i){
s *= a[i];
}
if(s > 0){
cout << "+";
}
else if(s == 0){
cout << "0";
}
else{
cout << "-";
}
cout << endl;
}
return 0;
}n, m = map(int, input().split())
a = [0] + list(map(int, input().split())) # Chỉ số bắt đầu từ 1
for _ in range(m):
l, r = map(int, input().split())
s = 1
for i in range(l, r + 1):
s *= a[i]
if s > 0:
print("+")
elif s == 0:
print("0")
else:
print("-")Kết quả tích các số có thể rất lớn nên ta đã chọn kiểu số nguyên 8 byte (long long) để lưu trữ cho đỡ bị tràn số. Tuy nhiên thì tránh cỡ nào cũng khó lòng tránh được bởi theo giới hạn đề bài thì $|a_i| \le 10^9$, nghĩa là $-10^9 \le a[i] \le 10^9$. Vậy $a[i]$ tối đa có thể là $10^9$. Hãy thử suy nghĩ: chỉ cần 2 thằng $a[i]$ cùng có giá trị $10^9$ đứng chung trong đoạn $L$ $R$ thì tụi nó nhân nhau đã thành $10^{18}$ là gần chạm giới hạn của kiểu long long (khoảng $9.2 \cdot 10^{18}$) rồi; có 3 thằng như vậy thì thành $10^{27}$ là tràn rồi. Chưa kể $1 \le L \le R \le N$ mà $N$ tối đa là $10^5$ – nếu có đến $10^5$ thằng $a[i]$ cùng bằng $10^9$ trong đoạn $L$ $R$ thì ôi thôi cỡ nào chứa cho nổi 😂.
Ví dụ cụ thể: dãy 1000000000 1000000000 1000000000, truy vấn 1 3. Tích thật là $10^{27} > 0$, đáp án phải là +, nhưng code C++ ở trên in ra - vì s đã bị tràn thành số âm. Nên cách làm này coi như phá sản nha các bạn.
Còn code Python thì bản chất Python xử lý được số lớn nên không bị Wrong Answer ở test 5, nhưng nhân những con số khổng lồ như vậy rất chậm, lại còn phải xét hết đoạn $L$ $R$ cho từng truy vấn nên bị Time Limit Exceeded ở test 10.
Cách 2Không cần nhân: đếm số 0 và số âm
Thì để giải quyết được vấn đề bị tràn số như ở trên thì nếu tinh ý một chút các bạn sẽ nhận ra không cần phải vất vả nhân liên tục các giá trị trong đoạn $L$ $R$ lại làm gì rồi sau cùng mới xét dấu của kết quả tích:
- Nếu trong đoạn $L$ $R$ chỉ cần tồn tại ít nhất một số 0 thì chắc chắn tích các số trong đoạn đó sẽ là 0, dù cho các thằng còn lại có là giá trị nào đi nữa.
- Còn nếu không tồn tại số 0 nào thì tích các số đó sẽ là âm hoặc dương. Theo nguyên tắc 2 số âm nhân nhau sẽ thành số dương, cứ 2 số âm nhân nhau thì dấu âm bị triệt tiêu. Trường hợp số lượng số âm là 0 (cũng được xem là số chẵn) thì tất cả đều dương.
0. Không có số 0: số lượng số âm là số chẵn → tích dương (+); số lượng số âm là số lẻ → tích âm (-).Source code nếu làm theo tư tưởng này:
Code cách 2 – đếm số 0 và số âm (TLE)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int a[n + 1];
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
while(m--){
int l, r;
cin >> l >> r;
int cntZero = 0, cntNegativeNumber = 0;
for(int i = l; i <= r; ++i){
if(a[i] == 0){
cntZero = 1;
break;
}
else if(a[i] < 0){
cntNegativeNumber++;
}
}
if(cntZero == 1){
cout << "0";
}
else if(cntNegativeNumber % 2 != 0){
cout << "-";
}
else{
cout << "+";
}
cout << endl;
}
return 0;
}n, m = map(int, input().split())
a = [0] + list(map(int, input().split())) # a[1..n]
for _ in range(m):
l, r = map(int, input().split())
cntZero = 0
cntNegativeNumber = 0
for i in range(l, r + 1):
if a[i] == 0:
cntZero = 1
break
elif a[i] < 0:
cntNegativeNumber += 1
if cntZero == 1:
print("0")
elif cntNegativeNumber % 2 != 0:
print("-")
else:
print("+")Giải thích một số chỗ trong code ở trên:
cntZerolà biến đếm số lượng các số 0,cntNegativeNumberlà biến đếm số lượng các số âm.- Trong quá trình xét từ $L$ đến $R$, chỉ cần gặp số 0 đầu tiên thì ta kết thúc luôn (
break), không cần xét tiếp mấy thằng đằng sau nữa vì giờ đây tích chắc chắn là 0. Lúc này biếncntZerođóng vai trò như cờ hiệu: ban đầu là 0, khi gặp số 0 đầu tiên thì cập nhật thành 1 và kết thúc. Ra bên ngoài ta kiểm tra cờ hiệucntZeronếu là 1 thì in ra0. Còn nếu không thì xét tiếpcntNegativeNumber, nếu là số lẻ thì in ra-. Không phải 2 trường hợp trên thì cuối cùng là trường hợp dương, in ra+. - Vì đoạn $L$ $R$ đang tính từ 1 nên ta cho mảng $a$ có $n + 1$ phần tử, coi như bỏ qua không dùng index 0, chỉ dùng từ index 1 trở đi cho khớp với vị trí tính từ 1 của $L$ $R$.
Đánh giá độ phức tạp của cách làm này:
Trường hợp xấu nhất là khi $N$ có đủ $10^5$ phần tử, có đủ $M = 10^5$ truy vấn, các truy vấn đều có $L = 1$, $R = 10^5$ và không có số 0 nào, như thế thì luôn phải xét đến tận cùng từ $L$ đến $R$. Thử tính số lần lặp cả thảy: $10^5 + 10^5 \cdot 10^5$ $= 10\,000\,100\,000$ (10 tỷ 100 ngàn) lần lặp. Trong khi ngưỡng giới hạn tiêu chuẩn 1 giây là $(3 \text{ đến } 5) \cdot 10^7$ tức là 30 triệu đến 50 triệu, hay cao lắm là $10^8$ – 10 tỷ đã gấp cả 100 – 200 lần rồi nên cách làm này chắc chắn sẽ bị TLE. Ta phải nghĩ ra cách làm khác tốt hơn.
Ý tưởngMảng cộng dồn (prefix sum)
Thì một kinh nghiệm là với các dạng bài mà có các truy vấn $L$ đến $R$ trong mảng thì phần lớn rơi vào bài toán prefix sum (mảng cộng dồn). Để hiểu rõ hơn nó là gì thì cứ trực tiếp qua bài này mình sẽ hướng dẫn cho các bạn nhìn ra.
Như cách làm ở trên thì mấu chốt là với mỗi truy vấn $L$ $R$ ta phải biết trong đoạn đó có số 0 không và có bao nhiêu số âm. Việc xét qua đủ $M$ truy vấn là chắc chắn không bỏ qua được (dữ liệu input cũng phải đọc đủ $M$ truy vấn mà). $M$ tối đa $10^5$ nên bước xử lý mỗi truy vấn chỉ được lặp tối đa khoảng $10^3$ lần trở lại thì mới không bị TLE. Vậy mỗi truy vấn mà xét hết từ $L$ đến $R$ thì chắc chắn là không ổn.
Cách xử lý tốt nhất như sau: đồng thời với dãy $a$ ta tạo 2 mảng cntZero và cntNegative có $N+1$ phần tử:
cntZero[i]lưu tổng số lượng các số 0 tính từ vị trí 1 đến vị trí $i$;cntNegative[i]lưu tổng số lượng các số âm tính từ vị trí 1 đến vị trí $i$.
Khi cần biết trong đoạn $L$ đến $R$ có bao nhiêu số 0 hay bao nhiêu số âm thì các bạn cứ kẻ thử trục số sẽ thấy: tại vị trí $R$ đang lưu số lượng từ 1 đến $R$, tại vị trí $L - 1$ đang lưu số lượng từ 1 đến $L - 1$. Lấy số lượng tại $R$ trừ cho số lượng tại $L - 1$ thì phần còn lại chính là từ $L$ đến $R$:
Vì sao là $L - 1$ mà không phải $L$? Nếu lấy $cnt[R] - cnt[L]$ thì phần còn lại là từ $L+1$ đến $R$, mất luôn phần tử tại vị trí $L$, lại phải xét riêng nó. Trừ cho $cnt[L-1]$ thì khỏi mất công xét riêng vị trí $L$, cũng đồng nghĩa không cần tạo mảng $a$ lưu các phần tử nữa, chỉ cần 1 biến $x$ đọc dữ liệu từ input vào thôi.
Em nhập dãy số và các truy vấn rồi bấm Tiếp để xem từng bước: dựng 2 mảng cộng dồn trước, sau đó mỗi truy vấn chỉ cần 2 phép trừ:
Cách 3Code mảng cộng dồn – O(N + M)
Source code nếu làm theo tư tưởng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
int cntZero[n + 1], cntNegative[n + 1];
cntZero[0] = cntNegative[0] = 0;
int zero = 0, negative = 0;
for(int i = 1; i <= n; ++i){
int x;
cin >> x;
if(x == 0){
zero++;
}
else if(x < 0){
negative++;
}
cntZero[i] = zero;
cntNegative[i] = negative;
}
while(m--){
int l, r;
cin >> l >> r;
if(cntZero[r] - cntZero[l - 1] > 0){
cout << 0 << endl;
continue;
}
if((cntNegative[r] - cntNegative[l - 1]) % 2 != 0){
cout << "-" << endl;
continue;
}
cout << "+" << endl;
}
return 0;
}n, m = map(int, input().split())
arr = list(map(int, input().split()))
cntZero = [0] * (n + 1)
cntNegative = [0] * (n + 1)
zero = 0
negative = 0
for i in range(1, n + 1):
x = arr[i - 1]
if x == 0:
zero += 1
elif x < 0:
negative += 1
cntZero[i] = zero
cntNegative[i] = negative
for _ in range(m):
l, r = map(int, input().split())
if cntZero[r] - cntZero[l - 1] > 0:
print("0")
elif (cntNegative[r] - cntNegative[l - 1]) % 2 != 0:
print("-")
else:
print("+")Giải thích một số chỗ trong code ở trên:
cntZero,cntNegativelà mảng thống kê tổng số lượng tính từ 1 đến từng vị trí index tương ứng. Biếnzerovànegativelà 2 biến đếm để cập nhật vào 2 mảng kia.- Ta tận dụng ngay chính vòng lặp đọc dữ liệu: mỗi giá trị đọc vào thì xét nó là số 0 hay số âm, số lượng đếm được cộng dồn lên liên tục và cập nhật vào vị trí index $i$ tương ứng của từng mảng.
if(cntZero[r] - cntZero[l - 1] > 0): số lượng số 0 trong đoạn $L$ đến $R$ có $> 0$ không? Nếu có thì ngay lập tức kết luận0vàcontinueđể qua truy vấn tiếp theo, không cần xét trường hợp+hay-nữa.if((cntNegative[r] - cntNegative[l - 1]) % 2 != 0): số lượng số âm trong đoạn có là số lẻ không? Nếu là số lẻ thì kết luận-vàcontinue.- Nếu 2 cái
ifđều không thỏa mà chương trình còn chạy được xuống tận cùng thì ta in ra+vì chỉ còn mỗi trường hợp này thôi.
Đánh giá độ phức tạp của cách làm này:
Độ phức tạp không gian thực ra là $O(2 \cdot N)$ nhưng theo quy tắc nhân BigO thì bỏ hằng số, vẫn kết luận là $O(N)$. Thời gian là $O(N)$ cho bước đọc dữ liệu kết hợp tạo 2 mảng cộng dồn, cộng $O(M)$ cho bước trả lời $M$ truy vấn; theo quy tắc cộng BigO lấy thành phần lớn nhất nên là $O(\max(N, M))$. Trường hợp xấu nhất mảng đủ $10^5$ phần tử và đủ $10^5$ truy vấn thì cả thảy chỉ lặp $2 \cdot 10^5$ (200 ngàn) lần thôi – nhỏ hơn ngưỡng 1 giây ít nhất cả 100 lần nên yên tâm không sợ bị TLE nhé.
Đến đây các bạn đã thấy cái hay của giải thuật chưa? Từ việc phải lặp xử lý hết cả 10 tỷ 100 ngàn lần, giờ chịu tốn thêm gấp 2 lần bộ nhớ nhưng bù lại số lần lặp rút xuống chỉ còn 200 ngàn lần. Thật tuyệt vời đúng không nào 😊
cin/endl), Python khoảng 0,45 giây. Cách 2 chỉ với 300 truy vấn $[1, 10^5]$ đã mất 0,04 giây, suy ra $10^5$ truy vấn cần cỡ 12 giây → TLE đúng như phân tích. Ví dụ tràn số ở cách 1 (3 số $10^9$) in sai - đúng như đã nêu.
