Phân tích

Vì mỗi thao tác thay mọi lần xuất hiện của một ký tự và cuối cùng chỉ đếm ký tự phân biệt, ta có thể xem S như một tập: bỏ qua các lần lặp và thứ tự. Viết \(x \to y\) cho phép thay \(x\) bằng \(y\). Trong phân tích, chữ thường và chữ hoa chỉ là tên biến, không phải ký tự cụ thể trong đầu vào.

Dựng đồ thị có hướng \(G\): mỗi đỉnh là một ký tự, có cạnh \(x \to y\) khi và chỉ khi phép đó có trong đầu vào. Mỗi thành phần liên thông yếu là một bài toán độc lập; kết quả chung là tổng kết quả các thành phần. Ký tự \(c\) không xuất hiện trong phép thay nào tạo thành phần một đỉnh, đóng góp 1 nếu \(c \in S\), ngược lại là 0.

Gọi độ đa dạng là số ký tự phân biệt, và \(U\) là tập ký tự hiện có. Nếu \(x,y \in U\), phép \(x \to y\) làm độ đa dạng giảm 1. Nếu ít nhất một trong hai vắng mặt, độ đa dạng không đổi. Vì vậy ta tối thiểu hóa lượng mất mát, rồi lấy độ đa dạng ban đầu trừ đi lượng đó.

Test Set 1

Bậc vào mỗi đỉnh không quá 1. Thành phần có đỉnh bậc vào 0 là cây có hướng, đỉnh đó là gốc. Nếu mọi đỉnh có bậc vào 1 thì có một chu trình (lần ngược cạnh từ đỉnh bất kỳ đến khi gặp lại một đỉnh). Mỗi đỉnh chu trình chỉ nhận cạnh vào từ chu trình nhưng có thể trỏ ra ngoài, nên có thể là gốc một cây. Đây là các thành phần của giả rừng.

Xét đường \(c_1 \to c_2 \to \cdots \to c_k\). Nếu \(c_{k-1},c_k \in S\), cạnh cuối buộc mất 1 vì không cạnh nào khác làm một trong hai biến mất trước lần đầu dùng nó. Sau \(c_{i-1}\to c_i\), có thể lập tức làm \(c_{i-2}\to c_{i-1}\) miễn phí vì \(c_{i-1}\) vừa vắng. Do đó xử lý các cạnh theo thứ tự ngược là tối ưu.

Mở rộng sang cây: xét lá \(y\) xa gốc nhất và cạnh \(x\to y\). Các phép khác có thể xóa \(x\) trước để cứu cạnh này, nhưng vì \(y\) xa nhất, mọi phép có ích cũng dẫn đến lá. Nếu \(x\) và đích của mọi cạnh ra từ \(x\) đều thuộc S, mất mát là không tránh được; chỉ cạnh đầu gây mất, các cạnh còn lại làm khi \(x\) đã vắng. Tổng quát, có thể "đẩy" \(x\) xuống miễn phí nếu có hậu duệ \(y\) đang vắng, bằng cách xử lý đường \(x\) tới \(y\) như trên.

Mọi cạnh không đi vào lá vì thế có thể dùng miễn phí. Dù ban đầu mọi hậu duệ của \(x\) đều có mặt, ta xử lý trước một lá không thể cứu để tạo khoảng trống. Cạnh đi vào lá cũng có thể cứu nếu nguồn còn hậu duệ khác. Xử lý đỉnh theo thứ tự tô-pô ngược: nếu \(x\) có hậu duệ vắng, đẩy \(x\) xuống rồi làm miễn phí mọi cạnh ra; nếu cả cây con đang hiện diện, cạnh ra đầu tiên mất 1 (chọn cạnh nào cũng được), và mất mát đó không thể tránh.

Với chu trình đơn, nếu có \(x\notin S\), làm \(y\to x\), rồi \(z\to y\), v.v.; các ký tự chỉ dịch chuyển và độ đa dạng giữ nguyên. Nếu mọi ký tự chu trình thuộc S, phép đầu tiên buộc mất 1, sau đó dùng ký tự vừa biến mất làm khoảng trống.

