Phân tích: Letter Stamper

Ý tưởng bài toán bắt nguồn từ báo cáo về một trong những bài nói chuyện của Robert Tarjan, nơi một lời giải bậc hai cho bốn chữ cái đã được khẳng định. Chúng tôi nhận thấy phiên bản ba chữ cái dễ hơn nhưng vẫn rất thú vị, và đã đưa nó vào làm bài đầu tiên cho vòng chung kết Code Jam này.

Lưu ý rằng trường hợp tổng quát khi kích thước bảng chữ cái không bị giới hạn ở một hằng số nhỏ như 3 có thể được giải bằng quy hoạch động trong \(O(n^3)\). Nó đã từng xuất hiện trong một số cuộc thi lập trình trước đây.

Trạng thái hiện tại được đặc trưng bởi một cặp (S, K), trong đó S là hậu tố của chuỗi đầu vào bạn vẫn cần in (vì vậy chữ cái tiếp theo bạn cần in là ký tự đầu của S), và K là ngăn xếp. Đối với mỗi tình huống, chúng ta cần quyết định xem bước tiếp theo là push, pop hay print.

Chúng tôi đưa ra một số quy tắc được thỏa mãn bởi một chuỗi thao tác tối ưu. Những quy tắc này sẽ làm cho lời giải trở nên rõ ràng hơn. Có thể có các chuỗi tối ưu khác, nhưng bạn luôn có thể biến đổi chúng về một chuỗi thỏa mãn các điều kiện này.

Quy tắc 1. Nếu chữ cái đầu tiên của S giống với đỉnh của K, thì bước tiếp theo là print.

Quy tắc 2. Bạn không bao giờ cần push một chữ cái đã có sẵn ở đỉnh ngăn xếp. Do đó, không có chữ cái nào xuất hiện hai lần liên tiếp trong ngăn xếp.

Quy tắc 3. Ngay sau khi bạn push một chữ cái X, bước tiếp theo là print X.

Các quy tắc trên là hiển nhiên và chúng tôi bỏ qua phần giải thích. Nhưng bạn nên dành một chút thời gian để tự thuyết phục bản thân một cách chặt chẽ.

Quy tắc 4. Không bao giờ có ba chữ cái liên tiếp trong ngăn xếp có dạng XYX.

Hãy cùng chứng minh quy tắc này. Giả sử một giải pháp tối ưu có XYX trong ngăn xếp. Hãy sửa đổi nó. Tại một thời điểm nào đó, đỉnh ngăn xếp là XY và chúng ta định push thêm một chữ X. Thay vào đó, chúng ta sẽ pop chữ Y. Sau đó tiếp tục như trước, cho đến khi chúng ta định pop chữ X thứ hai mà giờ không còn tồn tại. Thay vào đó, chúng ta sẽ push Y, quay lại trạng thái giống như trước đó. Bằng cách này, chúng ta đã rút ngắn ngăn xếp trong khi vẫn đạt được một giải pháp có cùng độ dài. Bằng phương pháp quy nạp, bạn có thể tiếp tục đơn giản hóa giải pháp cho đến khi cả 4 quy tắc đều được thỏa mãn.

Quy tắc 4 cùng với Quy tắc 2 ngụ ý rằng ngăn xếp luôn chứa một chu kỳ gồm 3 chữ cái, ví dụ: ABCABCABC.... Khi đó, trạng thái của ngăn xếp được xác định hoàn toàn bởi hai chữ cái đầu tiên và chiều cao của ngăn xếp. Chỉ có 6 mẫu chu kỳ như vậy (AB, AC, BA, BC, CA, CB), và chiều cao của ngăn xếp không bao giờ lớn hơn \(n\). Do đó, số lượng trạng thái (S, K) khả thi là \(O(n^2)\). Điều này dẫn đến một lời giải quy hoạch động với độ phức tạp bậc hai.

Cách cài đặt cụ thể

Gọi \(dp[i][j][k]\) là số thao tác tối thiểu để in xong \(i\) ký tự đầu tiên, với ngăn xếp hiện tại có độ cao \(j\) và hai ký tự trên cùng của ngăn xếp (theo thứ tự từ dưới lên) tạo thành một mẫu cụ thể \(k \in \{AB, AC, BA, BC, CA, CB\}\).

Tuy nhiên, với Quy tắc 4, ta có thể đơn giản hóa hơn: tại mỗi bước \(i\) (khi cần in ký tự \(S[i]\)), ta chỉ cần quan tâm đến:

1. Vị trí hiện tại trong chuỗi \(S\): \(i\).
2. Độ cao của ngăn xếp: \(h\).
3. Ký tự ở đỉnh ngăn xếp: \(top\).
4. Ký tự ngay dưới đỉnh ngăn xếp: \(under\).

Vì chỉ có 3 chữ cái, nếu biết \(top\) và \(under\), ký tự còn lại là duy nhất. Mẫu ngăn xếp sẽ có dạng \(...XYZXYZ\).

Với \(N \le 7000\), trạng thái \(DP[i][h]\) (với \(i\) là vị trí trong chuỗi và \(h\) là độ cao ngăn xếp) kết hợp với thông tin về các ký tự trong ngăn xếp sẽ cho phép giải trong \(O(N^2)\).

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