Nhận xét ban đầu

Với một chuỗi \(\mathbf{S}\) bất kỳ, số chuỗi mới có thể thu được từ nó nhiều nhất là \(2^{|\mathbf{S}|}\), vì với mỗi ký tự trong \(\mathbf{S}\) có đúng hai lựa chọn: đánh dấu hoặc không đánh dấu.

Test Set 1

Vì độ dài của \(\mathbf{S}\) không quá \(10\), số chuỗi mới có thể thu được nhiều nhất là \(2^{10}\). Ta có thể liệt kê tất cả rồi tìm chuỗi nhỏ nhất theo thứ tự từ điển. Độ phức tạp thời gian là \(O(2^{|\mathbf{S}|}\times |\mathbf{S}|)\), bởi có tổng cộng \(2^{|\mathbf{S}|}\) chuỗi cần so sánh và độ dài mỗi chuỗi không quá \(2\times |\mathbf{S}|\).

Test Set 2

Khi độ dài của \(\mathbf{S}\) có thể lên tới \(100\), \(2^{100}\) là quá lớn để liệt kê toàn bộ.

Nhắc lại rằng một chuỗi \(p\) đứng trước một chuỗi khác \(q\) theo thứ tự bảng chữ cái nếu \(p\) là tiền tố của \(q\), hoặc nếu tại vị trí khác nhau ngoài cùng bên trái, chữ cái của \(p\) nhỏ hơn theo thứ tự từ điển.

Với mỗi ký tự \(\mathbf{S}_i\) trong \(\mathbf{S}\), ta dùng quy tắc sau để quyết định có đánh dấu nó hay không:

• Nếu ký tự khác \(\mathbf{S}_i\) tiếp theo trong chuỗi lớn hơn \(\mathbf{S}_i\) theo thứ tự từ điển — nói cách khác, tồn tại \(j\) sao cho \(\mathbf{S}_j \gt \mathbf{S}_i\) và \(\mathbf{S}_k=\mathbf{S}_i\) với mọi \(i\lt k\lt j\) — thì ta phải đánh dấu \(\mathbf{S}_i\). Khi nhân đôi \(\mathbf{S}_i\), ta đồng thời đẩy \(\mathbf{S}_j\) sang phải và đặt \(\mathbf{S}_i\) vào vị trí đó, nên chuỗi mới nhỏ hơn theo thứ tự từ điển.
• Nếu ký tự khác \(\mathbf{S}_i\) tiếp theo nhỏ hơn \(\mathbf{S}_i\) — tức tồn tại \(j\) sao cho \(\mathbf{S}_j \lt \mathbf{S}_i\) và \(\mathbf{S}_k=\mathbf{S}_i\) với mọi \(i\lt k\lt j\) — thì ta tuyệt đối không đánh dấu \(\mathbf{S}_i\). Nhân đôi nó sẽ đẩy \(\mathbf{S}_j\) sang phải và thay vị trí đó bằng \(\mathbf{S}_i\), khiến chuỗi mới lớn hơn theo thứ tự từ điển.
• Nếu không còn ký tự nào khác \(\mathbf{S}_i\) ở phía sau — tức \(i\) là chỉ số cuối cùng, hoặc \(\mathbf{S}_k=\mathbf{S}_i\) với mọi \(i\lt k\lt |\mathbf{S}|\) — thì ta không đánh dấu \(\mathbf{S}_i\). Việc nhân đôi khi ấy làm chuỗi ban đầu trở thành tiền tố của chuỗi mới, nên chuỗi mới lớn hơn theo thứ tự từ điển.

Có nhiều cách cài đặt quy tắc này. Một cách là tiền xử lý \(\mathbf{S}\) thành các nhóm ký tự giống nhau và liên tiếp. Chẳng hạn, BOOKKEEPER trở thành [(B,1), (O,2), (K,2), (E,2), (P,1), (E,1), (R,1)]. Với mỗi phần tử trong danh sách, nếu ký tự của phần tử kế tiếp lớn hơn nó theo thứ tự từ điển thì in ký tự hiện tại với số lần xuất hiện gấp đôi; ngược lại, in đúng số lần xuất hiện ban đầu.

Độ phức tạp thời gian là \(O(|\mathbf{S}|)\): ta duyệt \(\mathbf{S}\) một lần khi tiền xử lý và duyệt danh sách đã xử lý, có độ dài không quá \(|\mathbf{S}|\), một lần nữa để tạo đáp án cuối cùng.

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 1A.