Phân tích

Test 1

Ta có thể xem nhiều nhất 475 mô hình trong Test 1, nhưng có tới 595 mô hình nên không thể kiểm tra riêng từng mô hình. Ta nhận thấy rằng khi khảo sát một bộ bất kỳ, ta chỉ cần xem bốn mô hình bất kỳ trong bộ đó (chẳng hạn bốn mô hình đầu tiên), vì có thể suy ra danh tính của mô hình thứ năm. Ví dụ, nếu bốn mô hình đầu tiên trong một bộ lần lượt là D, E, A và B, ta đã biết mô hình cuối cùng trong bộ đó là C. Nhờ vậy, số lượt đoán cần thiết giảm xuống còn \(4 \times 119 = 476\). Nhưng con số này vẫn nhiều hơn giới hạn cho phép đúng một lượt!

Nhận thấy rằng một khi đã xác định thứ tự trong tất cả các bộ trừ một bộ, chỉ còn hai bộ có thể xảy ra: bộ ta chưa kiểm tra và bộ ta còn thiếu. Hai bộ này phải có mô hình khác nhau tại ít nhất hai vị trí, và ta có thể xem một vị trí khác nhau bất kỳ để biết mình đang có bộ nào. Ví dụ, nếu biết hai bộ cuối cùng có thể là CADEB và CDEAB, ta có thể xem vị trí thứ hai; nếu thấy A thì ta có bộ thứ nhất, còn nếu thấy D thì ta có bộ thứ hai. Vì vậy, khi đến bộ thứ 119 trên kệ, ta chỉ cần xem một mô hình trong bộ đó (nhưng việc chọn mô hình nào để xem sẽ phụ thuộc vào những gì đã biết trước đó). Sau lượt xem ấy, ta sẽ biết đủ 119 bộ mình đang có, và do đó cũng biết bộ mình còn thiếu.

Kết hợp các nhận xét trên, ta bảo đảm chỉ dùng nhiều nhất \(4 \times 118 + 1 = 473\) lượt đoán.

Test 2

Trong Test 2, ta chỉ có 150 lượt đoán, không nhiều hơn một lượt cho mỗi bộ là bao! Làm sao ta có thể thành công?

Ta cần tận dụng sâu hơn sự thật rằng mình chỉ thiếu đúng một trong các bộ — tức một trong các hoán vị — có thể có. Trước hết, ta kiểm tra mô hình đầu tiên trong mỗi bộ, dùng 119 lượt đoán. Khi làm vậy, ta sẽ thấy bốn trong năm chữ cái xuất hiện đúng 24 lần mỗi chữ, còn chữ kia chỉ xuất hiện 23 lần. Chữ cái đó chắc chắn là chữ trên mô hình đầu tiên của bộ bị thiếu!

Bây giờ, ta có thể thu hẹp phạm vi tìm kiếm xuống còn 23 bộ bắt đầu bằng chữ cái ấy và xem mô hình thứ hai trong từng bộ; bước này dùng 23 lượt đoán. Một trong các chữ cái sẽ chỉ xuất hiện 5 lần, trong khi mỗi chữ còn lại xuất hiện 6 lần; sau đó, ta tiếp tục thu hẹp phạm vi xuống 5 trong số 23 bộ đó và dùng 5 lượt đoán để xem mô hình thứ ba của chúng. Ta sẽ tìm được một chữ cái thứ ba chỉ xuất hiện duy nhất một lần, rồi chỉ cần kiểm tra mô hình thứ tư trong bộ ấy để biết bộ còn lại — tức bộ bị thiếu — là bộ nào. Tổng cộng, cách này dùng \((5! - 1) + (4! - 1) + (3! - 1) + (2! - 1) = 119 + 23 + 5 + 1 = 148\) lượt đoán, nằm trong giới hạn 150.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 1C — Power Arrangers.