Test Set nhỏ

Vét cạn đủ cho Small: thử mọi cách điền các dấu ?, chọn hiệu tuyệt đối nhỏ nhất và phá hòa lần lượt bằng tỷ số thứ nhất rồi tỷ số thứ hai. Ngay trường hợp xấu nhất ??? ??? cũng chỉ có \(10^6\), tức một triệu khả năng.

Test Set lớn

Nhiều bài Code Jam trông phức tạp nhưng có lời giải đơn giản; bài này lại ngược lại. Một chiến lược tham lam hấp dẫn rất dễ sai, nên ta chỉ tham lam khi chắc chắn an toàn.

Ta xét nhiều cách điền ?, luôn lưu cặp tỷ số tốt nhất theo đủ quy tắc phá hòa. Duyệt cặp ký tự ở vị trí đầu, rồi vị trí thứ hai, v.v.

Tại một vị trí, ta quyết định cách điền các dấu ?. Có thể làm hai chữ số bằng nhau nhờ điền phù hợp, hoặc chúng vốn là cùng một chữ số. Nếu không bao giờ gặp vị trí bắt buộc khác nhau, ta làm mọi cặp chữ số bằng nhau và đạt hiệu 0, tối ưu tuyệt đối. Ví dụ ?1? 2?? có thể thành 210 210; với cặp ? ?, chọn 0 0 để thỏa quy tắc phá hòa.

Nhưng không phải lúc nào cũng vậy. Nếu hai chuỗi có chữ số khác nhau ở một vị trí thì hiệu không thể bằng 0. Thậm chí có lúc phải chủ động tạo khác biệt trước vị trí bắt buộc khác đầu tiên: với ??0 ?99, làm bằng nhau đến vị trí khác biệt sẽ cho 090 099, trong khi 100 099 tốt hơn.

Vì vậy, nếu tồn tại hai chữ số cố định khác nhau, ta hoặc làm mọi vị trí trước chúng bằng nhau, hoặc tạo điểm khác biệt đầu tiên sớm hơn. Nói cách khác, từ trái sang phải ta làm một số (có thể là 0) cặp đầu bằng nhau, rồi gặp hoặc tạo ra điểm khác biệt đầu tiên.

Ngay khi có điểm khác biệt đầu tiên, ta biết chắc tỷ số nào lớn hơn: mọi chữ số trước đều bằng nhau, nên chữ số lớn hơn tại đây quyết định toàn bộ, bất kể các dấu ? phía sau.

Ta cũng biết chính xác cách điền phần còn lại để hiệu nhỏ nhất. Không có lý do tăng số đang lớn hơn, nên mọi ? của nó thành 0; cần tăng số nhỏ hơn nhiều nhất, nên mọi ? của nó thành 9.

Khi duyệt từ trái sang phải, tại mỗi vị trí làm như sau:

• Nếu gặp hai chữ số giống nhau, chuyển sang vị trí kế.
• Nếu gặp hai chữ số khác nhau, điền mọi ? còn lại theo quy tắc trên, so sánh cặp thu được với tốt nhất hiện tại rồi dừng.
• Nếu gặp một chữ số và một ?:
• nếu chữ số không phải 9, thử thay ? bằng chữ số đó cộng 1; đây là điểm khác biệt đầu tiên, nên điền nốt phần sau và cập nhật đáp án;
• nếu chữ số không phải 0, thử thay ? bằng chữ số đó trừ 1, điền nốt và cập nhật;
• sau đó thay ? bằng chính chữ số ấy và tiếp tục. Không cần thử mọi chữ số: nếu điều khiển được hai chữ số tại điểm khác biệt đầu, cho chúng lệch quá 1 chỉ làm hiệu lớn hơn, bất kể phần sau.
• Nếu gặp hai dấu ?:
• thử 0 1, hoàn thiện hai tỷ số và cập nhật;
• thử 1 0, hoàn thiện và cập nhật;
• sau đó đặt cả hai thành 0 rồi tiếp tục. Một lần nữa, không cần tạo độ lệch lớn hơn 1.

Cài đặt cũng phải kiểm tra trường hợp không hề có điểm khác biệt. Khi duyệt xong, cặp tốt nhất là đáp án.

Cách này còn có thể cải thiện nhưng đã giải Large rất nhanh. Nó có một lượt qua toàn chuỗi; tại mỗi vị trí có thể thực hiện tối đa hai lượt từng phần bổ sung, nên thời gian xấu nhất là \(O(N^2)\) với \(N=|C|=|J|\). Phân tích chính thức để lời giải \(O(N)\) làm bài tập cho người đọc.

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Round 1B - Close Match, kho Google Coding Competitions (Apache-2.0).