Phân tích

Test Set 1

Dựng đồ thị có các đỉnh là số và các cạnh là hai thao tác. Bài toán là đường đi ngắn nhất từ \(S\) đến \(E\). Đồ thị vô hạn nhưng chỉ cần xét một tập đỉnh hữu hạn.

Trên biểu diễn nhị phân, Double là “nối một số \(0\) ở cuối”. Không bao giờ tối ưu khi nối nhiều số \(0\) hơn số bit của \(E\), vì NOT chỉ có thể xóa chữ số ở đầu; mọi số \(0\) dư cuối cùng vẫn phải bị xóa. Do đó giới hạn độ dài tối đa bằng \(|S|+|E|\), rồi dùng BFS để tìm đường đi ngắn nhất.

Test Set 2

Gọi nhóm bit là một đoạn dài cực đại gồm toàn số \(0\) hoặc toàn số \(1\). Giả sử \(S\) có \(K\) nhóm, \(E\) có \(L\) nhóm.

Double nối một bit ở phải; NOT bù bit và có thể xóa bit ở trái. Vì vậy kết quả của chuỗi thao tác gồm một hậu tố có thể rỗng của \(S\) (có thể đã bị bù) và một số bit mới do Double tạo. Gọi bit bắt nguồn từ \(S\) là bit tái sử dụng.

Trước hết xét trường hợp không tái sử dụng bit nào. Ta dựng \(E\) chỉ từ các bit \(0\) được thêm bởi Double, dùng NOT mỗi khi cần bắt đầu nhóm bit mới, đồng thời dùng thêm NOT để loại toàn bộ bit gốc của \(S\). Nếu thu được \(E\), số thao tác đó là một ứng viên.

Ví dụ, từ \(101_2\) tới \(11100_2\):

Dấu cách tách bit gốc của \(S\) với bit do Double thêm. Nếu \(S\) kết thúc bằng \(0\), cần thêm một NOT ở đầu để Double đầu tiên tạo nhóm bit hoàn toàn mới. Sau khi xóa hết bit gốc, có thể cần thêm một NOT nếu phần còn lại là bù của \(E\).

Bây giờ thử tái sử dụng một số bit. Mỗi NOT xóa một nhóm bit ở đầu biểu diễn rồi bù phần còn lại. Không bao giờ tối ưu khi dùng NOT quá \(K+1\) lần: nếu vậy ta hoặc lặp giữa \(0\) và \(1\), hoặc xóa những bit vừa thêm bằng Double — các bit vô ích đó lẽ ra không cần thêm.

Giả sử đáp án dùng đúng \(X\) lần NOT. Áp dụng \(X\) NOT lên \(S\) để được \(S'\). Nếu \(S'\) không là tiền tố của \(E\), trường hợp này bất khả thi vì Double không thay đổi tiền tố.

Nếu \(S'\) là tiền tố của \(E\), cần đúng \(Y=|E|-|S'|\) lần Double để dựng hậu tố. Giả sử hậu tố cần dựng có \(M\) nhóm bit; ta còn cần \(M\) hoặc \(M+1\) lần NOT tùy chẵn lẻ của \(M\) và bit đầu tiền tố; gọi số đó là \(Z\). Nếu \(Z>X\), trường hợp không hợp lệ. Nếu \(Z\le X\), đáp án ứng viên là \(X+Y\): các NOT dư so với \(Z\) có thể thực hiện trước khi thêm bit mới và không ảnh hưởng hậu tố.

Duyệt \(X\) từ \(0\) đến \(K+1\), lấy nhỏ nhất giữa các trường hợp này và trường hợp không tái sử dụng. Nếu không trường hợp nào hợp lệ, in IMPOSSIBLE.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1C, bài Double or NOTing.