Trò chơi biểu thức
Đề bài
Dũng và Vũ là hai bạn thân rất mê toán học. Đôi bạn thường nghĩ ra các bài toán để chơi giải trí với nhau. Hôm nay Vũ nghĩ ra một trò chơi mới và ngay lập tức mời Dũng cùng chơi. Trò chơi Vũ đề xuất như sau: Vũ viết lần lượt $n$ số nguyên $a_1, a_2, \ldots, a_n$ thành một hàng, sau đó giữa hai số $a_i$ và $a_{i+1}$ sẽ điền vào dấu $+$ khi $i$ là số chẵn, ngược lại điền dấu $-$. Như vậy Vũ sẽ có một biểu thức gồm $n$ số hạng $a_1, a_2, \ldots, a_n$ với dấu $-$ và $+$ đan xen nhau:
$a_1 - a_2 + a_3 - a_4$ $+ a_5 - \cdots + (-1)^{n-1} a_n$
Vũ đưa cho Dũng biểu thức này và yêu cầu Dũng thực hiện nhiều nhất một phép đổi chỗ hai số hạng cho nhau sao cho giá trị $S$ của biểu thức nhận được lớn nhất có thể.
Yêu cầu: Hãy giúp Dũng tìm giá trị $S$.
Dữ liệu: vào từ file văn bản EXP.INP trong đó:
- Dòng đầu ghi số $n$;
- Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$.
Kết quả: ghi ra file văn bản EXP.OUT số $S$.
Giới hạn: $n \le 10^6$; $|a_i| \le 10^9$ với mọi $i = 1, 2, \ldots, n$.
Subtask:
- $30\%$ số test có $n \le 10^2$;
- $30\%$ số test có $n \le 10^3$;
- $40\%$ số test còn lại không có điều kiện gì thêm.
6
2 5 4 7 9 112Giải thích ví dụ: ban đầu $S = 2 - 5 + 4 - 7 + 9 - 1 = 2$. Đổi chỗ số $2$ (đang mang dấu $+$) với số $7$ (đang mang dấu $-$) ta được $7 - 5 + 4 - 2 + 9 - 1 = 12$, đây là giá trị lớn nhất.
EXP.INP và ghi ra EXP.OUT. Các code bên dưới đều có dòng if (fopen("EXP.INP", "r")) { freopen(...); freopen(...); }: có file thì đọc/ghi file, không có file thì vẫn đọc bàn phím bình thường – nên nộp được mà các bạn cũng chạy thử trên máy được luôn.Lời mở đầu
Bài mở đầu phần Tham lam rất nhẹ nhàng nhưng có một nhận xét đẹp: thay vì thử mọi cách đổi chỗ, ta chỉ cần biết đổi chỗ hai số hạng thì $S$ thay đổi bao nhiêu. Mình sẽ đi từ cách "thử hết" ăn subtask 1, tối ưu dần lên cách $O(n)$ chỉ với một vòng lặp, kèm kết quả chạy thật trên bộ test của CLUE.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
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:
Bộ testBộ test chính thức có gì?
| Test | n | Giá trị $a_i$ | Đáp án $S$ |
|---|---|---|---|
| 1 – 10 | 1 … 10 | -20 … 20 | 9 … 69 |
| 11 – 30 | 11 … 83 | -32.738 … 32.695 | -145.709 … 351.865 |
| 31 – 60 | 141 … 967 | -32.765 … 32.754 | -722.812 … 1.495.754 |
| 61 – 80 | 2.823 … 39.765 | -32.767 … 32.767 | -4.318.812 … 3.633.799 |
| 81 – 90 | 101.520 … 120.274 | -32.767 … 32.767 | -3.818.144 … 7.518.676 |
| 91 – 100 | 1.000.000 | -32.767 … 32.767 | -10.169.672 … 19.396.387 |
- Bộ test có 100 test, đi đúng theo 3 subtask của đề: test 1–30 có $n \le 100$, test 31–60 có $n \le 1000$, test 61–100 lớn dần tới $n = 10^6$ (10 test cuối đều đúng $n = 10^6$).
- Có 2 test với $n = 1$ (test 1, 9): biểu thức chỉ có đúng một số hạng, không có số hạng dấu $-$ nào – code phải xử lý được trường hợp này.
- Có 30 test đáp án âm – đừng khởi tạo đáp án bằng 0! Có 2 test mà không đổi chỗ mới là tốt nhất (mọi số hạng dấu $-$ đều nhỏ hơn hoặc bằng mọi số hạng dấu $+$).
- Giá trị thật trong test chỉ nằm trong khoảng $\pm 32767$, nhưng đề cho $|a_i| \le 10^9$, $n \le 10^6$ nên tổng có thể tới $10^{15}$ → các bạn vẫn phải dùng
long long.
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 $O(n^3)$ | Cách 2 $O(n^2)$ | Cách 3 $O(n)$ |
|---|---|---|---|---|---|
| 1 (30%) | $n \le 100$ | 1 – 30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $n \le 1000$ | 31 – 60 | 30/30 | 30/30 | 30/30 |
| 3 (40%) | $n \le 10^6$ | 61 – 100 | 0/40 | 20/40 | 40/40 |
Ý tưởngĐổi chỗ thì S thay đổi bao nhiêu?
Gọi số hạng ở vị trí lẻ ($a_1, a_3, a_5, \ldots$) là số hạng dấu $+$, ở vị trí chẵn ($a_2, a_4, \ldots$) là số hạng dấu $-$. Dấu gắn với vị trí chứ không gắn với con số. Xét đổi chỗ hai số $x$ và $y$:
- Hai số cùng dấu (cùng ở vị trí lẻ hoặc cùng ở vị trí chẵn): đổi xong vẫn là $+x + y$ hoặc $-x - y$ → $S$ không đổi. Vô ích!
- $x$ đang mang dấu $+$, $y$ đang mang dấu $-$: trước khi đổi đóng góp $+x - y$, sau khi đổi thành $+y - x$. Vậy $S$ tăng thêm $(y - x) - (x - y) = 2(y - x)$.
Đáp án: $S_{\text{đầu}} + 2 \cdot \max(0,\ \max_{\text{chẵn}} - \min_{\text{lẻ}})$.
Với ví dụ của đề: số hạng dấu $+$ là $\{2, 4, 9\}$, nhỏ nhất là $2$; số hạng dấu $-$ là $\{5, 7, 1\}$, lớn nhất là $7$. $S$ ban đầu bằng $2$, tăng thêm $2 \cdot (7 - 2) = 10$ → $S = 12$.
Em nhập dãy số rồi bấm Tiếp để xem máy vừa tính $S$ vừa tìm "số $+$ nhỏ nhất" và "số $-$ lớn nhất" chỉ trong một lượt duyệt:
Cách 1Thử mọi cặp, tính lại biểu thức – O(n³)
Cách nghĩ đơn giản nhất, chưa cần nhận xét gì: thử đổi chỗ mọi cặp $(i, j)$, mỗi lần đổi xong thì tính lại cả biểu thức bằng hàm tinh(), rồi đổi trả lại như cũ. Đừng quên trường hợp không đổi: đáp án khởi tạo bằng giá trị biểu thức ban đầu.
- Hàm
tinh()duyệt $i$ từ $1$ tới $n$: $i$ lẻ thì cộng, $i$ chẵn thì trừ – đúng như biểu thức của đề. ans = tinh()trước vòng lặp chính là phương án "không đổi chỗ" (nhờ vậy test $n = 1$ vẫn đúng, và test mà đổi chỗ chỉ thiệt cũng đúng).- Có $\frac{n(n-1)}{2}$ cặp, mỗi cặp tốn $O(n)$ để tính lại → tổng $O(n^3)$. Với $n = 100$ chỉ khoảng $5 \cdot 10^5$ phép tính, nhưng $n = 1000$ đã là $5 \cdot 10^8$.
Kết quả chạy thật: bản C++ đúng 60/100 test (quá 1 giây ở các test 61–100), test đúng chạy lâu nhất 0.343s; bản Python đúng 49/100 test (quá thời gian ở các test 33, 35, 39, 43–44, 46, 52–55, 58, 61–100), lâu nhất 0.98s.
Bản C++ "lời" hơn dự kiến: qua được cả subtask 2 dù với $n = 1000$ phải làm cỡ $5 \cdot 10^8$ phép cộng trừ – vì vòng lặp trong tinh() rất đơn giản, trình biên dịch tối ưu được (cộng nhiều số một lúc). Nhưng từ test 61 ($n$ vài nghìn trở lên) thì $n^3$ tăng quá nhanh, không cứu được nữa. Bản Python tính tổng bằng sum(a[0::2]) (chạy ở tốc độ của C) nên qua được subtask 1 và khoảng một nửa subtask 2 – các test $n$ gần 1000 thì quá thời gian.
Cách 2Chỉ thử cặp (dấu +, dấu −) – O(n²)
Dùng nhận xét ở phần ý tưởng: đổi chỗ số hạng dấu $+$ ở vị trí lẻ $i$ với số hạng dấu $-$ ở vị trí chẵn $j$ thì $S$ tăng đúng $2(a_j - a_i)$ – không cần tính lại cả biểu thức. Các cặp cùng dấu không làm $S$ thay đổi nên bỏ qua.
- Tính $S$ ban đầu ngay lúc đọc dữ liệu.
best = 0nghĩa là "không đổi chỗ"; mỗi cặp $(i, j)$ chỉ tốn $O(1)$:best = max(best, 2 * (a[j] - a[i])).- Số cặp khoảng $\frac{n}{2} \cdot \frac{n}{2} = \frac{n^2}{4}$. Với $n = 1000$ là $2.5 \cdot 10^5$ – quá nhẹ; nhưng với $n = 10^6$ là $2.5 \cdot 10^{11}$ – không thể.
Kết quả chạy thật: bản C++ đúng 80/100 test (quá 1 giây ở các test 81–100), test đúng chạy lâu nhất 0.360s; bản Python đúng 63/100 test (quá thời gian ở các test 61–64, 66–67, 69, 71–100), lâu nhất 0.84s.
Bản C++ qua thêm được test 61–80 ($n$ tới khoảng $4 \cdot 10^4$, tức cỡ $4 \cdot 10^8$ cặp – phép tính trong vòng lặp quá đơn giản nên vẫn kịp), nhưng với $n \approx 10^5$ trở lên thì chịu. Tức là Cách 2 ăn trọn subtask 1, 2 và một phần subtask 3.
Cách 3Tham lam: số + nhỏ nhất, số − lớn nhất – O(n)
Trong Cách 2, ta đang đi tìm $\max(a_j - a_i)$ với $j$ chẵn, $i$ lẻ. Hai chỉ số này độc lập với nhau, nên $\max(a_j - a_i)$ $= \max_{j \text{ chẵn}} a_j - \min_{i \text{ lẻ}} a_i$. Chỉ cần một vòng lặp: vừa đọc vừa cộng/trừ vào $S$, vừa cập nhật mn (số hạng dấu $+$ nhỏ nhất) và mx (số hạng dấu $-$ lớn nhất). Không cần lưu mảng luôn!
mnkhởi tạo bằngLLONG_MAX,mxbằngLLONG_MINđể giá trị đầu tiên đọc được chắc chắn thay thế.- Điều kiện
n >= 2: khi $n = 1$ không có số hạng dấu $-$ nào,mxvẫn làLLONG_MIN, không được đổi. (Thật ramx > mnđã sai sẵn trong trường hợp này, nhưng viết rõ ra cho dễ đọc và đểmx - mnkhông bao giờ bị tràn số.) - Chỉ đổi khi
mx > mn– tức là đổi chỗ thật sự có lợi; còn lại giữ nguyên $S$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.102s; bản Python đúng 100/100 test, lâu nhất 0.41s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Thử mọi cặp, tính lại | C++ | 60/100 | 0.343s | Quá thời gian ở test 61–100 |
| Python | 49/100 | 0.979s | Quá thời gian ở test 33, 35, 39, 43–44, 46, 52–55, 58, 61–100 | |
| 2. Thử mọi cặp (+, −) | C++ | 80/100 | 0.360s | Quá thời gian ở test 81–100 |
| Python | 63/100 | 0.840s | Quá thời gian ở test 61–64, 66–67, 69, 71–100 | |
| 3. Tham lam min/max | C++ | 100/100 | 0.102s | Full điểm |
| Python | 100/100 | 0.407s | Full điểm |
Nhận xét
Đăng nhận xét