Phân tích: The Repeater

Đầu tiên, chúng ta hãy xem xét điều kiện thắng cho Omar. Để làm điều này, chúng ta sẽ xem xét ví dụ sau:

3
aabcaa
abbcaa
abccaa

Chúng ta biểu diễn các chuỗi đã cho bằng cách mượn ý tưởng từ Mã hóa độ dài chạy (Run-length Encoding). Sử dụng ý tưởng từ cách mã hóa này, chuỗi "aabcda" có thể được biểu diễn thành "2:a, 1:b, 1:c, 1:d, 1:a". Biểu diễn này cho thấy một danh sách có thứ tự các cặp tần suất và ký tự tương ứng, hãy gọi nó là chuỗi tần suất. Tương tự, chúng ta có thể tìm ra chuỗi tần suất cho tất cả các chuỗi ban đầu. Các chuỗi tần suất cho các chuỗi trong ví dụ được liệt kê dưới đây:

aabcaa  ->  2:a, 1:b, 1:c, 2:a
abbcaa  ->  1:a, 2:b, 1:c, 2:a
abccaa  ->  1:a, 1:b, 2:c, 2:a

Lưu ý rằng trong bài toán, một thao tác được định nghĩa là (i) lặp lại một ký tự, hoặc (ii) xóa một ký tự lặp lại. Trong chuỗi tần suất, các thao tác được phép của chúng ta có thể được phát biểu lại như sau: Thao tác thứ nhất tương đương với việc tăng tần suất của một ký tự, trong khi thao tác thứ hai tương đương với việc giảm tần suất của một ký tự. Tuy nhiên, lưu ý rằng chúng ta không thể giảm tần suất của một ký tự xuống dưới 1. Với các chuỗi này, chúng ta nhận thấy rằng Omar sẽ thắng khi danh sách các ký tự có thứ tự (không bao gồm tần suất) là giống hệt nhau. Ngược lại, Fegla sẽ thắng vì các thao tác được phép chỉ có thể tăng tần suất của một ký tự trong chuỗi tần suất đã mã hóa hoặc giảm tần suất (nhưng không bao giờ được phép xuống dưới 1). Vì vậy, nếu danh sách các ký tự có thứ tự của bất kỳ hai chuỗi nào không khớp nhau, Omar sẽ không thể thắng.

Khi đã biết cách xác định Omar có thể thắng hay không, chúng ta quan tâm đến số lượng thao tác tối thiểu để thắng trò chơi. Lưu ý rằng các thao tác thực hiện trên ký tự thứ \(i\) trong các chuỗi tần suất có thể được áp dụng độc lập với các ký tự ở các vị trí khác trong chuỗi tần suất. Do đó, chúng ta có thể xử lý một tập hợp các ký tự tại vị trí \(i\) trước khi xử lý các ký tự ở vị trí tiếp theo. Đối với ví dụ trên, chúng ta có thể giải quyết các chữ "a" dẫn đầu trước, sau đó đến "b", rồi "c", và cuối cùng là chữ "a" ở cuối. Từ đây về sau, chúng ta sẽ mô tả việc giải quyết cho một ký tự (tại vị trí thứ \(i\)) trong các chuỗi tần suất. Tất cả các ký tự khác có thể được giải quyết theo cùng một cách.

Thuật toán vét cạn:

Trong giải pháp vét cạn, chúng ta sẽ thử tất cả các tần suất mục tiêu có thể cho một ký tự duy nhất, ví dụ đối với ký tự "a", chúng ta sẽ thử tất cả các tần suất có thể của "a" là "1:a", sau đó là "2:a", rồi "3:a", v.v. Chúng ta gọi mỗi tần suất thử nghiệm là tần suất mục tiêu. Trong bài toán này, vì độ dài của chuỗi chỉ lên đến 100, do đó chúng ta có thể thử tất cả các tần suất mục tiêu từ 1 đến 100. Đối với mỗi tần suất mục tiêu, chúng ta có thể tính tổng số thao tác (là giá trị tuyệt đối của hiệu giữa tần suất của ký tự đó và tần suất mục tiêu) và duy trì tần suất mục tiêu mang lại tổng số thao tác tối thiểu.

Độ phức tạp thời gian cho thuật toán vét cạn là \(O(L \cdot N \cdot X)\), trong đó \(L\) là độ dài tối đa của bất kỳ chuỗi nào, \(N\) là số lượng chuỗi, và \(X\) là số lượng ký tự trong chuỗi tần suất.

Giải pháp này đủ để giải quyết cả bộ dữ liệu nhỏ và lớn đã cho.

Thuật toán hiệu quả:

Trong giải pháp vét cạn, chúng ta đã thử tất cả các tần suất có thể cho một ký tự duy nhất. Nhưng chúng ta không cần phải làm vậy, chúng ta chỉ cần thử một tần suất mục tiêu duy nhất!

Chúng tôi muốn chỉ ra rằng theo trực giác, người ta có thể nghĩ rằng số trung bình cộng (mean) sẽ là tần suất mục tiêu. Hãy xem xét một ví dụ. Giả sử chúng ta được cho các tần suất \(\{1, 1, 100\}\). Trung bình cộng là 34. Tổng các hiệu số tuyệt đối từ các tần suất đã cho đến tần suất mục tiêu là \(|1-34| + |1-34| + |100-34| = 33 + 33 + 66 = 132\). Nhưng nếu tần suất mục tiêu là 30 thay vì 34 thì sao? Khi đó tổng các hiệu số tuyệt đối là \(|1-30| + |1-30| + |100-30| = 29 + 29 + 70 = 128\), nhỏ hơn 132! Thực tế, nếu chúng ta thử tất cả các giá trị có thể cho tần suất mục tiêu (từ 1 đến 100), chúng ta sẽ thấy rằng giá trị tối thiểu là tại 1 với tổng là 99. Thực tế, chính số trung vị (median) mới là giá trị làm tối thiểu hóa tổng các hiệu số tuyệt đối (1 là trung vị của \(\{1, 1, 100\}\)).

Trong ví dụ của chúng ta ở trên, các tần suất cho chữ "a" dẫn đầu là \(\{2, 1, 1\}\), cho "b" là \(\{1, 2, 1\}\), cho "c" là \(\{1, 1, 2\}\), và cho chữ "a" cuối cùng là \(\{2, 2, 2\}\). Do đó, đối với chữ "a" dẫn đầu, chúng ta sẽ sử dụng trung vị là 1 làm tần suất mục tiêu. Tương tự đối với "b" và "c" chúng ta sử dụng 1, trong khi đối với chữ "a" cuối cùng, tần suất mục tiêu là 2.

Bạn có thể thắc mắc tại sao trung vị lại là tần suất mục tiêu đúng, chúng tôi xin dẫn ra một lời giải thích tuyệt vời của Michal Forišek cho câu hỏi "Tại sao trung vị lại làm tối thiểu hóa tổng các độ lệch tuyệt đối?" mà chúng tôi trích dẫn ở đây:

Trong lời giải thích trên, việc tối thiểu hóa tổng các độ lệch tuyệt đối tương đương với việc tối thiểu hóa tổng số thao tác cần thiết để chuyển đổi bất kỳ ký tự thứ \(i\) nào trong chuỗi tần suất thành một tần suất mục tiêu trong bài toán của chúng ta.

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