Phân tích: PermRLE

Phần A. Chu trình Hamilton trong thế giới nhỏ

Một chu trình Hamilton trong một đồ thị là một chu trình đi qua mỗi nút đúng một lần. Cho một đồ thị đầy đủ, có hướng, có trọng số trên \(n\) nút, có \((n-1)!\) chu trình Hamilton khác nhau. Một bài toán nổi tiếng là tìm chu trình Hamilton ngắn nhất (hoặc dài nhất) là NP-khó. Nhiều thí sinh cũng biết rằng, đối với \(n\) nhỏ khoảng 20, quy hoạch động tạo ra sự khác biệt giữa \(n \cdot 2^n\) và \(n!\), đó là sự khác biệt giữa một giây và vĩnh cửu.

Hãy cùng xem thủ thuật DP \(n \cdot 2^n\) này, trong trường hợp bạn chưa từng thấy nó trước đây.

Không mất tính tổng quát, chúng ta có thể coi nút 0 là điểm bắt đầu của chu trình, cũng như điểm kết thúc của nó. Với bất kỳ tập con \(A\) nào của tập nút \(V\) và bất kỳ nút \(x\) nào trong \(A\), chúng ta định nghĩa:

Để làm rõ, 0 không nhất thiết phải thuộc \(A\), nhưng chúng ta có tính độ dài của cạnh từ điểm cuối cùng đến nút 0. Do đó, bài toán tìm chu trình Hamilton ngắn nhất chỉ là \(dp[V][0]\). (Hãy tự thuyết phục bản thân, có thể bằng cách nhìn vào (*).)

Chúng ta cần tính \(dp[A][x]\). Đối với các trường hợp dễ dàng khi \(A = \{x\}\), câu trả lời chỉ là độ dài của cạnh \(x \to 0\). Ngược lại, chúng ta tập trung vào bước đầu tiên của đường đi. Nếu bước đầu tiên là \(x \to y\), với độ dài cạnh \(q\), thì chúng ta trả chi phí \(dp[A - \{x\}][y] + q\). Nói chung, \(dp[A][x]\) là:

• \(length(x \to 0)\), nếu \(A = \{x\}\).
• \(\min \{ dp[A - \{x\}][y] + length(x \to y) \mid y \in A - \{x\} \}\), nếu \(|A| > 1\).

Phần B. Đưa mọi thứ vào thế giới nhỏ

Đối với bất kỳ chuỗi nào, hãy định nghĩa số lần chuyển đổi là số lần các ký tự liền kề khác nhau trong chuỗi. Chúng ta muốn tìm một hoán vị biến đổi \(S\) thành \(S'\) sao cho số lần chuyển đổi là tối thiểu. Giả sử độ dài của \(S\) là \(m \cdot k\). Khi đó \(S\) có thể được xem như một chuỗi gồm \(m\) khối có độ dài \(k\).

Bây giờ chúng ta đưa ra một hỗ trợ trực quan để đơn giản hóa việc viết lách. Hãy vẽ chuỗi \(S\) thành \(m\) hàng, mỗi khối trên một hàng duy nhất. Ý tưởng chính là đếm số lần chuyển đổi theo từng cột một.

Hãy lấy một ví dụ bán cụ thể. Giả sử tại một thời điểm chúng ta đã quyết định rằng vị trí thứ 5 trong khối gốc được hoán vị sang vị trí thứ 7 trong khối mới, và vị trí thứ 2 được hoán vị sang vị trí thứ 8. Khi đó, mà không cần biết phần còn lại của hoán vị, chúng ta có thể kiểm tra ký tự thứ 5 và thứ 2 trong mỗi khối. Giả sử trong \(Z\) khối, ký tự thứ 5 và thứ 2 khác nhau, thì chúng ta biết rằng trong bất kỳ hoán vị nào như vậy, chúng ta sẽ phải trả giá là \(Z\).

Một ngoại lệ là phần tử cuối cùng của hoán vị. Trong tất cả các trường hợp trừ một trường hợp, chúng ta chỉ cần quay vòng lại điểm bắt đầu vì phần cuối của mỗi khối \(k\) tiếp xúc với phần đầu của khối \(k\) tiếp theo trong chuỗi, ngoại trừ ký tự cuối cùng trong chuỗi. Chúng ta có thể xử lý cả hai trường hợp nếu chúng ta cố định phần tử cuối cùng của hoán vị bằng cách thử tất cả các khả năng.

Tiếp theo, chúng ta quy bài toán của mình về bài toán ở Phần A. Giả sử chúng ta cố định \(T\) là phần tử cuối cùng trong hoán vị. Định nghĩa một đồ thị đầy đủ, có hướng, có trọng số \(G\) trên \(k\) đỉnh \(\{1, 2, \dots, k\}\). Trọng số trên cạnh \(x \to y\) là:

• số lượng khối mà ký tự thứ \(x\) khác với ký tự thứ \(y\) trong cùng một khối. (nếu \(x \neq T\))
• số lượng khối (không bao gồm khối cuối cùng) mà ký tự thứ \(x\) khác với ký tự thứ \(y\) trong khối tiếp theo. (nếu \(x = T\))

Dễ dàng kiểm tra thấy rằng đối với bất kỳ hoán vị nào, số lần chuyển đổi bằng với độ dài của chu trình Hamilton tương ứng trong \(G\).

Chúng ta có \(k\) lựa chọn khác nhau cho \(T\). Đối với mỗi \(T\), việc tìm chu trình Hamilton ngắn nhất mất thời gian \(O(2^k \cdot k)\). Việc xây dựng đồ thị mất \(O(k^2 \cdot m) = O(k \cdot |S|)\) thời gian cho mỗi \(T\); cũng dễ dàng xây dựng trong \(O(k^2 \cdot m)\) thời gian đồ thị cho tất cả các \(T\). Thời gian chạy của giải pháp là \(O(2^k \cdot k^2 + k \cdot |S|)\).

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