Spring Contest 2022 SPC4
Đề bài
Bún và Đậu là 2 thợ cắt tóc lành nghề và chuyên nghiệp nhất 30 Shine. Hôm nay có $N$ vị khách, mỗi vị khách sẽ yêu cầu một kiểu đầu khác nhau. Bún mất $b_i$ phút để phục vụ cho vị khách thứ $i$, Đậu mất $d_i$ phút để phục vụ cho vị khách thứ $i$. Vì gần đến Tết nên ông chủ muốn phân bố những vị khách để Bún và Đậu phục vụ sao cho cửa tiệm có thể đóng cửa sớm nhất để nhân viên đi về quê. Bún sẽ phục vụ một số vị khách và Đậu sẽ phục vụ một số vị, sao cho thời gian lớn nhất trong tổng thời gian phục vụ của 2 người là nhỏ nhất có thể.
Dữ liệu đầu vào:
- Dòng đầu tiên gồm một số nguyên dương $T$ $(1 \le T \le 40)$ là số lượng bộ dữ liệu của đề bài.
- $T$ bộ dữ liệu tiếp theo, mỗi bộ gồm 3 dòng:
- Dòng đầu tiên chứa một số nguyên dương $N$ là số lượng vị khách.
- Dòng thứ hai chứa $N$ số nguyên dương, số thứ $i$ là $b_i$ – thời gian để Bún phục vụ vị khách thứ $i$.
- Dòng thứ ba chứa $N$ số nguyên dương, số thứ $i$ là $d_i$ – thời gian để Đậu phục vụ vị khách thứ $i$.
Dữ liệu đầu ra: gồm $T$ dòng, mỗi dòng gồm một số nguyên duy nhất là thời gian tối thiểu để phục vụ toàn bộ $N$ vị khách.
Bài toán có 2 Dataset: Small Dataset: $1 \le N \le 14$; Large Dataset: $1 \le N \le 100$. Trong mọi Dataset, ta luôn có $1 \le b_i, d_i \le 100$ (đề gốc ghi $a_i$). Giới hạn: 1 giây, 512 MB cho mỗi Dataset.
4
1
2
3
5
1 1 1 1 1
2 1 4 3 5
8
5 2 5 4 1 3 6 2
9 1 5 2 4 10 4 2
15
9 2 4 12 5 8 10 6 8 29 4 3 5 2 1
8 5 10 8 2 44 1 50 2 4 12 5 2 4 62
3
12
30Giải thích test ví dụ:
- Ví dụ 1: chỉ có duy nhất 1 vị khách nên ai phục vụ nhanh hơn thì để người đó phục vụ. Bún phục vụ chỉ trong 2 phút nên Bún sẽ phục vụ người đó.
- Ví dụ 2: người 1 và 2 do Đậu phục vụ, người 3, 4, 5 do Bún phục vụ. Bún phục vụ người nào cũng trong 1 phút nên thời gian Bún phục vụ là 3 phút; 2 người đầu tiên do Đậu phục vụ cũng tổng cộng 3 phút. Nên thời gian để phục vụ cả 5 vị khách là 3 phút.
- Ví dụ 3 và 4: để thí sinh có thể kiểm tra tính đúng đắn của thuật toán.
Lời mở đầu
Thoạt nhìn đây là bài "chia việc cho 2 người" – dễ bị dụ dùng tham lam (khách nào ai làm nhanh hơn thì giao cho người đó). Nhưng ví dụ 2 cho thấy ngay tham lam sai: Bún làm nhanh hơn ở cả 5 khách, giao hết cho Bún thì mất 5 phút, trong khi đáp án là 3. Mình sẽ đi từ vét cạn $2^N$ cách chia (ăn Small Dataset), rồi biến bài về dạng quy hoạch động cái túi / tổng tập con để ăn Large Dataset.
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ì?
| File test | Số bộ $T$ | $N$ | $b_i, d_i$ | Đáp án |
|---|---|---|---|---|
| 001 (Small) | 20 | 2 – 14 | 1 – 30 | 3 – 114 |
| 002 (Large) | 40 | 2 – 100 | 1 – 100 | 3 – 1842 |
Bài chỉ có 2 file test, mỗi file chứa nhiều bộ dữ liệu. File 001 là Small Dataset: 20 bộ, $N \le 14$, thời gian mỗi khách không quá 30. File 002 là Large Dataset: 40 bộ, trong đó 20 bộ đầu giống hệt file 001, 20 bộ sau có $N$ từ 10 tới 100 và thời gian tới 100. Vì cả file chấm chung một lần nên chỉ cần một bộ lớn chạy chậm là mất trọn file 002.
| Dataset | Điều kiện | File | Cách 1 vét cạn | Cách 2 QHĐ 2 chiều | Cách 3 QHĐ 1 chiều |
|---|---|---|---|---|---|
| Small | $N \le 14$ | 001 | đúng | đúng | đúng |
| Large | $N \le 100$ | 002 | quá thời gian | đúng | đúng |
Ý tưởngCố định tổng thời gian của Bún, tối thiểu thời gian của Đậu
Mỗi cách chia cho ra 2 con số: tổng thời gian của Bún $s_B$ và của Đậu $s_D$; ta muốn $\max(s_B, s_D)$ nhỏ nhất. Hai đại lượng cùng thay đổi nên khó tối ưu trực tiếp. Mẹo quen thuộc của QHĐ cái túi: đưa một đại lượng vào trạng thái. Vì $b_i \le 100$, $N \le 100$ nên $s_B \le 10^4$ – đủ nhỏ để làm chỉ số mảng.
Vì sao chỉ cần $f$ nhỏ nhất? Với cùng $s_B = s$, Đậu càng ít việc thì $\max(s, s_D)$ càng nhỏ (hoặc bằng), nên giữ giá trị nhỏ nhất là đủ. Em nhập dữ liệu rồi bấm Tiếp để xem bảng được điền từng ô (ô vàng đang tính, ô tím $f[i-1][s]$ – giao cho Đậu, ô cam $f[i-1][s-b_i]$ – giao cho Bún, "∞" là không đạt được):
Cách 1Vét cạn 2ᴺ cách chia (Small Dataset)
Mỗi khách chỉ có 2 lựa chọn: Bún hoặc Đậu. Duyệt mọi mask từ $0$ đến $2^N - 1$ (bit $i$ = 1 nghĩa là khách $i$ cho Bún), cộng 2 tổng và lấy $\max$, rồi lấy $\min$ trên mọi mask.
Kết quả chạy thật: đúng 1/2 file test. File 001 (Small, $N \le 14$): $20 \cdot 2^{14} \cdot 14 \approx 4{,}6 \cdot 10^6$ phép tính, chạy tức thì. File 002 có bộ $N = 100$: $2^{100}$ cách chia – không bao giờ chạy xong (còn bị tràn 1 << n khi $n \ge 31$) → quá thời gian.
Cách 2QHĐ bảng 2 chiều f[i][s] (full điểm)
- $S = \sum b_i$ là tổng lớn nhất Bún có thể nhận, nên cột $s$ chỉ chạy từ 0 đến $S \le 10^4$.
- Hằng
INF = 1e9đánh dấu trạng thái không đạt được; kiểm tra< INFtrước khi cộng để không bị cộng vào "vô cùng". - Mảng
f[105][10005]khoảng 4 MB. Mỗi bộ dữ liệu chỉ khởi tạo lại hàng 0 (các hàng sau được ghi đè hết).
Kết quả chạy thật: đúng 2/2 file test, chậm nhất 0,01 giây (cả 40 bộ cộng lại chỉ khoảng $40 \cdot 100 \cdot 10^4 = 4 \cdot 10^7$ phép tính).
Cách 3Tối ưu bộ nhớ: QHĐ 1 chiều
Hàng $i$ chỉ cần hàng $i - 1$, nên dùng 1 mảng $f[s]$ và cập nhật tại chỗ – giống hệt bài cái túi 0/1. Điểm cần cẩn thận: duyệt $s$ giảm dần. Khi đứng ở $s$, ta "đẩy" giá trị cũ $f[s]$ sang ô $s + b_i$ (giao khách cho Bún) – ô này đã được xử lý trước đó (vì lớn hơn) nên không bị dùng lại trong cùng lượt, mỗi khách chỉ được giao đúng 1 lần. Sau đó mới cập nhật chính ô $f[s] \mathrel{+}= d_i$ (giao cho Đậu).
Kết quả chạy thật: bản C++ đúng 2/2 file test, chậm nhất 0,01 giây. Bản Python (cùng ý tưởng 1 chiều) đúng 2/2, chậm nhất 0,57 giây – vẫn kịp 1 giây.
Nhận xét
Đăng nhận xét