Ký hiệu

Gọi \(M=25\) là số chuột tối đa có thể có.

Test Set 1

Cách giải gồm hai bước: tìm ngưỡng khẩu vị nhỏ nhất trong mọi chú chuột, rồi dùng nó để xác định tổng số chuột \(N\).

Để tìm ngưỡng nhỏ nhất, chỉ cần tìm kiếm nhị phân bằng câu hỏi “ngưỡng nhỏ nhất có lớn hơn hẳn \(X\) không?”. Điều này tương đương hỏi “món chất lượng \(X\) có bị tất cả chuột bỏ qua không?”. Đưa liên tiếp \(2M-1\) món chất lượng \(X\) sẽ bảo đảm mỗi chú gặp ít nhất một món. Nếu không món nào bị ăn, mọi ngưỡng đều lớn hơn \(X\); nếu có ít nhất một món bị ăn, tồn tại chú có ngưỡng không quá \(X\). Có thể dừng sớm ngay khi một món bị ăn để tiết kiệm. Cách này dùng nhiều nhất \(\lceil\log_2 10^6\rceil\times49=980\) món.

Khi đã biết có đúng một chú \(g\) có ngưỡng \(L\), và \(L\) là ngưỡng nhỏ nhất, ta có thể hỏi “đang đến lượt \(g\) phải không?” bằng món chất lượng \(L\), vì chỉ \(g\) ăn nó. Lặp lại nhiều lần và tính tỷ lệ món bị ăn sẽ xấp xỉ \(1/N\). Vì còn rất nhiều món, có thể ước lượng rồi chọn \(N\) sao cho \(1/N\) gần tỷ lệ quan sát nhất. Thực tế, thử \(M^3\) lần bảo đảm đáp án đúng ngay cả trong trường hợp xấu nhất. Chứng minh nằm trong phần giải Test Set 2 dưới đây.

Test Set 2

Lời giải bộ 1 không mở rộng tự nhiên sang bộ 2. Biết tỷ lệ chuột có ngưỡng nhỏ nhất hoặc lớn nhất không còn đủ, vì có thể có nhiều chú cùng ngưỡng. Nếu tỷ lệ là \(1/K\), tổng số chuột có thể là bất kỳ bội số nào của \(K\). Ta phải khảo sát các mức khác; nhưng ở mức không cực trị, kết quả còn bị ảnh hưởng bởi chuột có ngưỡng khác mức đang quan tâm. Vẫn có thể lặp nhiều món cùng chất lượng để trả lời truy vấn tổng quát, nhưng việc diễn giải phản hồi phức tạp hơn phép OR đơn giản.

Truy vấn tỷ lệ chính xác

Truy vấn tự nhiên đầu tiên \(Q\) là: tỷ lệ chính xác các chú có ngưỡng khẩu vị \(\ge X\) bằng bao nhiêu?

Chỉ truy vấn này đã đủ giải bài. Ta thực hiện một dạng tìm kiếm nhị phân nhiều nhánh. Với đoạn mức \([A,B]\) có ít nhất hai mức, giả sử đã biết các tỷ lệ \(X,Y\) tương ứng tại hai đầu, tính tỷ lệ \(Z\) tại \(C=(A+B)/2\). Đệ quy vào \([A,C]\) nếu \(X\ne Z\), và vào \([C,B]\) nếu \(Y\ne Z\), bởi hai tỷ lệ khác nhau khi và chỉ khi trong đoạn làm thay đổi tỷ lệ có ít nhất một chú chuột.

Thuật toán xác định mọi mức có chuột. Với mỗi mức \(L\), tính tỷ lệ chuột đúng tại \(L\) bằng truy vấn rồi trừ tỷ lệ của từng mức nhỏ hơn \(L\). Cuối cùng, lấy bội chung nhỏ nhất (LCM) các mẫu số của những phân số ấy để tìm \(N\).

Cách này cần khoảng \(N\lceil\log_2(10^6)-N\rceil\) truy vấn loại \(Q\). Phần sau cho thấy nếu trả lời từng truy vấn theo cách trực tiếp thì số món quá lớn.

Cách W1: lấy mẫu rồi làm tròn

Đưa đủ nhiều món rồi làm tròn tỷ lệ quan sát về phân số khả thi gần nhất. Nếu số món đủ lớn, làm tròn cho đáp án chính xác. Khi đưa \(X\) món liên tiếp, câu trả lời đúng trên toàn bộ dãy trừ một tiền tố và một hậu tố, mỗi phần dài không quá \(M-1\), nên sai số tổng bị chặn bởi \(2M-2\). Hơn nữa, vì mỗi thử nghiệm có kết quả nhị phân, số phản hồi dương hoặc âm lệch xa nhất khỏi giá trị thật là \(M-1\): với \(M\) lẻ, trường hợp xấu là có \(\lceil M/2\rceil\) kết quả một loại và \(\lfloor M/2\rfloor\) loại kia, rồi cả tiền tố lẫn hậu tố dài \(\lfloor M/2\rfloor\) cùng cho một loại. Với \(M\) chẵn, cận xấu nhất là \(M\).

