Trọng số
Đề bài
Trọng số của dãy số nguyên dương $A_1, A_2, \ldots, A_N$ được tính bằng:
$$\sum_{i=1}^{N-1} \left( A_{i+1} \bmod A_i \right)$$
Yêu cầu: chọn một dãy con liên tiếp của dãy đã cho rồi tăng tất cả các phần tử của dãy con đó lên $K$ đơn vị để trọng số của cả dãy đạt giá trị lớn nhất. Lưu ý: tính cả trường hợp để nguyên dãy ban đầu.
Dữ liệu: vào từ file văn bản WSEQ.INP gồm:
- Dòng đầu là số nguyên dương $T$ là số test $(T \le 10)$;
- Mỗi test gồm: dòng thứ nhất chứa 2 số nguyên dương $N, K$ $(N \le 10^5,\ K \le 10^9)$; dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \ldots, A_N$ $(A_i \le 10^9)$.
Kết quả: ghi ra file văn bản WSEQ.OUT, với mỗi test một số nguyên duy nhất là trọng số lớn nhất tìm được.
Ràng buộc:
- Có 1 điểm có $T = 1$ và $N \le 10^4$;
- 2 điểm còn lại không còn ràng buộc gì thêm.
2
3 1
5 4 3
2 3
7 119
4Giải thích ví dụ: test 1 – dãy $5, 4, 3$ có trọng số ban đầu $4 \bmod 5 + 3 \bmod 4 = 4 + 3 = 7$. Cộng $K = 1$ cho cả dãy được $6, 5, 4$: $5 \bmod 6 + 4 \bmod 5 = 5 + 4 = 9$ – lớn nhất (các đoạn khác cho $7, 8, 3, 4, 4$). Test 2 – dãy $7, 11$: để nguyên được $11 \bmod 7 = 4$; cộng 3 cho $[7]$ được $11 \bmod 10 = 1$, cho $[11]$ được $14 \bmod 7 = 0$, cho cả dãy được $14 \bmod 10 = 4$ → đáp án $4$ (để nguyên cũng là một lựa chọn).
Lời mở đầu
Bài này nhìn qua tưởng phải thử mọi đoạn con $[l, r]$ – có tới $\frac{N(N+1)}{2}$ đoạn. Mình sẽ đi từ cách thử thẳng $O(N^3)$, cải tiến thành $O(N^2)$ bằng cách cập nhật dần, rồi nhìn bài toán theo kiểu quy hoạch động trạng thái: mỗi phần tử hoặc ở trước đoạn, hoặc ở trong đoạn, hoặc ở sau đoạn – chỉ cần đi một lượt $O(N)$ là xong.
WSEQ.INP / WSEQ.OUT; code dùng if(fopen("WSEQ.INP", "r")) nên nộp trên CLUE OJ (đọc bàn phím) vẫn chạy đúng.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 | $T$ | $N$ | $K$ lớn nhất | $A_i$ lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1–20 | 1/2 | 2 … 10 | 20 | 20 | 150 |
| 21–33 | 1 | 10.000 … 10.000 | 70.715.028 | 999.967.792 | 478.947.414.777 |
| 34–90 | 1 | 100.000 … 100.000 | 977.752.318 | 999.997.791 | 54.944.101.361.612 |
| 91–100 | 10 | 100.000 … 100.000 | 81.585.678 | 999.999.379 | 5.393.165.623.556 |
Đề có 3 điểm: 1 điểm cho $T = 1$, $N \le 10^4$ và 2 điểm không ràng buộc thêm. Bộ test 100 test khớp đúng tỉ lệ đó: test 1–33 (33%) là subtask 1 – trong đó 20 test đầu rất nhỏ ($N \le 10$, số $\le 20$; test 1 chính là ví dụ với $T = 2$) và 13 test có $N = 10^4$; test 34–100 (67%) có $N = 10^5$, riêng 10 test cuối có $T = 10$ bộ dữ liệu.
Đáp án lên tới khoảng $5{,}5 \cdot 10^{13}$ (tổng của $10^5$ số dư, mỗi số tới $10^9$) nên bắt buộc dùng long long. Ngoài ra $A_i + K$ có thể tới $2 \cdot 10^9$ – vượt int.
| Phần | Điều kiện | Test | Cách 1 $O(N^3)$ | Cách 2 $O(N^2)$ | Cách 3 QHĐ $O(N)$ |
|---|---|---|---|---|---|
| Subtask 1 – nhỏ | $N \le 10$ | 1–20 | qua | qua | qua |
| Subtask 1 – lớn | $T = 1$, $N = 10^4$ | 21–33 | quá thời gian | qua | qua |
| Subtask 2 | $N = 10^5$, $T \le 10$ | 34–100 | quá thời gian | quá thời gian | qua |
Cách 1Thử mọi đoạn, tính lại trọng số – $O(N^3)$
Cách thẳng thắn nhất: với mỗi đoạn $[l, r]$, tạo dãy mới $b$ (cộng $K$ cho các phần tử trong đoạn), tính trọng số của $b$ mất $O(N)$, lấy max. Khởi tạo đáp án bằng trọng số dãy ban đầu (trường hợp để nguyên).
Kết quả chạy thật: bản C++ đúng 20/100 test – 20 test nhỏ ($N \le 10$), chậm nhất 0,004 giây; bản Python cũng qua 20 test này. Từ test 21 ($N = 10^4$) cần khoảng $\frac{N^3}{2} = 5 \cdot 10^{11}$ phép tính → quá thời gian.
Cách 2Mỗi cặp kề nhau chỉ có 4 khả năng – $O(N^2)$
Trọng số là tổng theo từng cặp kề nhau $(A_i, A_{i+1})$. Khi cộng $K$ cho một đoạn, mỗi cặp chỉ rơi vào 1 trong 4 trường hợp, ta tính sẵn cả 4 giá trị:
| Trường hợp | $A_i$ cộng $K$? | $A_{i+1}$ cộng $K$? | Đóng góp |
|---|---|---|---|
w00[i] | không | không | $A_{i+1} \bmod A_i$ |
w01[i] | không | có (đoạn bắt đầu tại $i+1$) | $(A_{i+1} + K) \bmod A_i$ |
w11[i] | có | có (cả cặp trong đoạn) | $(A_{i+1} + K) \bmod (A_i + K)$ |
w10[i] | có (đoạn kết thúc tại $i$) | không | $A_{i+1} \bmod (A_i + K)$ |
Cố định $l$, cho $r$ tăng dần, trọng số thay đổi chỉ ở 2 cặp nên cập nhật $O(1)$: cặp $(r-1, r)$ chuyển từ w10 sang w11, cặp $(r, r+1)$ chuyển từ w00 sang w10.
Kết quả chạy thật: bản C++ đúng 33/100 test – trọn subtask 1 (1 điểm), chậm nhất 0,08 giây ở $N = 10^4$. 67 test $N = 10^5$ cần $5 \cdot 10^9$ phép → quá thời gian (khoảng 2 giây mỗi test trước khi bị dừng). Bản Python chỉ qua 20 test nhỏ, các test $N = 10^4$ chạy khoảng 1,6 giây.
Ý tưởng QHĐMỗi phần tử ở 1 trong 3 trạng thái
Đi từ trái sang phải, mỗi phần tử $A_i$ thuộc đúng một trong ba "giai đoạn": 0 – đoạn chưa bắt đầu, 1 – đang ở trong đoạn (được cộng $K$), 2 – đoạn đã kết thúc. Các giai đoạn chỉ đi theo thứ tự $0 \to 1 \to 2$ (có thể bỏ qua 1 = để nguyên dãy). Đóng góp của cặp $(A_{i-1}, A_i)$ chỉ phụ thuộc vào trạng thái của 2 phần tử đó, nên:
Em nhập $K$ và dãy rồi bấm Tiếp. Mỗi bước tính cột $i$ của 3 hàng $f_0, f_1, f_2$; mũi tên nhỏ trong công thức cho biết ô lấy từ đâu. Bước cuối lần ngược ra đoạn được cộng $K$ (tô xanh):
Cách 3QHĐ 3 trạng thái – $O(N)$ (full điểm)
- Dùng
NEG = LLONG_MIN / 4làm "âm vô cùng" cho $f_2[1]$, cộng thêm vài số dương cũng không bị tràn. - Mọi phép tính dùng
long long: $A_i + K$ tới $2 \cdot 10^9$, tổng tới $10^{14}$. - Mỗi test chỉ một vòng lặp $N$ bước, 4 phép
%mỗi bước – 10 test $N = 10^5$ chạy chưa tới 0,1 giây.
Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,082 giây (test 94, $T = 10$, $N = 10^5$). Bản Python cũng 100/100, chậm nhất 0,58 giây.
long long cho cả $A_i + K$ lẫn tổng, và đừng quên trường hợp để nguyên dãy (trạng thái 0 đi hết dãy).