Diễn giải bài toán

Trước hết, bài toán tương đương với việc tìm một thứ tự nối các chuỗi thành phần sao cho mọi lần xuất hiện của cùng một chữ cái nằm liền nhau.

Test Set 1

Vì \(\mathbf{N}\le6\), số hoán vị của các chuỗi nhiều nhất là \(6!=720\). Ta sinh mọi hoán vị và với mỗi hoán vị, kiểm tra chuỗi cuối thu được khi nối các chuỗi đầu vào theo thứ tự đó.

Xét chuỗi CCCABDAEEF. Để kiểm tra, chỉ cần:

1. Lấy tập chữ cái xuất hiện: \(\{A,B,C,D,E,F\}\).
2. Rút gọn mỗi đoạn ký tự giống nhau liên tiếp thành một ký tự, thu được CABDAEF.
3. Chuỗi hợp lệ khi và chỉ khi độ dài của chuỗi đã rút gọn bằng kích thước tập chữ cái.

Nếu ít nhất một hoán vị thỏa điều kiện độ dài, in chuỗi tương ứng; nếu không thì đáp án là IMPOSSIBLE.

Độ phức tạp là

vì có \(\mathbf{N}!\) hoán vị và việc kiểm tra chuỗi cuối cần thời gian tuyến tính theo tổng độ dài các chuỗi đầu vào.

Test Set 2

Trong Test Set này, \(\mathbf{N}\) có thể bằng \(100\), nên không thể liệt kê \(\mathbf{N}!\) hoán vị.

Trước tiên kiểm tra riêng từng chuỗi \(\mathbf{S}_i\) có thỏa điều kiện của đề hay không bằng phương pháp ở phần trên. Nếu một chuỗi đầu vào thất bại, mọi hoán vị chứa nó cũng thất bại, nên in IMPOSSIBLE.

Gọi chữ ở giữa là mọi chữ không thuộc đoạn liên tiếp đầu tiên hay đoạn liên tiếp cuối cùng của một chuỗi. Nếu \(\mathbf{S}_i\) có hơn hai chữ cái phân biệt thì:

• Nếu một chữ là chữ ở giữa trong nhiều hơn một chuỗi đầu vào, các lần xuất hiện ấy không thể nằm cùng nhau trong chuỗi cuối bất kể thứ tự nối. Trường hợp này là bất khả thi.
• Nếu các chữ ở giữa chỉ tồn tại trong một chuỗi đầu vào, chúng không ảnh hưởng đến cách nối vì các lần xuất hiện của chúng luôn nằm cùng nhau bất kể thứ tự. Khi xét quan hệ nối, có thể coi chuỗi đó chỉ còn hai chữ, bỏ mọi thứ ngoài chữ đầu và chữ cuối; khi dựng đáp án vẫn giữ nguyên nội dung chuỗi gốc.

Vì vậy, với mỗi chữ ở giữa, đếm số chuỗi mà nó xuất hiện. Nếu bất kỳ số đếm nào lớn hơn \(1\), in IMPOSSIBLE.

Ta cũng đã kiểm tra riêng từng chuỗi, nên biết rằng trong mỗi \(\mathbf{S}_i\), mỗi chữ chỉ xuất hiện trong đúng một đoạn.

Sau bước trên, về mặt quan hệ giữa hai đầu, các chuỗi chỉ còn hai dạng:

• \(X\): chuỗi chỉ gồm một đoạn chữ \(X\).
• \(XY\): chuỗi bắt đầu bằng một đoạn chữ \(X\) và kết thúc bằng một đoạn chữ \(Y\).

Nếu có hai chuỗi dạng \(X\) với cùng chữ, có thể nối chúng ngay vì trong đáp án cuối chúng không thể bị ngăn cách bởi chuỗi khác. Nếu có hai chuỗi \(X_1Y_1\) và \(X_2Y_2\), trường hợp \(X_1=X_2\) hoặc \(Y_1=Y_2\) là IMPOSSIBLE: ở mọi thứ tự sẽ có ít nhất một đoạn chữ khác chen giữa những lần xuất hiện cần liền nhau.

Với mỗi chữ \(X\), tạo các ánh xạ:

• Nếu \(\mathbf{S}_i\) có dạng \(X\), lưu \(\mathbf{S}_i\) vào \(\operatorname{single}[X]\); nhiều chuỗi thuần cùng chữ có thể được ghép thành một khối duy nhất.
• Nếu \(\mathbf{S}_i\) có dạng \(XY\), lưu \(\mathbf{S}_i\) làm chuỗi duy nhất trong \(\operatorname{starts}[X]\) và trong \(\operatorname{ends}[Y]\).

