Phân tích: Dancing With the Googlers

Các thí sinh tinh ý có thể nhận thấy bài toán này dựa trên một chương trình truyền hình thực tế. Tác giả của bài toán khi xem một tập của Dancing With the Stars (chương trình này và đơn vị phân phối BBC Worldwide không xác nhận, bảo trợ hay tham gia Google Code Jam), đã tự hỏi liệu có thí sinh nào đạt được ít nhất 8 điểm từ bất kỳ giám khảo nào hay không.

Các giám khảo trong chương trình đó thường cho điểm chênh lệch nhau không quá 1 điểm, và thực sự bất ngờ khi họ chênh lệch nhiều hơn. Có một vài quan sát chính giúp chúng ta giải quyết bài toán này:

1. Bất kỳ tổng điểm không bất ngờ nào cũng được biểu diễn duy nhất bởi một bộ ba điểm số không thứ tự của các giám khảo. Ví dụ: 21 phải là 7 7 7; 22 phải là 7 7 8; 23 phải là 7 8 8.
2. Chỉ có một vài loại tổng điểm bất ngờ. 21 có thể là 6 7 8; 22 có thể là 6 8 8; 23 có thể là 9 7 7. Có một quy luật lặp lại của các tổng điểm bất ngờ kéo dài từ 2 (0, 0, 2) đến 28 (8, 10, 10).
3. Quy luật lặp lại dừng lại ở 2 và 28 vì 1 và 29 không thể bất ngờ: chúng ta không thể sử dụng (-1, 1, 1) cho 1 vì điểm số âm không được phép. Chúng ta cũng không thể sử dụng (9, 9, 11) cho 29 vì điểm số tối đa là 10.

Kết hợp tất cả các sự kiện này, chúng ta có thể dễ dàng xây dựng một bảng ánh xạ từ mỗi tổng điểm đến kết quả tốt nhất của nó nếu nó bất ngờ, và kết quả tốt nhất nếu nó không bất ngờ:

unsurprising(0) = 0
unsurprising(1) = 1
unsurprising(2) = 1
unsurprising(n) = unsuprising(n-3) + 1
unsurprising(n) = ceiling(n/3), for 0 <= n <= 30

surprising(2) = 2
surprising(3) = 2
surprising(4) = 2
surprising(5) = 3
surprising(n) = surprising(n-3) + 1
surprising(n) = ceiling((n-1)/3) + 1, for 2 <= n <= 28

Nhiều thí sinh đã viết lời giải ban đầu mà không tính đến việc 0, 1, 29 và 30 không thể bất ngờ, và do đó đã thất bại ở một trong các ví dụ mẫu. Đó chính là lý do các ví dụ mẫu tồn tại!

Một cách để xây dựng bảng unsurprising(n) và surprising(n) mà không cần suy nghĩ quá nhiều là viết ba vòng lặp để duyệt qua tất cả các bộ điểm số có thể có của giám khảo, kiểm tra xem mỗi tổ hợp ba điểm có hợp lệ hay bất ngờ hay không, và xây dựng các bản đồ theo cách đó.

Bây giờ, đối với mỗi giá trị \(t_i\), chúng ta có một trong ba trường hợp:

• unsurprising(t_i) >= p: Googler này có thể "tốt" (tức là có điểm số tối đa ít nhất là \(p\)) ngay cả với một bộ ba không bất ngờ.
• \(2 \le t_i \le 28\) và surprising(t_i) >= p > unsurprising(t_i): Googler này chỉ có thể "tốt" bằng cách sử dụng một bộ ba bất ngờ.
• Ngược lại, Googler này không thể "tốt".

Một thuật toán tham lam đơn giản sẽ hoạt động: lấy tất cả các Googler thuộc loại thứ nhất, và lấy nhiều nhất có thể (tối đa \(S\)) các Googler thuộc loại thứ hai.

Dựa trên phân tích chính thức của Google Code Jam.