Nếu có cây treo trên chu trình, xử lý độc lập các cây trước. Mỗi cây sau đó có một ký tự vắng, vốn vắng từ đầu hoặc được tạo ra khi xử lý. Đẩy gốc một cây (cũng là đỉnh chu trình) xuống miễn phí để tạo ký tự vắng trên chu trình, rồi xử lý chu trình miễn phí.

Test Set 2

\(G\) giờ có thể tùy ý, nên không thể phân loại thành phần, nhưng vẫn dùng ý tưởng đường đi và đẩy ký tự. Ta biến bài toán sắp thứ tự dùng mỗi cạnh ít nhất một lần, với số bước mất mát nhỏ nhất, thành các bài toán tương đương.

Sau \(x\to y\), có thể chèn ngay mọi \(x\to z\) khác mà không mất thêm. Do đó chỉ cần dùng ít nhất một cạnh ra của mỗi đỉnh có bậc ra dương; các cạnh còn lại chèn vào mà không đổi kết quả. Cạnh có \(x\notin S\) có thể làm từ đầu mà không tác động. Ta chỉ bỏ yêu cầu dùng cạnh cụ thể, không cấm dùng nó, nên bài toán nới lỏng chỉ yêu cầu dùng mọi đỉnh bậc ra dương có ký tự thuộc S.

Với danh sách đường \(L\), định nghĩa trọng số bằng số đường trừ số ký tự \(c\notin S\) có ít nhất một đường kết thúc ở \(c\): với mỗi \(c\) như vậy, một đường kết thúc ở \(c\) là miễn phí. \(L\) phủ \(G\) nếu mọi đỉnh cần dùng xuất hiện ở vị trí không cuối của một đường, tức ít nhất một cạnh ra của nó được dùng. Trọng số phủ nhỏ nhất bằng số bước mất độ đa dạng nhỏ nhất của bài toán nới lỏng.

Ta chứng minh hai chiều: lịch mất \(D\) cho phủ trọng số không quá \(D\), và phủ trọng số \(D\) cho lịch mất không quá \(D\).

Từ lịch tới phủ

Cho lịch \(r_1,\ldots,r_n\) có \(D\) bước mất mát. Khởi tạo \(L\) rỗng. Với \(r_i=x\to y\):

1. Nếu văn bản không đổi, không đổi \(L\).
2. Nếu có đường bắt đầu bằng \(y\), thêm \(x\) vào đầu nó.
3. Nếu không, thêm \(r_i\) làm đường mới.

Lần đầu dùng cạnh ra của đỉnh \(x\) cần phủ không thể thuộc trường hợp 1: các ký tự \(x\) ban đầu chưa bị thay, nên văn bản phải đổi. Trường hợp 2 và 3 đặt \(x\) ở vị trí không cuối; về sau chỉ thêm vào đầu nên nó vẫn không cuối. Vậy \(L\) là phủ.

Giả sử \(r_i=x\to y\) thuộc trường hợp 3 và làm tăng trọng số. Vì văn bản đổi nên \(x\) đang có. Không có đường bắt đầu ở \(y\), nên mỗi phép trước đó \(y\to z\) từng xóa \(y\) phải có một phép \(w\to y\) đưa \(y\) trở lại và khiến \(y\) không còn là đầu đường chứa \(y\to z\). Vì trọng số tăng, hoặc \(y\in S\), hoặc đã có đường kết thúc bằng \(v\to y\) đưa \(y\) vào văn bản. Vậy \(y\) cũng đang có và \(r_i\) mất 1. Mỗi đơn vị trọng số ứng với một bước mất mát, nên trọng số không quá \(D\).

Từ phủ tới lịch

Cho phủ \(L\) trọng số \(D\). Cách xử lý đường ở Test Set 1 còn tạo thay đổi phụ, có thể ảnh hưởng các đường khác cùng thành phần, nên cần quy trình sau.

Với đường \(P\), xét tập hiện tại \(U\). Đỉnh nội bộ nghiêm ngặt không phải đầu hay cuối. Chia \(P\) thành \(P_1,\ldots,P_n\), cuối \(P_i\) là đầu \(P_{i+1}\) và các cạnh tạo thành một phân hoạch. Chọn điểm chia sao cho đỉnh nội bộ nghiêm ngặt của \(P\) cũng nội bộ nghiêm ngặt trong đường con chứa nó khi và chỉ khi ký tự đó thuộc \(U\). Xử lý \(P_n,P_{n-1},\ldots,P_1\); trong mỗi đường con, làm cạnh theo chiều đường, khác Test Set 1.

