Phân tích: Pottery Lottery

Một cách tiếp cận đơn giản (nhưng không chính xác)

Suy nghĩ hấp dẫn đầu tiên có thể là: tại sao không bỏ một thẻ của chúng ta vào mỗi bình? Sau đó ta chỉ việc ngồi chờ chiến thắng, bất kể bình nào được chọn. Ai cần đến 80 ngày còn lại chứ?

Sai sót trong lập luận này là nếu nhiều bình cùng có ít thẻ nhất thì không có người chiến thắng. Một phép mô phỏng nhanh cho thấy chỉ khoảng 57% số lần có đúng một bình chiến thắng. Vì vậy, cách tiếp cận này không có hy vọng vượt qua bài và ta phải cố gắng hơn!

Một cách tiếp cận phức tạp hơn đôi chút (nhưng cũng không chính xác)

Có vẻ như ta vẫn có thể thành công mà không cần kiểm tra bất kỳ bình nào. Giả sử ta chọn trước một bình — không mất tính tổng quát, ta chọn bình số 20 — rồi cố biến nó thành bình chiến thắng thì sao? Trong 99 đêm đầu tiên, ta phân phối các thẻ giả vào 19 bình còn lại càng đều càng tốt (để không bình nào trong số đó trở thành mối đe dọa lớn hơn các bình khác). Số hiệu trên những thẻ giả này không quan trọng, vì ta đặt cược rằng bình 20 sẽ thắng. Sau đó, vào đêm thứ 100, ta đặt thẻ của mình vào bình 20. Vì mỗi bình trong 19 bình kia đều phải gánh thêm 5 (hoặc thậm chí 6) thẻ, khả năng bình 20 có ít thẻ nhất hẳn là cao, đúng không?

Đáng tiếc, khả năng ấy không cao đến vậy. Một lần nữa, ta có thể viết một phép mô phỏng nhanh để xác nhận rằng chiến lược này chỉ thành công khoảng 53% số lần — thậm chí còn tệ hơn chiến lược phía trên! "Gánh nặng" trung bình mà ta thêm vào các bình khác đơn giản là chưa đủ lớn so với biến động ngẫu nhiên của số thẻ trong mỗi bình.

Một cách tiếp cận tốt hơn

Ta cần tận dụng khả năng kiểm tra bình, nhưng nên dùng nó khi nào? Kiểm tra sớm trong cuộc xổ số không đem lại nhiều giá trị vì khi ấy mới chỉ có tương đối ít thẻ được đặt vào. Mặt khác, nếu kiểm tra quá muộn, ta có thể không còn đủ số đêm để phản ứng với thông tin vừa phát hiện.

Ta có thể xây dựng một phiên bản của cách tiếp cận đầu tiên có kết hợp việc kiểm tra bình. Trong cách này, \(V\) và \(N\) là các tham số mà ta sẽ phải tìm ra:

1. Chọn "từ bỏ" \(V\) bình đầu tiên. Ta giả định rằng không bình nào trong số này sẽ thắng, nên số hiệu trên các thẻ ta thêm vào chúng không quan trọng. Dành \(N\) đêm đầu tiên để phá chúng (một cách đồng đều).
2. Dành 20 lượt tiếp theo để lần lượt kiểm tra tất cả các bình.
3. Dựa trên kết quả kiểm tra, chọn bình có ít thẻ nhất (trong số \(20-V\) bình còn lại) làm bình ứng viên chiến thắng.
4. Trong mỗi đêm còn lại trong số \(99 - 20 - N\) đêm, chọn một bình (khác bình ứng viên) có số thẻ nhỏ nhất theo kết quả kiểm tra và thêm một thẻ vào đó. Sau đó, cập nhật kết quả kiểm tra để phản ánh thay đổi này.
5. Vào ngày thứ 100, thêm thẻ của chính ta vào bình ứng viên.

Ta có thể lo rằng kết quả kiểm tra chỉ là những ảnh chụp tại một thời điểm rồi dần trở nên lỗi thời. Khi ta kiểm tra bình 20, ước lượng cho bình 1 đã không còn mới — nếu có thêm thẻ được bỏ vào bình 1 kể từ đó thì sao? Để so sánh các ước lượng công bằng hơn một chút, ta có thể điều chỉnh chúng theo số thẻ kỳ vọng đã được thêm vào kể từ đêm thực hiện ước lượng (tức là số đêm đã trôi qua thêm chia cho 20). Mức điều chỉnh này nhiều nhất là \(0{,}95\), nhỏ hơn một thẻ nguyên, nên các điều chỉnh chỉ có thể được dùng để phá hòa giữa những bình có cùng số thẻ... và ta có thể đạt hiệu quả tương tự bằng cách chọn bình có ID lớn nhất khi hòa.

Quá trình này không quá khó mô phỏng, vì vậy ta có thể thử các giá trị \(V\) và \(N\) khác nhau để xem lựa chọn nào cho kết quả tốt nhất, rồi nhận thấy \(V = 14\), \(N = 60\) thành công khoảng 95% số lần. Theo phân phối nhị thức, điều đó cho ta xác suất khoảng 99,96% giải đúng ít nhất 225 trong 250 trường hợp. Vì bài chỉ có một Test Set Hiển thị, ta chỉ cần nộp bài và hy vọng điều tốt nhất!

Ta có thể làm tốt hơn nữa không?

Nếu muốn thử nghiệm thêm, vẫn còn những lời giải tốt hơn! Sau đây là một biến thể của chiến lược trên; nó thành công hơn 98% số lần:

• Ngày 1–60: Bỏ 4 thẻ vào mỗi bình từ 1 đến 15.
• Ngày 61–80: Kiểm tra mọi bình. Tìm hai bình có ít thẻ nhất (khi hòa, ưu tiên bình mang số lớn hơn; ta sẽ luôn phá hòa như vậy trong toàn bộ chiến lược này) và chỉ định chúng làm các ứng viên.
• Ngày 81–94: Theo chiến lược tham lam, bỏ một thẻ vào bình không phải ứng viên có số thẻ nhỏ nhất theo kết quả kiểm tra. Cập nhật các kết quả đó.
• Ngày 95–96: Kiểm tra lại hai ứng viên và chốt chọn bình có ít thẻ hơn.
• Ngày 97–99: Phá ứng viên còn lại.

Nếu giữ lại hai ứng viên, khả năng cả hai cùng tích lũy nhiều thẻ do kém may mắn trong giai đoạn phá thứ hai sẽ thấp hơn. Ta được lợi khi trì hoãn thời điểm ra quyết định càng lâu càng tốt, trong khi vẫn chừa đủ thời gian để xử lý ứng viên về nhì.

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 2 — Pottery Lottery.