Job (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1, C2)
Đề bài
Alice được giao $n$ công việc, đánh số từ $1$ đến $n$. Các công việc được làm lần lượt: mỗi lúc chỉ làm một việc và đã làm thì làm liền tới xong. Công việc thứ $i$ có:
- thời gian thực hiện $t_i$;
- mức độ quan trọng (trọng số) $w_i$: nếu công việc $i$ kết thúc tại thời điểm $d$ thì chịu chi phí $d \times w_i$;
- công việc $p_i$ phải làm xong trước khi bắt đầu công việc $i$ ($p_i < i$). Riêng $p_1 = 0$: chỉ công việc $1$ được bắt đầu ngay ở thời điểm $0$.
Alice muốn sắp thứ tự làm sao cho tổng chi phí của cả $n$ công việc nhỏ nhất. Ngoài ra Alice được phép đổi trọng số của một công việc nào đó thành $1$.
Yêu cầu: chọn công việc để đổi trọng số (và thứ tự làm) sao cho tổng chi phí nhỏ nhất.
Dữ liệu vào:
- Dòng 1: số nguyên dương $n$.
- Dòng 2: $n$ số nguyên $p_1, p_2, \dots, p_n$.
- Dòng 3: $n$ số nguyên không âm $w_1, \dots, w_n$ ($w_i \le 10^3$).
- Dòng 4: $n$ số nguyên không âm $t_1, \dots, t_n$ ($t_i \le 10^3$).
Kết quả: một số nguyên là tổng chi phí nhỏ nhất.
Subtask:
- Subtask 1 (30%): $n \le 8$;
- Subtask 2 (20%): $n \le 18$;
- Subtask 3 (30%): $n \le 180$;
- Subtask 4 (20%): $n \le 1800$.
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.
3
0 1 1
2 3 3
1 2 317Giải thích: đổi trọng số công việc $3$ thành $1$ rồi làm theo thứ tự $1, 2, 3$: các việc kết thúc ở thời điểm $1, 3, 6$, tổng chi phí $1 \cdot 2 + 3 \cdot 3 + 6 \cdot 1 = 17$.
- Quan hệ "$p_i$ trước $i$" với $p_i < i$ tạo thành một cây gốc 1: công việc chỉ được làm khi cha của nó đã xong.
- Đề ghi "có thể đổi". Đổi một trọng số $w_i \ge 1$ thành $1$ không bao giờ làm chi phí tăng, nên chỉ khi mọi $w_i = 0$ thì hai cách hiểu (bắt buộc đổi / không bắt buộc) mới khác nhau. Bộ test luôn có ít nhất một $w_i \ge 1$; lời giải bên dưới thử đổi đúng một công việc.
- $t_i$ có thể bằng $0$; đáp án tới cỡ $1{,}6 \cdot 10^{12}$ nên phải dùng
long long.
Lời mở đầu
Đây là bài khó nhất của đề C1/C2 vòng khu vực. Phần "đổi một trọng số" chỉ là vỏ: cứ thử đổi từng công việc rồi giải bài toán gốc. Cái khó nằm ở bài toán gốc – lập lịch một máy, ràng buộc dạng cây, cực tiểu $\sum w_i C_i$. Mình đi từ thử mọi hoán vị (Subtask 1), QHĐ bitmask (Subtask 2), tới thuật toán tham lam gộp nhóm theo tỉ số $W/T$ (Subtask 3, 4), cuối cùng là một mẹo cắt tỉa giúp chạy nhanh gấp nhiều lần.
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 đề).
| Nhóm | Test | $n$ lớn nhất | Cây là đường thẳng | Cây hình sao | Có $w_i = 0$ | Có $t_i = 0$ | Đáp án lớn nhất |
|---|---|---|---|---|---|---|---|
| Subtask 1 | 1–6 | 8 | test 4 | test 1, 5 | test 5–6 | test 5–6 | 15.373.942 |
| Subtask 2 | 7–10 | 18 | – | test 8 | test 10 | test 8, 10 | 26.566.506 |
| Subtask 3 | 11–16 | 180 | test 12 | test 13 | test 14 | test 16 | 16.110.180.000 |
| Subtask 4 | 17–24 | 1.800 | test 18 | test 19, 24 | test 17, 20–21 | test 17, 20–21, 23–24 | 1.619.101.800.000 |
- Cây có đủ hình dạng: ngẫu nhiên, đường thẳng (thứ tự bị ép), hình sao (tự do nhất), "chổi", cây sâu...
- Nhiều test có $t_i = 0$ hoặc $w_i = 0$ để bắt lỗi chia cho 0 khi so sánh tỉ số $W/T$. Hai test cuối (23, 24) được thiết kế để cách cắt tỉa ở Cách 5 phải thử nhiều lần nhất.
- Đáp án lớn nhất là $1\,619\,101\,800\,000$.
Kết quả chạy thật các cách bên dưới theo từng subtask (C = cách, Py = Python):
| Subtask | Điều kiện | Test | C1 C++ | C1 Py | C2 C++ | C3 C++ | C4 C++ | C4 Py | C5 C++ | C5 Py |
|---|---|---|---|---|---|---|---|---|---|---|
| Subtask 1 (30%) | $n \le 8$ | 1–6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 |
| Subtask 2 (20%) | $n \le 18$ | 7–10 | 0/4 | 0/4 | 4/4 | 4/4 | 4/4 | 4/4 | 4/4 | 4/4 |
| Subtask 3 (30%) | $n \le 180$ | 11–16 | 0/6 | 0/6 | 0/6 | 6/6 | 6/6 | 6/6 | 6/6 | 6/6 |
| Subtask 4 (20%) | $n \le 1800$ | 17–24 | 0/8 | 0/8 | 0/8 | 0/8 | 8/8 | 0/8 | 8/8 | 5/8 |
Ý tưởngĐổi chỗ hai khối kề nhau và gộp nhóm
Bước 1 – vỏ ngoài: thử đổi trọng số của từng công việc $c$ thành 1, mỗi lần giải bài toán gốc, lấy kết quả nhỏ nhất. Vậy chỉ cần giải tốt bài toán gốc.
Bước 2 – đổi chỗ hai khối kề nhau. Giả sử trong lịch có khối $A$ (tổng trọng số $W_A$, tổng thời gian $T_A$) đứng ngay trước khối $B$. Đổi chỗ thành $B$ rồi $A$: các việc trong $B$ xong sớm hơn $T_A$, các việc trong $A$ xong muộn hơn $T_B$, chi phí thay đổi $W_A T_B - W_B T_A$. Vậy nếu được tự do, nên đặt khối có tỉ số $W/T$ lớn hơn lên trước (quy tắc Smith). Khối có $T = 0$ coi như tỉ số vô cùng.
Bước 3 – gộp nhóm (thuật toán Horn). Xét công việc $g \ne 1$ có tỉ số $w_g / t_g$ lớn nhất, cha của nó là $q$. Trong một lịch tối ưu, nếu giữa $q$ và $g$ còn việc $x$ đứng ngay trước $g$ thì $x$ không phải tổ tiên của $g$ (tổ tiên đều đứng trước $q$) và $w_x/t_x \le w_g/t_g$, nên đổi chỗ $x$ với $g$ không vi phạm ràng buộc và không làm tăng chi phí. Lặp lại tới khi $g$ đứng ngay sau $q$.
Em nhập cây và các trọng số rồi bấm Tiếp để xem các nhóm được gộp dần (mỗi màu là một nhóm, nhãn dưới đỉnh là $w/t$). Ô "Đổi việc" để chọn công việc bị đổi trọng số thành 1 (0 = không đổi):
Cách 1Thử mọi hoán vị (Subtask 1)
Với mỗi công việc $c$ được đổi trọng số, duyệt mọi hoán vị của $1..n$ bằng next_permutation, bỏ các hoán vị làm một việc trước cha của nó, tính chi phí các hoán vị hợp lệ.
- Mảng
doneđánh dấu các việc đã xong; gặp việc $j$ mà chap[j]chưa xong thì hoán vị không hợp lệ. nowlà thời điểm hiện tại, tăng dần theo từng việc – chính là thời điểm kết thúc $C_j$.
Kết quả chạy thật: Bản C++ đúng 6/24 test, sai test 13, 16–17, 19, 22–24, quá thời gian test 7–12, 14–15, 18, 20–21 (các test đúng chạy lâu nhất 0.005s). Bản Python đúng 6/24 test, quá thời gian test 7–24 (các test đúng chạy lâu nhất 0.240s). Với $n = 8$ có $8 \cdot 8! \approx 3{,}2 \cdot 10^5$ hoán vị – rất nhanh; nhưng $n = 18$ thì $18!$ là không tưởng (các test lớn hơn còn bị tràn mảng khai báo cho $n$ nhỏ nên ghi là sai). 30 điểm.
Cách 2QHĐ bitmask (Subtask 2)
Thứ tự trong một tập việc đã làm xong không ảnh hưởng tới các việc sau – chỉ cần biết tập đã làm và tổng thời gian của tập đó. Gọi dp[mask] là chi phí nhỏ nhất khi đã làm xong đúng các việc trong mask. Thêm việc $j$ (chưa làm, cha đã làm): nó kết thúc ở thời điểm sumT[mask] + t[j].
sumTtính một lần bằng bit thấp nhất: bỏ bit $j$ ra khỏimasklà được một mask nhỏ hơn đã tính.- Chỉ thêm $j$ khi
p[j]đã nằm trongmask(công việc 0 cóp = -1nên luôn được làm trước tiên).
Kết quả chạy thật: Bản C++ đúng 10/24 test, sai test 11–24 (các test đúng chạy lâu nhất 0.168s). Với $n = 18$: $18 \cdot 2^{18} \cdot 18 \approx 8{,}5 \cdot 10^7$ phép tính, vẫn kịp. Với $n \ge 180$ thì không thể (mảng $2^{180}$). Qua Subtask 1, 2: 50 điểm.
Cách 3Gộp nhóm, quét tìm max – O(n³) (Subtask 3)
Cài đặt trực tiếp thuật toán gộp nhóm ở phần ý tưởng. Mỗi nhóm được đại diện bởi việc đầu nhóm (việc làm đầu tiên của nhóm); cha của nhóm $g$ là nhóm chứa p[g] – tìm bằng DSU. Mỗi lần gộp, quét mọi nhóm còn sống để tìm tỉ số lớn nhất.
- Hàm
betterso sánh hai phân số bằng nhân chéo $W_g T_h > W_h T_g$ – không chia, không sai số, không lo $T = 0$ (xử lý riêng là vô cùng). Tích lớn nhất cỡ $1{,}8 \cdot 10^6 \cdot 1{,}8 \cdot 10^6$ $\approx 3{,}2 \cdot 10^{12}$, vừalong long. findSetcó nén đường đi (gándsu[x] = dsu[dsu[x]]) nên gần như $O(1)$.- Mỗi lần giải tốn $O(n^2)$, thử $n$ công việc → $O(n^3)$.
Kết quả chạy thật: Bản C++ đúng 16/24 test, quá thời gian test 17–24 (các test đúng chạy lâu nhất 0.015s). $n = 180$ chỉ tốn khoảng $6 \cdot 10^6$ phép tính, nhưng $n = 1800$ là $5{,}8 \cdot 10^9$ → quá thời gian. 80 điểm.
Cách 4Gộp nhóm + hàng đợi ưu tiên – O(n² log n) (full)
Thay việc quét bằng priority_queue sắp theo tỉ số $W/T$. Khi nhóm $q$ nhận thêm nhóm con, tỉ số của $q$ đổi – ta không xoá bản ghi cũ mà tăng "phiên bản" ver[q] rồi đẩy bản ghi mới; lúc lấy ra, bản ghi nào có phiên bản cũ (hoặc nhóm đã bị gộp) thì bỏ qua (xoá lười).
operator<củaItem: $a < b$ khi tỉ số của $a$ nhỏ hơn –priority_queueluôn đưa phần tử "lớn nhất" lên đầu. Mọi bản ghi $T = 0$ được coi là bằng nhau và lớn hơn mọi bản ghi khác, nên đây vẫn là một thứ tự hợp lệ.- Nhóm gốc (chứa việc 1) không bao giờ được đẩy vào hàng đợi: nó không có cha để gộp vào.
- Mỗi lần giải có tối đa $2n$ lần đẩy vào hàng đợi → $O(n \log n)$; thử $n$ công việc → $O(n^2 \log n)$.
Kết quả chạy thật: Bản C++ đúng 24/24 test, chạy lâu nhất 0.494s. Full điểm, dù hơi sát (khoảng nửa giới hạn thời gian). Bản Python đúng 16/24 test, quá thời gian test 17–24 (các test đúng chạy lâu nhất 0.064s).
Cách 5Thêm cắt tỉa bằng cận dưới (nhanh gấp nhiều lần)
Gọi OPT là chi phí nhỏ nhất khi không đổi gì. Với một lịch bất kỳ, đổi $w_c$ thành 1 làm chi phí giảm đúng $(w_c - 1) \cdot C_c$, mà thời điểm kết thúc $C_c$ không thể vượt quá $Mx_c = $ (tổng mọi $t$) $-$ (tổng $t$ của các con cháu của $c$) – vì con cháu của $c$ phải làm sau $c$. Do đó:
kết quả khi đổi $c$ $\;\ge\; LB_c = OPT - (w_c - 1) \cdot Mx_c$ (với $w_c = 0$ thì $LB_c = OPT$).
Sắp các công việc theo $LB_c$ tăng dần, lần lượt giải; ngay khi $LB_c \ge$ kết quả tốt nhất đã có thì dừng – các việc sau chắc chắn không tốt hơn.
- Tổng $t$ của cây con tính bằng một vòng duyệt ngược $i = n..2$ (vì $p_i < i$ nên con luôn có số lớn hơn cha).
sub[1]là tổng mọi $t$. - Cắt tỉa không đổi kết quả (chỉ bỏ những lần thử chắc chắn không tốt hơn), nên đúng như Cách 4.
Kết quả chạy thật: Bản C++ đúng 24/24 test, chạy lâu nhất 0.213s – nhanh hơn Cách 4 nhiều lần. Bản Python đúng 21/24 test, quá thời gian test 19, 23–24 (các test đúng chạy lâu nhất 0.891s): cắt tỉa giúp bản Python qua thêm phần lớn Subtask 4, nhưng các test được thiết kế để phải thử nhiều lần vẫn quá thời gian.
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. Thử mọi hoán vị | C++ | 6/24 | 0.005s | 30% |
| Python | 6/24 | 0.240s | 30% | |
| 2. QHĐ bitmask | C++ | 10/24 | 0.168s | 50% |
| 3. Gộp nhóm (Horn) quét tuyến tính $O(n^3)$ | C++ | 16/24 | 0.015s | 80% |
| 4. Gộp nhóm + hàng đợi ưu tiên $O(n^2 \log n)$ | C++ | 24/24 | 0.494s | 100% |
| Python | 16/24 | 0.064s | 80% | |
| 5. Cách 4 + cắt tỉa bằng cận dưới | C++ | 24/24 | 0.213s | 100% |
| Python | 21/24 | 0.891s | 80% |
Nhận xét
Đăng nhận xét