Ta chỉ xét các phân số có mẫu không quá \(M\), nên khoảng cách giữa hai kết quả khác nhau ít nhất \(1/(M(M-1))\). Nếu sai số nhỏ hơn một nửa khoảng cách ấy, làm tròn chắc chắn đúng. Ghép với sai số tổng cỡ \(M\), cần \(M^3\) món để trả lời \(Q\) hoàn hảo. Tổng \(M\lceil\log_2(10^6)-M\rceil M^3\) vượt xa ngân sách.

Cách W2: dùng bội chung nhỏ nhất

Luôn dùng đúng \(R\) món liên tiếp, với \(R\) là LCM của mọi kết quả có thể. Khi đó sai số bằng \(0\), vì mỗi chú nhận đúng cùng số cơ hội. Nhưng \(\operatorname{lcm}(2,3,\ldots,25)\) cũng quá lớn, nên cách này riêng lẻ không dùng được.

Cách W3: chỉ so sánh xấp xỉ

Ta chỉ cần số chính xác ở các mức cuối cùng ngay trước khi lấy LCM. Ở các nút trung gian của tìm kiếm nhị phân nhiều lá, chỉ cần biết một đoạn có chuột hay không. Thay vì các tỷ lệ chính xác \(X,Y,Z\) tại \(A,B,C\), dùng các xấp xỉ \(X',Y',Z'\) đủ tốt để quyết định hai giá trị thật có bằng nhau không.

Dùng \(2M^2\) món bảo đảm gặp mỗi chú ít nhất \(2M\) lần. Nếu \(X\ne Z\), hai xấp xỉ về tổng số phản hồi dương chênh ít nhất \(2M\). Vì phân tích trên chặn sai số tổng của hai xấp xỉ bởi \(M-1\), sai số của hiệu không quá \(2M-1\); so sánh hiệu với \(2M\) đủ phân biệt hai tỷ lệ thật có bằng nhau. Điều này giảm đáng kể số món: tìm kiếm nhiều lá cần \(M\lceil\log_2(10^6)-M\rceil M^2\), sau đó cần thêm \(MM^3\) hoặc \(MR\) để lấy các kết quả cuối chính xác. Tuy vậy, tổng vẫn quá lớn.

Thuật toán cuối cùng

Phải kết hợp cả ba biến thể. Bắt đầu tìm kiếm nhị phân nhiều lá bằng W3. Mỗi khi tìm thấy một mức, dùng W1 hoặc W2, tùy cách nào rẻ hơn, để lấy tỷ lệ thật của mức ấy. Nếu đệ quy vào đoạn lớn hơn trước, ta tìm các mức từ cao xuống thấp, nhờ đó thực hiện được phép trừ. Khi có tỷ lệ thật, có thể thu hẹp các giá trị \(N\) khả dĩ còn các bội của mẫu số; điều này làm \(R\) giảm. Cuối cùng, \(R\) có thể đủ nhỏ để dùng W2 ngay cả cho tìm kiếm nhị phân thay cho W3.

Mỗi lần chuyển sang W2, vì trước đó đã dùng các phương pháp khác, cần thêm tối đa \(R\) món để “căn chỉnh” vị trí trong chu kỳ, tùy số món đã dùng. Nhưng một khi dùng \(R\) cho mọi thứ, chi phí căn chỉnh này rất nhỏ.

Phân tích chính thức để lại cho người đọc việc chứng minh chính xác tổng số món, nhưng với các cận cẩn thận có thể chứng minh nó không bao giờ vượt \(S\); nhóm tác giả không tìm thấy trường hợp nào vượt khoảng \(85\%S\). Lý do là: nếu mẫu số của một tỷ lệ lớn hơn \(M/2\), chỉ còn một giá trị \(N\) khả dĩ và ta xong. Nếu mẫu số nhỏ hơn \(M/2\) nhưng vẫn khá lớn, số khả năng của \(N\) giảm mạnh, còn LCM giảm mạnh hơn vì gcd của các khả năng lớn hơn \(1\). Nếu mẫu số nhỏ, mức vừa tìm có nhiều chuột, làm giảm tổng chi phí của tìm kiếm nhị phân nhiều lá.

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2018, Chung kết thế giới, bài Go, Gophers!.