Phân tích

Các lời giải dựa trên thực tế rằng lợi thế của kẻ gian lận làm tăng số câu đúng độc lập với độ khó. Xét theo tổng số câu đúng, một kẻ gian có trình độ cơ sở \(B\) sẽ trông giống một người chơi có trình độ \(B+\Delta\) với một \(\Delta\) đáng kể (giá trị \(\Delta\) phụ thuộc vào \(B\)).

Tuy nhiên, kẻ gian này làm kém hơn một người thật sự có trình độ \(B+\Delta\) ở các câu dễ và tốt hơn ở các câu khó. Lý do là những câu đúng do gian lận được phân bố đều, thay vì tập trung nhiều hơn ở các câu dễ như khi trình độ tăng.

Test Set 1

Có nhiều cách đạt độ chính xác \(10\%\). Một cách là ước lượng độ khó của mỗi câu bằng số người trả lời đúng, sắp xếp câu hỏi theo độ khó đó, rồi kiểm tra mức độ đồng đều của phân bố câu đúng của từng ứng viên. Phân bố càng gần đều, người đó càng giống kẻ gian lận.

Một thước đo khả dĩ là số cặp câu hỏi có kết quả khác nhau sao cho câu trả lời sai được ước lượng là câu dễ hơn câu trả lời đúng. Dùng thước đo này vừa đủ để vượt qua Test Set 1.

Test Set 2

Vấn đề của việc đếm nghịch thế như thước đo ở Test Set 1 là nó rất nhạy với trình độ người chơi. Cụ thể, một danh sách có rất ít câu đúng hoặc rất ít câu sai tạo ít cơ hội xuất hiện nghịch thế hơn một danh sách có hai loại kết quả tương đối cân bằng.

Ta khắc phục bằng cách chia số nghịch thế cho số nghịch thế kỳ vọng trong một thứ tự ngẫu nhiên. Việc chuẩn hóa này giảm nhiễu đủ để vượt qua Test Set 2.

Một cách khác để tăng độ chính xác — cho số nghịch thế hoặc bất kỳ thước đo nào khác — là chỉ xét các câu cực dễ và cực khó, bởi khác biệt giữa phân bố câu đúng đồng đều và phân bố thiên lệch mạnh thể hiện rõ hơn ở đó. Tỷ lệ chính xác phụ thuộc vào thước đo, nhưng trong các lời giải thử nghiệm của chúng tôi, khoảng \(5\%\) câu dễ nhất và \(5\%\) câu khó nhất là phù hợp.

Các thước đo khác chính xác hơn số nghịch thế và cũng giải được bài. Chúng tôi tìm thấy hai kỹ thuật đủ tốt. Kỹ thuật thứ nhất: sắp xếp người chơi theo trình độ ước lượng (tổng số câu đúng), chỉ đếm câu đúng trên nhóm câu “cực trị”, rồi so sánh với những người lân cận có trình độ ước lượng tương tự. Giả sử kẻ gian là người có chênh lệch lớn nhất so với các hàng xóm.

Kỹ thuật thứ hai: ước lượng trình độ thật bằng sigmoid ngược của tỷ lệ đúng của từng người, đồng thời ước lượng độ khó thật của câu hỏi bằng sigmoid ngược của tỷ lệ người trả lời đúng. Từ hai ước lượng đó, tính số câu đúng kỳ vọng của mỗi người trên nhóm câu cực trị. Người có chênh lệch lớn nhất giữa kỳ vọng và giá trị thực là kẻ gian. Kỹ thuật cuối này có thể đạt độ chính xác trên \(90\%\).

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng loại, bài Cheating Detection.