Xóa Số (XOSO – OLPCĐ 2012)
Đề bài
XOSO – Xóa số (OLPCĐ 2012) · Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Cho dãy $n$ số nguyên không âm $a_1, a_2, \ldots, a_n$. Người ta tiến hành chọn ra 2 chỉ số $i, j$ sao cho $i \lt j$ và xóa khỏi dãy 2 số $a_i, a_j$ để tổng giá trị các số còn lại trong dãy là số chẵn.
Yêu cầu: Cho dãy số $a_1, a_2, \ldots, a_n$. Hãy đếm số lượng cách chọn 2 chỉ số $i, j$ thỏa mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.
Dữ liệu nhập: gồm 2 dòng
- Dòng 1: chứa số nguyên $n$ $(2 \le n \le 10^6)$.
- Dòng 2: chứa $n$ số nguyên không âm $a_1, a_2, \ldots, a_n$ $(0 \le a_i \le 10^9)$.
Dữ liệu xuất:
- Là một số nguyên cho biết số cách chọn 2 chỉ số $i, j$ thỏa mãn.
5
1 2 3 4 565
2 4 6 8 1010Lời mở đầu
Bài này đề ngắn gọn, đọc qua là hiểu liền, nhưng lại là một bài rất hay để luyện cái tư duy đi từ vét cạn rồi tối ưu dần lên: từ $O(N^3)$ rút xuống $O(N^2)$ rồi xuống hẳn $O(N)$ chỉ nhờ một nhận xét chẵn lẻ cực kỳ đơn giản. Anh em cùng mình đi từng bước nha 😇.
Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Ở ví dụ 1, dãy là 1 2 3 4 5, tổng cả dãy là $15$. Ta thử xóa từng cặp vị trí $(i, j)$ và xem tổng còn lại:
| Cặp $(i, j)$ | Xóa $a_i, a_j$ | Tổng còn lại | Chẵn? |
|---|---|---|---|
| (1, 2) | 1, 2 | 15 − 3 = 12 | ✔ |
| (1, 3) | 1, 3 | 15 − 4 = 11 | ✘ |
| (1, 4) | 1, 4 | 15 − 5 = 10 | ✔ |
| (1, 5) | 1, 5 | 15 − 6 = 9 | ✘ |
| (2, 3) | 2, 3 | 15 − 5 = 10 | ✔ |
| (2, 4) | 2, 4 | 15 − 6 = 9 | ✘ |
| (2, 5) | 2, 5 | 15 − 7 = 8 | ✔ |
| (3, 4) | 3, 4 | 15 − 7 = 8 | ✔ |
| (3, 5) | 3, 5 | 15 − 8 = 7 | ✘ |
| (4, 5) | 4, 5 | 15 − 9 = 6 | ✔ |
Có đúng $6$ cặp cho tổng còn lại là số chẵn nên đáp án là $6$. Ở ví dụ 2, dãy 2 4 6 8 10 toàn số chẵn nên xóa cặp nào thì tổng còn lại cũng chẵn, có tất cả $\dfrac{5 \cdot 4}{2} = 10$ cặp nên đáp án là $10$.
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 cặp, cộng lại phần còn lại – O(N³)
Tư tưởng vét cạn rất dễ để nhìn ra: ta đi liệt kê ra tất cả các cặp vị trí $i, j$ thỏa $i \lt j$, rồi tính tổng các phần tử còn lại (bỏ qua 2 vị trí $i, j$). Nếu tổng đó là số chẵn thì cặp $i, j$ được chọn, tăng biến đếm lên. Cứ như thế xét hết tất cả các cặp rồi thì biến đếm chính là kết quả cần tìm – y hệt cái bảng mình làm tay ở trên.
Việc xét hết tất cả các cặp $i \lt j$ chính là kiểu 2 vòng lặp lồng nhau mà ta hay gặp khi cài đặt các thuật toán sắp xếp cơ bản. Nội việc đó đã tốn $O(N^2)$, mà $N$ tối đa $10^6$ thì $(10^6)^2 = 10^{12}$ – vượt quá xa ngưỡng khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$ phép tính trong 1 giây. Nhìn thấy rõ ngay từ đầu cách này chắc chắn bị TLE.
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;
const int MAX = 1e6 + 5;
int a[MAX];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
long long res = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
long long sum = 0;
for(int k = 0; k < n; ++k){
if(k != i && k != j){
sum += a[k];
}
}
if(sum % 2 == 0){
res++;
}
}
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
res = 0
for i in range(n):
for j in range(i + 1, n):
s = 0
for k in range(n):
if k != i and k != j:
s += a[k]
if s % 2 == 0:
res += 1
print(res)
main()- Biến
sumphải làlong long(8 byte): $a_i$ tối đa $10^9$ và $N$ tối đa $10^6$, nên tổng có thể lên tới $10^9 \cdot 10^6 = 10^{15}$ (1 triệu tỷ). Kiểu 4 byte chỉ lưu được tới hàng tỷ là hết mức. - Biến
rescũng phải làlong long: nếu mọi cặp đều thỏa thì có $\dfrac{N(N-1)}{2}$ cặp, với $N = 10^6$ là cỡ $5 \cdot 10^{11}$ (500 tỷ). Kiểu 4 byte không dấu cũng chỉ lưu được tầm hơn 4 tỷ thôi.
Em bấm Tiếp trong khung bên dưới để xem 3 vòng lặp chạy thế nào: ô đỏ là 2 phần tử đang bị "xóa", ô vàng là phần tử $k$ đang được cộng vào tổng.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là số lượng phần tử của mảng.
- Thời gian: $O(N)$ của bước đọc mảng + $O(N^3)$ của bước xử lý (2 vòng xét cặp, bên trong lại thêm 1 vòng duyệt cả mảng để tính tổng: $N^2 \cdot N = N^3$). Theo quy tắc cộng của Big-O lấy thành phần lớn nhất nên tổng quát là $O(N^3)$.
Cách 2Tính tổng cả mảng trước, bỏ vòng lặp thứ 3 – O(N²)
Ta phải tiếp tục nhìn ra những cái không tốt để tối ưu lại. Có thật sự cần vòng lặp thứ 3 duyệt cả mảng chỉ để tính tổng các phần tử còn lại không? Bản chất ta chỉ cần tổng của các phần tử trừ 2 vị trí $i, j$. Vậy ngay từ đầu ta tính tổng $S$ của toàn bộ mảng, rồi khi xét cặp $i, j$ chỉ việc lấy:
Như thế là không cần vòng lặp thứ 3 lồng bên trong nữa, độ phức tạp rút xuống $O(N^2)$. Còn việc tính $S$ thì cũng không cần thêm một vòng lặp riêng: ta tận dụng luôn vòng lặp đọc dữ liệu, đọc số nào cộng số đó vào sum. Đọc xong input là có luôn tổng cả mảng.
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;
const int MAX = 1e6 + 5;
int a[MAX];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
long long sum = 0;
for(int i = 0; i < n; ++i){
cin >> a[i];
sum += a[i];
}
long long res = 0;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if((sum - a[i] - a[j]) % 2 == 0){
res++;
}
}
}
cout << res;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
s = sum(a)
res = 0
for i in range(n):
for j in range(i + 1, n):
if (s - a[i] - a[j]) % 2 == 0:
res += 1
print(res)
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ với $N$ là số lượng phần tử của mảng.
- Thời gian: $O(N)$ của bước đọc mảng + $O(N^2)$ của bước xử lý, tổng quát là $O(N^2)$.
Cách 3Nhận xét chẵn lẻ + đếm tổ hợp – O(N)
Để ý một chút quy luật toán học: ta đâu cần biết tổng còn lại bằng bao nhiêu, ta chỉ cần biết nó chẵn hay lẻ. Mà tính chẵn lẻ của phép trừ thì quá quen thuộc:
Trường hợp 1: tổng $S$ của cả mảng là số lẻ. Để $S - (a_i + a_j)$ ra số chẵn thì $a_i + a_j$ phải là số lẻ (chứ nếu $a_i + a_j$ chẵn thì lẻ − chẵn = lẻ rồi). Mà để tổng 2 số là lẻ thì phải là 1 thằng lẻ, 1 thằng chẵn – 2 thằng cùng lẻ cộng lại ra chẵn, 2 thằng cùng chẵn cộng lại cũng ra chẵn.
Vậy nếu ngay ở bước đọc dữ liệu ta thống kê được có $X$ số chẵn và $Y$ số lẻ, thì số cách chọn 1 thằng chẵn ghép với 1 thằng lẻ chính là $X \cdot Y$. Ví dụ $X = 4$ thằng chẵn, $Y = 3$ thằng lẻ: $X_1$ ghép được với cả $\{Y_1, Y_2, Y_3\}$, $X_2$ cũng ghép được với cả $\{Y_1, Y_2, Y_3\}$, rồi $X_3$, $X_4$ cũng vậy. Tổng cộng $3 + 3 + 3 + 3 = 12 = 4 \cdot 3$. Phép nhân có tính giao hoán nên hiểu ngược lại "mỗi $Y$ ghép với cả 4 thằng $X$" cũng ra như nhau.
Trường hợp 2: tổng $S$ là số chẵn. Muốn trừ đi $a_i + a_j$ mà vẫn còn chẵn thì $a_i + a_j$ cũng phải chẵn (chỉ có chẵn − chẵn = chẵn). Tổng 2 số chẵn thì có 2 tình huống: cả 2 cùng chẵn hoặc cả 2 cùng lẻ.
Câu hỏi giờ là: từ một tập có $K$ phần tử, chọn ra được bao nhiêu cặp? Thử với $K = 4$ vị trí $\{1, 2, 3, 4\}$: các cặp là $\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$ – cả thảy 6 cặp. Quy luật: vị trí thứ $i$ ghép đôi với $K - i$ thằng đứng sau nó, nên số cặp là $(K-1) + (K-2) + \ldots + 1 + 0$ – tổng cộng dồn từ 1 đến $K - 1$, có công thức tính nhanh $\dfrac{K(K-1)}{2}$. Với $K = 4$: $\dfrac{4 \cdot 3}{2} = 6$ ✔. Công thức này rất phổ biến, bạn nào muốn tìm hiểu cách chứng minh thì Google search "chứng minh bằng quy nạp" nhé.
- $S$ lẻ: $\text{đáp án} = X \cdot Y$
- $S$ chẵn: $\text{đáp án} = \dfrac{X(X-1)}{2} + \dfrac{Y(Y-1)}{2}$
Kiểm lại với ví dụ 1: 1 2 3 4 5 có $X = 2$ (số 2, 4), $Y = 3$ (số 1, 3, 5), $S = 15$ lẻ ⇒ đáp án $2 \cdot 3 = 6$ ✔. Ví dụ 2: $X = 5$, $Y = 0$, $S = 30$ chẵn ⇒ $\dfrac{5 \cdot 4}{2} + 0 = 10$ ✔.
Minh hoạ đếm chẵn lẻ
Em nhập dãy số rồi bấm Tiếp để xem từng số được phân loại chẵn (xanh) / lẻ (vàng) thế nào, và cuối cùng các cặp hợp lệ hiện ra ra sao (cặp gạch ngang là cặp không hợp lệ):
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 n;
cin >> n;
long long cntEven = 0, sum = 0;
int temp = n;
while(temp--){
int x;
cin >> x;
sum += x;
if(x % 2 == 0){
cntEven++;
}
}
long long cntOdd = n - cntEven;
if(sum % 2 != 0){
cout << cntEven * cntOdd;
}
else{
cout << (cntEven * (cntEven - 1)) / 2 + (cntOdd * (cntOdd - 1)) / 2;
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
cnt_even = 0
s = 0
for k in range(1, n + 1):
x = int(data[k])
s += x
if x % 2 == 0:
cnt_even += 1
cnt_odd = n - cnt_even
if s % 2 != 0:
print(cnt_even * cnt_odd)
else:
print(cnt_even * (cnt_even - 1) // 2 + cnt_odd * (cnt_odd - 1) // 2)
main()Giải thích một số chỗ trong code ở trên:
- Biến
sumđể kiểulong long, lý do mình đã nói trong phần lưu ý ở cách 1 (tổng có thể tới $10^{15}$). cntEvenlà biến lưu số lượng số chẵn,cntOddlà biến lưu số lượng số lẻ của dãy ban đầu. Mình nói luôn để bạn nào không rành tiếng Anh thì không bị rối.cntEven,cntOddcũng để kiểulong long. Dù bản thân chúng tối đa chỉ $10^6$, nhưng ở phép tính cuốicntEven * (cntEven - 1), kết quả tạm được lưu theo kiểu của các biến thành phần. Nếu đểintthì $10^6 \cdot (10^6 - 1)$ cỡ $10^{12}$ sẽ bị tràn, làm sai kết quả. Cholong longtừ đầu thì mọi vùng nhớ tạm khi tính toán cũng làlong long, khỏi phải ép kiểu từng chỗ cho rối.- Không cần đếm riêng số lẻ: mỗi số chỉ có thể chẵn hoặc lẻ, nên đếm số chẵn xong thì
cntOdd = n - cntEven. Ví dụ mảng 10 phần tử có 4 số chẵn thì chắc chắn có 6 số lẻ. - Không cần mảng nữa: đọc vào biến
x, xét luôn rồi bỏ, về sau không cần dùng lại.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(1)$ vì giờ ta không cần mảng lưu trữ, chỉ đọc từng số vào biến
xrồi xét luôn. - Thời gian: $O(N)$ của bước đọc dữ liệu. Trường hợp xấu nhất $N = 10^6$ thì vòng lặp chỉ chạy $10^6$ lần, ít hơn ngưỡng 1 giây cả 50 – 100 lần nên thoải mái không sợ TLE.
long long. Còn cách 2 với $n = 10^5$ đã mất hơn 3 giây, cách 1 với $n = 2000$ đã mất gần 4 giây ⇒ TLE đúng như phân tích.- 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