Mỗi chữ chỉ được có nhiều nhất một chuỗi không thuần bắt đầu tại nó và nhiều nhất một chuỗi không thuần kết thúc tại nó. Nếu vị trí tương ứng đã có chuỗi khác, trả về IMPOSSIBLE.

Chuỗi bắt đầu

Gọi chuỗi bắt đầu là một chuỗi đầu vào không bị chuỗi nào trước nó ép vị trí trong đáp án cuối. Khi nào \(\mathbf{S}_i\) có thể là chuỗi bắt đầu?

• Nếu \(\mathbf{S}_i\) thuộc một khối thuần \(X\), không được có chuỗi không thuần nào kết thúc bằng \(X\); nếu có, khối thuần này phải nối ngay sau chuỗi đó chứ không thể bắt đầu một thành phần mới.
• Nếu \(\mathbf{S}_i\) có dạng \(XY\), nó là chuỗi đi ra duy nhất từ \(X\), đồng thời không có chuỗi nào kết thúc bằng \(X\) và không còn khối thuần \(X\) phải đặt trước nó.

Từ hai điều kiện này, lập tập ứng viên \(C\) gồm mọi chuỗi có thể bắt đầu một thành phần.

Mở rộng khối

Giả sử đã xây được đáp án bộ phận \(A\) kết thúc bằng chữ \(c\). Nếu tồn tại khối tại \(\operatorname{single}[c]\), đây là cơ hội cuối cùng để nối nó; nếu không, nó sẽ bị ít nhất một đoạn chữ khác ngăn cách. Tương tự, nếu tồn tại chuỗi tại \(\operatorname{starts}[c]\), ta cũng phải nối nó ngay vì cùng lý do.

Chọn chuỗi bắt đầu nào?

Khi bắt đầu một thành phần mới, có thể chọn tùy ý một phần tử trong tập ứng viên.

Chứng minh. Giả sử ta chọn \(\mathbf{S}_i\) làm chuỗi bắt đầu nhưng một lời giải tối ưu bắt đầu thành phần bằng \(\mathbf{S}_j\). Xét lời giải tối ưu sau khi đổi chỗ hai thành phần này.

Gọi chữ đầu của \(\mathbf{S}_i\) là \(a\) và của \(\mathbf{S}_j\) là \(b\). Dạng trước và sau khi đổi là:

• Tối ưu: \(|b\ldots X|a\ldots Y|\).
• Tối ưu sau khi đổi: \(|a\ldots Y|b\ldots X|\).

Sau phép đổi:

• Với các chữ ở giữa hai thành phần: mọi chữ giữa \(b\) và \(a\) vốn không thể xuất hiện sau \(a\), và mọi chữ sau \(a\) vốn không thể xuất hiện trước \(a\). Vì vậy chúng vẫn hợp lệ sau khi đổi.
• Với chữ \(b\): lời giải tối ưu ban đầu không thể có chữ \(b\) nào sau \(a\), nên phép đổi không phá tính liên tiếp của \(b\).
• Với chữ \(a\): vì \(\mathbf{S}_i\) thuộc tập ứng viên, hoặc không có chuỗi nào kết thúc bằng \(a\), hoặc \(\mathbf{S}_i\) là phần duy nhất có thể kết thúc tại \(a\). Do đó thành phần \(X\) không thể kết thúc bằng \(a\), và phép đổi vẫn đúng.

Vậy một ứng viên tùy ý đều có thể được chọn.

Thuật toán cuối cùng

Lặp các bước sau:

1. Chọn một chuỗi tùy ý từ tập ứng viên và bắt đầu một thành phần bằng nó.
2. Gọi \(e\) là chữ cuối của thành phần hiện tại. Nếu có khối thuần \(\operatorname{single}[e]\), nối toàn bộ khối ấy. Nếu \(\operatorname{starts}[e]\) khác rỗng, nối chuỗi đó rồi lặp lại bước 2 với chữ cuối mới. Nếu không, quay lại bước 1 để bắt đầu thành phần khác.
3. Nếu đã dùng hết mọi chuỗi, in đáp án. Nếu không còn ứng viên nhưng vẫn còn chuỗi chưa dùng — chẳng hạn các chuỗi tạo thành chu trình — in IMPOSSIBLE.

Mỗi ứng viên chỉ được chạm tới một lần sau phần tiền xử lý; việc quét và kiểm tra nội dung các chuỗi cần thời gian theo tổng độ dài. Bản phân tích chính thức nêu độ phức tạp

Google Code Jam khuyến nghị luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1C.