Phần thưởng (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Bắc & miền Trung – Bảng B, C2)
Đề bài
Alice tham gia một cuộc thi phát triển mô hình trí tuệ nhân tạo và được Ban tổ chức cho cơ hội nhận thưởng.
Có $n$ ô ($n \ge 2$) đánh số từ $1$ đến $n$, ô thứ $i$ ghi số nguyên $p_i$. Cho trước số nguyên không âm $d$. Alice được chọn hai ô $i$, $j$ sao cho hiệu hai số thứ tự lớn hơn $d$, tức là $|i - j| > d$. Gọi $t = p_i \cdot p_j$:
- nếu $t > 0$ thì Alice nhận món quà trị giá $t$;
- nếu $t \le 0$ thì Alice không nhận được gì (coi như giá trị $0$).
Yêu cầu: tìm giá trị lớn nhất của món quà Alice có thể nhận.
Dữ liệu vào:
- Dòng 1: hai số nguyên $n, d$ ($0 \le d < n$).
- Dòng 2: $n$ số nguyên $p_1, p_2, \dots, p_n$ ($|p_i| \le 10^9$).
Kết quả: một số nguyên là giá trị lớn nhất của món quà (in $0$ nếu Alice không thể nhận quà).
Subtask:
- Subtask 1 (50%): $n \le 3 \cdot 10^3$;
- Subtask 2 (50%): $n \le 3 \cdot 10^5$.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
5 1
1 -4 5 -4 116Giải thích: chọn ô 2 và ô 4 (cách nhau $4 - 2 = 2 > 1$), tích bằng $(-4) \cdot (-4) = 16$. Các cặp có tích dương khác như ô 1 và ô 3 ($1 \cdot 5 = 5$), ô 3 và ô 5 ($5 \cdot 1 = 5$) đều nhỏ hơn. Lưu ý cặp ô 2, ô 3 không được chọn vì chỉ cách nhau 1 (không lớn hơn $d = 1$).
Lời mở đầu
Bài "dễ mà dễ sai": ý tưởng chỉ là tìm tích lớn nhất của hai số, nhưng có ba cái bẫy nhỏ – số âm nhân số âm ra số dương, hai ô phải cách nhau hơn $d$, và tích tới $10^{18}$. Mình đi từ cách duyệt mọi cặp (50 điểm) tới cách $O(n)$ chỉ cần nhớ số lớn nhất và nhỏ nhất của phần đầu dãy.
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 có gì?
Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 24 test (test 1 là ví dụ của đề), chia đều 12 test cho mỗi subtask.
| Nhóm | Test | $n$ lớn nhất | Các giá trị $d$ | Đáp án = 0 | Toàn số âm | Không có số âm | Đáp án = $10^{18}$ |
|---|---|---|---|---|---|---|---|
| Subtask 1 | 1–12 | 3.000 | 0, 1, 5, 8, 10, 100, 1.500, 2.998, 2.999 | test 3, 10 | test 2, 8 | test | test 2, 4 |
| Subtask 2 | 13–24 | 300.000 | 0, 1, 7, 100, 1.000, 99.999, 123.456, 150.000, 299.998 | test 15, 19, 21 | test 17 | test 18–19 | test 20 |
- Có 5 test đáp án bằng 0 (test 3, 10, 15, 19, 21): ví dụ dãy toàn số 0, hoặc $d = n - 2$ nên chỉ có đúng một cặp hợp lệ mà tích lại âm. Lời giải nào khởi tạo
best = LLONG_MINrồi in thẳng ra sẽ sai các test này. - Các test "toàn số âm" bắt buộc phải xét số nhỏ nhất (âm nhất): tích hai số âm mới là số dương lớn.
- Các test đáp án đúng bằng $10^{18}$ ($= 10^9 \cdot 10^9$ hoặc $(-10^9) \cdot (-10^9)$) bắt buộc dùng
long long.
Kết quả chạy thật các cách bên dưới theo từng subtask:
| Subtask | Điều kiện | Test | Cách 1 $O(n^2)$ C++ | Cách 1 Python | Cách 2 $O(n)$ C++ | Cách 2 Python |
|---|---|---|---|---|---|---|
| Subtask 1 (50%) | $n \le 3 \cdot 10^3$ | 1–12 | 12/12 | 12/12 | 12/12 | 12/12 |
| Subtask 2 (50%) | $n \le 3 \cdot 10^5$ | 13–24 | 2/12 | 2/12 | 12/12 | 12/12 |
Ý tưởngCố định ô bên phải, ô bên trái chỉ cần là max hoặc min
Giả sử hai ô được chọn là $i < j$. Điều kiện $j - i > d$ tương đương $i \le j - d - 1$. Vậy khi cố định ô bên phải $j$, ô bên trái $i$ được chọn tuỳ ý trong đoạn đầu $1..j-d-1$.
Trong đoạn đầu đó, số nào nhân với $p_j$ cho tích lớn nhất?
- Nếu $p_j > 0$: tích $p_i \cdot p_j$ càng lớn khi $p_i$ càng lớn → chọn max của đoạn đầu.
- Nếu $p_j < 0$: tích càng lớn khi $p_i$ càng nhỏ (càng âm) → chọn min của đoạn đầu.
- Nếu $p_j = 0$: tích luôn bằng 0.
mx * p[j] và mn * p[j] rồi lấy cái lớn hơn. Khi $j$ tăng thêm 1, đoạn đầu chỉ thêm đúng một ô là ô $j - d - 1$, nên cập nhật mx, mn trong $O(1)$.Em nhập dãy và $d$ rồi bấm Tiếp để xem ô $j$ chạy sang phải, vùng xanh là các ô $i$ hợp lệ (cách $j$ hơn $d$), vùng mờ là $d$ ô quá gần $j$:
Cách 1Duyệt mọi cặp – O(n²) (Subtask 1)
Với mỗi $i$, cho $j$ chạy từ $i + d + 1$ tới $n$ (để $j - i > d$), cập nhật best bằng tích $p_i \cdot p_j$.
bestkhởi tạo bằng 0 chứ không phải số rất nhỏ: món quà không dương thì coi như 0, và nếu không có cặp nào hợp lệ thì đáp án cũng là 0.- Mảng
pkiểulong longđể phép nhânp[i] * p[j](tới $10^{18}$) không bị tràn. Nếu khai báointthì phép nhân haiintbị tràn trước khi gán vàobest.
Kết quả chạy thật: Bản C++ đúng 14/24 test, quá thời gian test 13–14, 16–20, 22–24 (các test đúng chạy lâu nhất 0.026s). Bản Python đúng 14/24 test, quá thời gian test 13–14, 16–20, 22–24 (các test đúng chạy lâu nhất 0.958s). Với $n = 3000$ có khoảng $4{,}5$ triệu cặp – C++ chạy tức thì, Python mất gần 1 giây (vừa kịp). Với $n = 3 \cdot 10^5$ có tới $4{,}5 \cdot 10^{10}$ cặp → quá thời gian; hai test 15 và 21 của subtask 2 vẫn đúng vì $d$ rất lớn nên chỉ có vài cặp hợp lệ. Vẫn là 50 điểm.
Cách 2Max/min của đoạn đầu – O(n) (full)
Cho $j$ chạy từ $d + 2$ tới $n$ (ô bên phải nhỏ nhất có thể là $d + 2$, ứng với $i = 1$). Mỗi lần $j$ tăng, ô $j - d - 1$ vừa "đủ xa" nên được thêm vào đoạn đầu, cập nhật mx, mn; rồi thử hai tích mx * p[j], mn * p[j].
- Không cần xử lý riêng trường hợp $d = n - 1$ (không có cặp nào): vòng lặp không chạy lần nào, in
best = 0. mx,mnđược khởi tạo làLLONG_MIN,LLONG_MAXnhưng trước mỗi phép nhân chúng đã được cập nhật bằng một số thật trong dãy, nên phép nhân không bao giờ dùng giá trị khởi tạo (không tràn số).- Thử với ví dụ ($d = 1$): $j = 3$: đoạn đầu $\{1\}$, tích $1 \cdot 5 = 5$; $j = 4$: đoạn đầu $\{1, -4\}$, $mn \cdot p_4 = (-4)(-4) = 16$; $j = 5$: đoạn đầu $\{1, -4, 5\}$, $mx \cdot p_5 = 5$. Đáp án 16 ✓.
Kết quả chạy thật: Bản C++ đúng 24/24 test, chạy lâu nhất 0.034s. Bản Python đúng 24/24 test, chạy lâu nhất 0.302s. Full điểm.
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) | Điểm theo subtask |
|---|---|---|---|---|
| 1. Duyệt mọi cặp $O(n^2)$ | C++ | 14/24 | 0.026s | 50% |
| Python | 14/24 | 0.958s | 50% | |
| 2. Max/min tiền tố $O(n)$ | C++ | 24/24 | 0.034s | 100% |
| Python | 24/24 | 0.302s | 100% |
Nhận xét
Đăng nhận xét