Các ký tự trung gian của đường con không thuộc \(U\), nên đường con từ \(x\) tới \(y\) có hiệu ứng ròng là thay \(x\) bằng \(y\). Với \(P_1\), nếu \(x\notin U\) thì không có hiệu ứng. Sau \(P_{i+1}\) bắt đầu tại \(x_{i+1}\), \(x_{i+1}\) vắng; sau \(P_i\), \(x_i\) vắng và \(x_{i+1}\) được khôi phục. Toàn bộ \(P\) vì thế chỉ thay ký tự đầu tiên trên đường đang thuộc \(U\) bằng ký tự cuối, không đổi ký tự nào khác.

Chọn \(L'\) gồm đúng một đường kết thúc ở mỗi \(c\notin S\) có đường như vậy. Khi đó \(L\setminus L'\) có đúng \(D\) đường. Xử lý \(L'\) trước: mỗi đường đưa vào một ký tự mới ngoài S, luôn khác các ký tự đã đưa vào, nên không mất đa dạng. Mỗi đường còn lại có hiệu ứng một phép thay, mất nhiều nhất 1. Tổng mất không quá \(D\).

Thành phần liên thông mạnh và ghép cặp

Nếu đường chạm đỉnh \(x\) có ký tự thuộc S, thay lần xuất hiện đó bằng chu trình bắt đầu và kết thúc tại \(x\), thăm toàn bộ thành phần liên thông mạnh của \(x\), mà không đổi trọng số. Do đó trong mỗi thành phần chỉ cần phủ một đỉnh bậc ra dương có ký tự thuộc S.

Chuyển thành ghép cặp cực đại hai phía như phủ đường đi trên DAG. Gọi \(C\) là tập thành phần liên thông mạnh cần phủ, và \(D\) gồm bản sao của \(C\) cùng mọi đỉnh còn lại có ký tự ngoài S. Ghép \(c\in C\) với \(d\in D\) nếu có đường đi không rỗng từ \(c\) tới \(d\); không ghép một thành phần với chính nó. Ghép biểu diễn quan hệ "tiếp theo", phần tử chưa ghép là điểm kết thúc.

Gọi \(f(c)\) ánh xạ \(c\in C\) tới bản sao cùng thành phần trong \(D\). Từ ghép \(M\), tạo phủ có trọng số đúng bằng số phần tử chưa ghép của \(C\): mỗi phần tử như vậy tạo đường có tính trọng số, phần tử \(D\setminus C\) tạo đường miễn phí.

Với mỗi \(c\in C\) chưa ghép, tạo đường chứa \(c\), rồi nối về trái lần lượt \(M(f(c))\), \(M(f(M(f(c))))\), v.v. Làm tương tự cho mỗi phần tử đã ghép thuộc \(D\setminus C\), tức ký tự ngoài S. Các đường chạm mọi phần tử \(C\); điểm cuối là phần tử chưa ghép của \(C\) hoặc ký tự ngoài S. Nếu có đường một đỉnh, nó vẫn bị tính trọng số, nên nối thêm cạnh ra bất kỳ để đường không rỗng mà không tăng trọng số.

Vì vậy, số phần tử \(C\) chưa ghép trong ghép cực đại, tính được bằng cách điều chỉnh thuật toán luồng cực đại như Ford–Fulkerson, chính là trọng số phủ nhỏ nhất.

Dựng đồ thị tuyến tính theo đầu vào. Thành phần liên thông mạnh và bao đóng bắc cầu để dựng quan hệ ghép tốn \(O(A^2)\) theo kích thước bảng chữ cái \(A\); bản thân quan hệ có thể có \(O(A^2)\) phần tử. Ghép cực đại tốn \(O(A^3)\) vì có tối đa \(A\) đường tăng, mỗi đường quét \(O(A^2)\) quan hệ. Tổng thể \(O(A^3)\), đủ nhanh. Có thể dùng phương pháp đơn giản hơn nhưng về kỹ thuật chậm hơn, như Floyd–Warshall, cho thành phần liên thông mạnh và bao đóng bắc cầu mà không đổi độ phức tạp tổng thể.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2020, Virtual World Finals.