Test Set 1

Ta có thể nghĩ đến việc liệt kê mọi cách gán các bit cho các thu ngân, nhưng với 20 bit và 5 thu ngân, số cách có thể lên tới \(5^{20}\) — quá nhiều để kiểm tra! Ta cần tận dụng việc các bit không thể phân biệt được, và thay vào đó tìm mọi cách phân hoạch \(B\) bit cho \(R\) trong số \(C\) thu ngân (vì số thu ngân ta có thể sử dụng không thể nhiều hơn số robot). Sau đó, ta tính thời gian của từng cách và chọn giá trị nhỏ nhất.

Ta có thể tính số cách phân hoạch 20 bit cho 5 robot bằng phương pháp chia kẹo Euler. Hóa ra chỉ có \(\binom{24}{4}=10\,626\) cách cần kiểm tra. Nếu số robot ít hơn số thu ngân, ta cần nhân thêm hệ số \(\binom{C}{R}\), nhưng trong Test Set 1 hệ số này không thể lớn hơn 10. Mỗi lần kiểm tra mất \(O(R)\) thời gian, rất nhỏ vì \(R\) không quá 5.

Test Set 2

Để giải Test Set này, ta cần trả lời câu hỏi sau: với một giới hạn thời gian \(T\), có tồn tại cách phân phối bit sao cho tất cả robot hoàn tất tương tác với thu ngân trong không quá \(T\) giây hay không? Gọi \(f(T)\) là câu trả lời cho câu hỏi đó.

Làm thế nào để tìm \(f(T)\)? Số bit tối đa mà thu ngân thứ \(i\) có thể xử lý trong không quá \(T\) giây là

Ta gọi giá trị này là \(Capacity_i\).

Tiếp theo, ta cần biết liệu có thể giao tổng cộng \(B\) bit cho \(R\) robot, rồi giao mỗi robot cho một thu ngân, sao cho số bit do thu ngân thứ \(i\) xử lý không vượt quá \(Capacity_i\) hay không. Ta tham lam sắp các giá trị Capacity theo thứ tự không tăng, rồi giao \(R\) robot cho \(R\) thu ngân đầu tiên. \(f(T)\) đúng khi và chỉ khi tổng số bit mà \(R\) thu ngân đầu tiên có thể xử lý ít nhất bằng \(B\). Do đó, ta có thể tính \(f(T)\) bất kỳ trong \(O(C\log C)\) thời gian, chính là thời gian sắp xếp các giá trị Capacity. (Ngoài lề: ta thậm chí có thể tránh sắp xếp và thay vào đó phân hoạch trong \(O(C)\) thời gian, chẳng hạn bằng introselect.)

Vì muốn tối thiểu hóa thời gian để tất cả robot tương tác với thu ngân, ta cần tìm giá trị \(T\) nhỏ nhất sao cho \(f(T)\) đúng. Giá trị \(T\) đó còn thỏa:

• \(f(x)\) sai với mọi \(x<T\);
• \(f(x)\) đúng với mọi \(x\ge T\).

Vì vậy, ta có thể tìm \(T\) bằng tìm kiếm nhị phân. Đáp án lớn nhất không vượt quá \(O(\max(S)\times B+\max(P))\), nên thuật toán chạy trong

thời gian.

Nguồn

Dịch đầy đủ từ phân tích chính thức của Google Code Jam 2018, Round 1A, bài Bit Party.