Đóng gói (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng C1)
Đề bài
Alice cần đóng gói $n$ món quà, món thứ $i$ có khối lượng $w_i$. Alice có $b$ thùng. Một thùng nếu được dùng thì tổng khối lượng các món trong thùng phải không vượt quá $m$ và không nhỏ hơn $\left\lceil \dfrac{9m}{10} \right\rceil$ (tức là thùng phải "gần đầy"). Thùng không chứa món nào thì không bị ràng buộc gì.
Yêu cầu: giúp Alice đóng gói được càng nhiều món quà càng tốt vào $b$ thùng.
Dữ liệu vào:
- Dòng 1: ba số nguyên dương $n, m, b$ ($b \le n \le 1000$; $m \le 10^9$).
- Dòng 2: $n$ số nguyên dương $w_1, w_2, \dots, w_n$ ($w_i \le 10^9$).
Kết quả: một dòng gồm $n$ số nguyên $r_1, r_2, \dots, r_n$ ($0 \le r_i \le b$): $r_i = 0$ nghĩa là món $i$ không được đóng gói, $r_i > 0$ nghĩa là món $i$ được cho vào thùng số $r_i$.
Chấm điểm: với mỗi test, gọi $s$ là số món trong phương án của thí sinh (phương án phải hợp lệ) và $d$ là số món trong phương án của Ban giám khảo. Nếu $d - s \le 10$ thì thí sinh được $0{,}9^{\max(0,\ d - s)}$ số điểm của test, ngược lại được 0 điểm.
Subtask: Subtask 1 (50%): $m \le 1000$; Subtask 2 (50%): không có ràng buộc gì thêm.
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.
8 10 3
1 2 3 4 5 6 8 31 2 1 3 1 3 2 0Giải thích: mỗi thùng được dùng phải có tổng trong đoạn $[9, 10]$. Thùng 1 chứa các món 1, 3, 5 (tổng $1 + 3 + 5 = 9$), thùng 2 chứa các món 2, 7 ($2 + 8 = 10$), thùng 3 chứa các món 4, 6 ($4 + 6 = 10$). Có 7 món được đóng gói. Bài có thể có nhiều phương án đúng (output của em khác ví dụ vẫn được chấm đúng nếu hợp lệ và đủ nhiều món).
Lời mở đầu
Đây là một bài tối ưu hóa thuộc họ "xếp thùng" (bin packing) – một bài toán NP-khó: không ai biết thuật toán nào vừa luôn cho đáp án tốt nhất vừa chạy nhanh với $n = 1000$. Vì vậy đề chấm theo kiểu điểm từng phần: càng gần đáp án của Ban giám khảo càng nhiều điểm. Với dạng bài này, mục tiêu không phải là "đúng" mà là "đủ tốt" – và kỹ năng cần rèn là: tìm cận trên để biết mình còn cách tối ưu bao xa, xây một phương án tham lam làm "lưới an toàn", rồi cải thiện bằng tìm kiếm cục bộ.
Mình cũng sẽ kể thật về kết quả trên bộ chấm chính thức – vì bài này có một chuyện khá lạ.
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 và cách chấm trên CLUE
Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 25 test (test 1 là ví dụ), test 1–13 có $m \le 1000$, test 14–25 có $m$ tới $10^9$. Vì không có đáp án của Ban giám khảo, "đáp án tham chiếu" $d$ của mỗi test là kết quả của lời giải mạnh nhất của mình (bản đã nộp chính thức, mô tả ở cuối bài). Trình chấm (checker) trên CLUE làm đúng công thức của đề: kiểm tra phương án hợp lệ, rồi cho $0{,}9^{\max(0, d - s)}$ điểm nếu $d - s \le 10$.
Cột UB là một cận trên dễ tính (giải thích ở phần ý tưởng): không phương án nào gói được nhiều hơn UB món. Ô xanh ở cột "đáp án tham chiếu" là test mà đáp án tham chiếu đạt đúng UB – tức là chắc chắn tối ưu – có 15/25 test như vậy.
| Test | $n$ | $m$ | $b$ | Kiểu khối lượng | Cận trên UB | Đáp án tham chiếu | Cách 1 số món (điểm) | Cách 2 số món (điểm) |
|---|---|---|---|---|---|---|---|---|
| 1 | 8 | 10 | 3 | ví dụ | 7 | 7 | 6 (0,90) | 7 (1,00) |
| 2 | 1000 | 1.000 | 50 | rất nhỏ (≤ m/20) | 1000 | 1000 | 993 (0,48) | 1000 (1,00) |
| 3 | 1000 | 1.000 | 1000 | rất nhỏ | 1000 | 1000 | 983 (0,00) | 1000 (1,00) |
| 4 | 1000 | 1.000 | 300 | nhỏ (≤ m/5) | 1000 | 1000 | 997 (0,73) | 1000 (1,00) |
| 5 | 1000 | 997 | 400 | m/5 – m/3 | 1000 | 1000 | 622 (0,00) | 1000 (1,00) |
| 6 | 1000 | 1.000 | 500 | m/4 – m/2 | 1000 | 1000 | 618 (0,00) | 999 (0,90) |
| 7 | 1000 | 1.000 | 1000 | lớn 0,8m – 1,1m | 668 | 314 | 314 (1,00) | 314 (1,00) |
| 8 | 1000 | 10 | 1000 | bất kì ≤ m | 1000 | 1000 | 776 (0,00) | 1000 (1,00) |
| 9 | 1000 | 1 | 600 | có món > m | 317 | 317 | 317 (1,00) | 317 (1,00) |
| 10 | 1000 | 1.000 | 200 | trộn: nhiều món tí hon + vài món lớn | 1000 | 968 | 914 (0,00) | 976 (1,00) |
| 11 | 1000 | 999 | 100 | lệch: đa số nhỏ | 994 | 994 | 933 (0,00) | 994 (1,00) |
| 12 | 1000 | 1.000 | 333 | sát m/3 (khó ghép 3 món) | 1000 | 999 | 999 (1,00) | 999 (1,00) |
| 13 | 7 | 100 | 3 | bất kì, n = 7 | 7 | 6 | 6 (1,00) | 6 (1,00) |
| 14 | 1000 | 1.000.000.000 | 50 | rất nhỏ | 1000 | 1000 | 990 (0,35) | 1000 (1,00) |
| 15 | 1000 | 1.000.000.000 | 1000 | nhỏ | 1000 | 1000 | 997 (0,73) | 1000 (1,00) |
| 16 | 1000 | 999.999.999 | 300 | m/5 – m/3 | 1000 | 1000 | 633 (0,00) | 1000 (1,00) |
| 17 | 1000 | 1.000.000.000 | 500 | m/4 – m/2 | 1000 | 991 | 570 (0,00) | 999 (1,00) |
| 18 | 1000 | 1.000.000.000 | 1000 | lớn 0,8m – 1,1m | 1000 | 687 | 687 (1,00) | 687 (1,00) |
| 19 | 1000 | 1.000.000.000 | 700 | có món > m | 879 | 875 | 199 (0,00) | 872 (0,73) |
| 20 | 1000 | 987.654.321 | 250 | trộn | 1000 | 982 | 920 (0,00) | 980 (0,81) |
| 21 | 1000 | 1.000.000.000 | 120 | lệch | 993 | 993 | 919 (0,00) | 993 (1,00) |
| 22 | 1000 | 1.000.000.000 | 400 | sát m/3 | 1000 | 999 | 999 (1,00) | 999 (1,00) |
| 23 | 1000 | 123.456.789 | 1000 | bất kì ≤ m | 1000 | 1000 | 674 (0,00) | 1000 (1,00) |
| 24 | 1000 | 1.000.000.000 | 10 | nhỏ, b = 10 | 292 | 291 | 289 (0,81) | 292 (1,00) |
| 25 | 1000 | 1.000.000.000 | 1000 | rất nhỏ | 1000 | 1000 | 987 (0,00) | 1000 (1,00) |
Điểm theo subtask (trung bình điểm các test trong subtask):
| Subtask | Điều kiện | Test | Cách 1 tham lam | Cách 2 tìm kiếm cục bộ | Bản đã nộp chính thức |
|---|---|---|---|---|---|
| Subtask 1 (50%) | $m \le 1000$ | 1–13 | 46,98% | 99,23% | 100,00% |
| Subtask 2 (50%) | không ràng buộc thêm | 14–25 | 32,40% | 96,16% | 100,00% |
Lời giải mạnh nhất của mình (cột "bản đã nộp chính thức") khi nộp lên hệ thống chấm của Hội thi (tinhoctre.vn) chỉ được 2,185/100 điểm.
Theo công thức của đề, thí sinh gói được ít nhất bằng Ban giám khảo thì được trọn điểm test đó, và chỉ bị 0 điểm khi kém BGK hơn 10 món. Mà trên bộ test của mình, lời giải này đạt đúng cận trên lý thuyết ở 15/25 test, các test còn lại cũng không thể kém tối ưu nhiều đến thế ở các dạng dữ liệu "dễ". Mình không biết bộ test chính thức, nhưng 2,185 điểm nghĩa là gần như mọi test đều bị 0 điểm – điều này rất khó xảy ra nếu bộ chấm làm đúng công thức. Đây là dấu hiệu bộ chấm chính thức không chấm đúng công thức trong đề (ví dụ: bắt khớp đúng phương án của BGK, hoặc phạt cả khi thí sinh gói nhiều hơn BGK). Mình không kiểm chứng được nguyên nhân nên chỉ ghi nhận như vậy; điểm chính thức của bài này không phản ánh chất lượng lời giải.
Ý tưởngCận trên, và vì sao nên chọn món nhỏ
Đặt $L = \lceil 9m/10 \rceil$. Món nào có $w_i > m$ thì chắc chắn không gói được – loại ngay. Muốn gói nhiều món thì tự nhiên nên ưu tiên món nhẹ. Từ đó có một cận trên đơn giản:
Nhưng chọn toàn món nhỏ chưa chắc đã được: mỗi thùng phải đạt ít nhất $L$ (gần đầy). Ví dụ $m = 10$, các món $1, 1, 9$: hai món nhỏ $1 + 1 = 2 < 9$ không lấp nổi thùng nào, còn món $9$ một mình thì được. Cái khó của bài nằm ở cửa sổ hẹp $[L, m]$ (chỉ rộng 10% sức chứa).
Chiến lược của mình: (1) tham lam ra một phương án hợp lệ; (2) với một số món $k$ cho trước, cố "nhét" $k$ món (bắt đầu từ $k$ món nhỏ nhất) vào $u$ thùng sao cho mọi thùng nằm trong cửa sổ, bằng tìm kiếm cục bộ; (3) dò $k$ từ UB đi xuống.
Em nhập dữ liệu rồi bấm Tiếp để xem cách 2 chạy trên dữ liệu nhỏ: mỗi cột là một thùng, dải xanh là cửa sổ $[L, m]$, thùng đỏ là thùng đang vi phạm; mỗi bước tìm kiếm thử chuyển/đổi món và chỉ giữ lại nếu tổng vi phạm $V$ không tăng:
Cách 1Tham lam lấp từng thùng
Lần lượt với từng thùng $j = 1, 2, \dots$:
- Cho vào các món nhỏ nhất còn lại cho tới khi món tiếp theo làm tràn $m$.
- Nếu tổng vẫn $< L$ (thùng chưa đủ đầy): duyệt các món còn lại từ lớn xuống, món $y$ nào thay được một món nhỏ hơn trong thùng mà không tràn thì thay vào (tổng tăng lên).
- Vẫn không đạt $L$ thì dừng (các thùng sau còn ít món hơn, cũng khó đạt); đạt thì chốt thùng $j$.
- Phương án luôn hợp lệ (mỗi thùng được chốt đều có tổng trong $[L, m]$), nên không bao giờ bị "sai" – chỉ là có thể ít món.
- Cách này hay hụt ở chỗ: lấy quá nhiều món nhỏ vào các thùng đầu, tới khi chỉ còn món to thì không ghép nổi; hoặc dừng sớm khi một thùng không lấp đủ.
Kết quả chạy thật (chấm bằng checker): bản C++ được 39,69 điểm, bản Python cũng 39,69 điểm (cùng thuật toán, chạy lâu nhất 0.075s). Đúng trọn điểm ở các test dễ (ví dụ món lớn chỉ cần mỗi thùng một món), nhưng nhiều test kém đáp án tham chiếu hơn 10 món → 0 điểm.
Cách 2Chọn số món k + tìm kiếm cục bộ
Đổi góc nhìn: cố định số món $k$ muốn gói, rồi hỏi "có xếp được không?". Hàm tryKU(k, r, u):
- Tập món ban đầu: $k - r$ món nhỏ nhất và $r$ món lớn nhất. Thường $r = 0$; nhưng nếu trong $k$ món nhỏ nhất có các món $> m/2$ (mỗi món như vậy phải nằm riêng một thùng) thì thử thêm phương án lấy $r$ món lớn nhất thay cho chúng – vì một món đã chiếm riêng một thùng thì càng to càng dễ lấp đầy thùng đó.
- Số thùng $u$: ít nhất $\lceil T/m \rceil$ ($T$ = tổng khối lượng) và ít nhất bằng số món $> m/2$; thử vài giá trị: ước lượng $2T/(L + m)$ (mỗi thùng ở giữa cửa sổ), cận dưới, $T/L$, và $\min(b, k)$.
- Chia ban đầu: món lớn trước, mỗi món vào thùng đang nhẹ nhất (hàng đợi ưu tiên).
- Hàm phạt $V$ = tổng độ vi phạm: thùng có tổng $s < L$ phạt $L - s$, $s > m$ phạt $s - m$. Mục tiêu: đưa $V$ về 0.
- Tìm kiếm cục bộ: lặp lại: chọn ngẫu nhiên một món $x$ (ưu tiên món đang ở thùng vi phạm) và một trong 3 phép: chuyển $x$ sang thùng khác, đổi $x$ với một món ở thùng khác, đổi $x$ với một món chưa gói (thay đổi tập món!). Nếu $V$ tăng thì hoàn tác. Lâu không giảm được $V$ (20 000 bước) thì bỏ cuộc.
Hàm main: lấy phương án của cách 1 làm "lưới an toàn", rồi thử $k = UB,$ $UB - 1,$ $UB - 2,$ $UB - 4,$ $\dots$ cho tới khi thành công, sau đó tìm nhị phân giữa $k$ thành công và $k$ thất bại. Tổng số bước tìm kiếm giới hạn $6 \cdot 10^6$ để chắc chắn kịp 1 giây; bộ sinh số ngẫu nhiên xorshift với hạt giống cố định nên chạy lại luôn ra cùng kết quả.
- Hàm
moveItemlà "trái tim": chuyển một món và cập nhật $V$ trong $O(1)$ (chỉ 2 thùng thay đổi). "Thùng" số 0 là phần bên ngoài, không tính phạt. - Thử một phép rồi hoàn tác nếu tệ hơn – nhờ
moveItemnhanh nên mỗi bước chỉ vài phép tính, 6 triệu bước chạy khoảng 0,3 giây. - Nhận cả bước "không đổi $V$" (đi ngang) giúp thoát khỏi các vùng phẳng. Mình đã thử thêm "mô phỏng luyện kim" (nhận cả bước tệ hơn với xác suất nhỏ) nhưng trên bộ test này không tốt hơn nên bỏ cho gọn.
- Subtask 1 ($m \le 1000$) gợi ý có thể quy hoạch động theo tổng, nhưng với cách tìm kiếm này thì $m$ lớn hay nhỏ không khác gì nhau.
Kết quả chạy thật (chấm bằng checker): được 97,69 điểm so với đáp án tham chiếu, chạy lâu nhất 0.324s. Ở test 17 và 24, cách 2 còn gói nhiều hơn đáp án tham chiếu. Chỉ còn hụt vài món ở các test khó (món sát $m/3$, dạng "trộn"). Bản Python của cách này mình không viết – với vài triệu bước tìm kiếm thì Python quá chậm.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Điểm trên bộ test CLUE | Lâu nhất |
|---|---|---|---|
| 1. Tham lam lấp từng thùng | C++ | 39,69 | 0.005s |
| Python | 39,69 | 0.075s | |
| 2. Tham lam + chọn k + tìm kiếm cục bộ | C++ | 97,69 | 0.324s |
| Bản đã nộp chính thức (~340 dòng, sinh đáp án tham chiếu) | C++ | 100,00 | 0.463s |