Điều kiện chấp nhận của bài dựa trên competitive analysis (phân tích cạnh tranh).

Bài khá khó kiểm thử cục bộ ngay cả đối với một bài tương tác. Dễ sinh một tập sở thích khách hàng cụ thể, nhưng để xác định số kẹo tối đa có thể bán cần giải ghép cặp hai phía. Tuy nhiên, vì chỉ có một Test Set hiển thị, ta có thể thử nghiệm và chấp nhận một vài bước suy luận mang tính tin tưởng có cơ sở.

Một chiến lược chỉ chọn ngẫu nhiên trong các vị hợp lệ không đủ để vượt qua. Ta cần ba nhận xét:

1. Nếu có thể bán thì bán một cây không bao giờ tệ hơn không bán. Giả sử một lời giải tốt không bán ở hiện tại và về sau bán tổng cộng \(L\) cây. Bán ngay bây giờ nhiều nhất chỉ ngăn một cây được bán về sau, nên vẫn có thể bán thêm \(L-1\) cây; tổng không giảm.
2. Khi có nhiều vị để chọn, tốt nhất là bán vị có xác suất được thích thấp nhất. Trực giác là ta giữ lại những vị có khả năng xuất hiện trong yêu cầu tương lai cao hơn; trực giác này có thể được chứng minh bằng toán học.
3. Ta không biết xác suất thật. Ước lượng tốt nhất tại một thời điểm cho một vị là số khách đã thích vị đó từ trước đến nay chia cho tổng số khách đã quan sát.

Vì thế, luôn bán nếu có thể. Duy trì số lần mỗi vị đã xuất hiện trong danh sách sở thích của những khách đã gặp. Trong các vị khách hiện tại thích và chưa bán, chọn vị có số lần xuất hiện nhỏ nhất rồi đánh dấu đã bán; nếu không có vị hợp lệ thì in -1.

Khi hòa, nên phá hòa ngẫu nhiên để đề phòng tác giả đoán trước và cản những quy tắc cố định như luôn lấy ID nhỏ nhất. Trong bài này, tác giả thực ra không thể dùng judge để trừng phạt quy tắc đó, vì sở thích được cố định độc lập với lựa chọn của chương trình.

Chiến lược không hoạt động với một danh sách xác suất tùy ý, ngay cả với 200 khách. Chẳng hạn, nếu mọi xác suất đều bằng 0,02, các vị giống nhau nên chiến lược mất khả năng phân biệt; mỗi vị xuất hiện đủ thường xuyên để cách trực tuyến kém ghép cặp đáng kể, nhưng lại đủ thưa để có rất ít cơ hội sửa lựa chọn. Đề bảo đảm các xác suất được lấy ngẫu nhiên từ \([0.005,0.1]\), tạo đủ khác biệt để chiến lược khai thác.

Thuật toán mô tả trên có thể chứng minh là tốt ít nhất bằng mọi lời giải khác trong mô hình của đề. Editorial còn lưu ý: nếu vẫn chưa chắc chắn, với một bài chỉ có Test Set hiển thị, thường nên thử nộp và chấp nhận nguy cơ phạt 4 phút thay vì lo lắng quá 4 phút.

Mỗi lượt xử lý \(O(D)\) và dùng \(O(N)\) bộ nhớ.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2018, Round 1C, bài Lollipop Shop; kho Google Coding Competitions (Apache-2.0).