Phân tích

Test Set 1

Trong Test Set 1, bức tranh đủ ngắn để thử mọi cách hoàn thiện. Gọi \(\ell\) là độ dài của \(S\). Ta có thể xét từng xâu độ dài \(\ell\) chỉ gồm C và J, rồi kiểm tra xem nó có khớp với \(S\) tại các vị trí không phải ? hay không; hoặc vét cạn trực tiếp các vị trí ?.

Với mỗi cách hoàn thiện hợp lệ, ta tính tổng chi phí của Cody-Jamal và duy trì giá trị nhỏ nhất để xuất ra cuối cùng. Ta xét nhiều nhất \(2^\ell\) bức tranh hoàn chỉnh, và mỗi bức chỉ cần thêm một lượt duyệt tuyến tính để tính điểm, nên thuật toán chạy trong \(O(2^\ell\ell)\), đủ nhanh cho Test Set 1.

Test Set 2

Trong Test Set 2, \(\ell\) có thể tới \(1000\), nên thuật toán mũ không còn phù hợp. Tuy nhiên, một nhận xét đơn giản cho ta thuật toán nhanh hơn nhiều: vì \(X>0\) và \(Y>0\), ta muốn tránh chèn CJ hoặc JC vào xâu.

Nếu tất cả chữ cái bao quanh một đoạn liên tiếp gồm các dấu ? đều là cùng một chữ \(a\), thì thay toàn bộ các dấu ? đó bằng \(a\) không tạo thêm CJ hay JC. Ngược lại, nếu đoạn đó được bao bởi \(a\) ở bên trái và \(b\) ở bên phải với \(a\ne b\), thì ở đâu đó bắt buộc phải có một lần chuyển từ \(a\) sang \(b\), tức một lần xuất hiện \(ab\). Thay toàn bộ ? bằng \(a\) (hoặc bằng \(b\)) bảo đảm ta chỉ tạo đúng lần xuất hiện bắt buộc đó và không tạo gì thêm.

Nhận xét này dẫn đến một thuật toán tham lam có thể cài đặt theo nhiều cách, trong đó có cách chạy \(O(\ell)\). Chi phí của xâu kết quả cũng chính là chi phí của xâu thu được khi xóa các dấu ? thay vì thay chúng, dẫn đến cài đặt một dòng:

S.replace('?', '').count('CJ') * X + S.replace('?', '').count('JC') * Y

Thử thách thêm: Test Set 3

Lời giải Test Set 2 giả sử giảm số lần xuất hiện CJ và/hoặc JC luôn là tốt nhất; điều đó chỉ đúng khi \(X\) và \(Y\) không âm. Vì vậy Test Set 3 cần một lời giải hoàn toàn khác, sử dụng một kỹ thuật thường không xuất hiện ở bài thứ hai của Vòng loại: quy hoạch động.

Ta có thể lấy hàm \(f(s)\) cần tính và định nghĩa đệ quy như sau:

• \(f(\mathtt{?}s)=\min(f(\mathtt C s),f(\mathtt J s))\);
• \(f(a\mathtt{?}s)=\min(f(a\mathtt C s),f(a\mathtt J s))\) với \(a\in\{\mathtt C,\mathtt J\}\);
• \(f(aas)=f(as)\) với \(a\in\{\mathtt C,\mathtt J\}\);
• \(f(\mathtt{CJ}s)=X+f(\mathtt J s)\);
• \(f(\mathtt{JC}s)=Y+f(\mathtt C s)\);
• \(f(s)=0\) nếu \(|s|\le1\).

Có thể kiểm tra rằng các trường hợp trên tạo thành một phân hoạch và định nghĩa đệ quy đầy đủ. Ta có một số trường hợp hằng số; mỗi trường hợp được tính trong thời gian hằng số nếu không kể các lời gọi đệ quy. Vì thế độ phức tạp là \(O(D)\), với \(D\) là kích thước miền của hàm.

Mọi giá trị \(f\) từng cần để tính \(f(S)\) đều có thể được biểu diễn bởi một hậu tố của xâu đầu vào \(S\) cùng nhiều nhất hai ký tự bổ sung ở đầu. Do đó \(D\) tuyến tính theo \(|S|\), và độ phức tạp thời gian của thuật toán cũng vậy.

Để đạt đúng độ phức tạp nói trên, mỗi phần tử miền phải được biểu diễn trong không gian hằng số, chẳng hạn biểu diễn hậu tố của \(S\) chỉ bằng độ dài hoặc một chỉ số trong \(S\). Tuy nhiên, với giới hạn nhỏ của bài này, ngay cả cách biểu diễn lớn hơn bằng việc sao chép toàn bộ hậu tố vẫn đủ nhanh.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng loại, bài Moons and Umbrellas.