Để dễ theo dõi, phân tích gốc trình bày các chuỗi \(B,G\) và đầu ra bằng phông đơn cách, lệnh chương trình thứ nhất bằng chữ thường, còn lệnh chương trình thứ hai có gạch chân.

Trước hết xét khi nào bài vô nghiệm. Nếu \(B\in G\) thì hiển nhiên không thể, như một ví dụ mẫu. Điều bất ngờ là nếu \(B\notin G\) thì bài luôn có lời giải.

Ta sẽ chứng minh bằng cách dựng hai chương trình có thể sinh mọi chuỗi độ dài \(L\) trừ \(B\). Điều này nghe còn khó hơn chỉ sinh các chuỗi trong \(G\), nhưng đôi khi tăng yêu cầu lại làm lộ ra ý tưởng; trong bài này, tập \(G\) thực chất chỉ là dữ kiện đánh lạc hướng.

Chương trình thứ nhất

Từ \(B\), dựng chương trình đầu như sau:

1. Đảo từng ký tự của \(B\): 0 thành 1, 1 thành 0.
2. Thêm một lệnh ? sau mỗi lệnh 0 hoặc 1.

Nếu \(B=\) 111, chương trình là 0?0?0?. Nếu \(B=\) 010, chỉ có thể xuất hiện ở Large, chương trình là 1?0?1?.

Theo mặc định, chương trình in chuỗi đối của \(B\). Muốn tạo chuỗi khác, chương trình thứ hai phải ghi đè một hay nhiều dấu ?: ngay trước ? của chương trình đầu, xen một lệnh đổi thanh ghi. Chẳng hạn với 1?0?1?, dùng chương trình thứ hai 01 và xen thành 1<u>0</u>?0<u>1</u>?1? có thể in 011 thay vì 101. Muốn in chính \(B\), ta phải ghi đè cả ba dấu ?.

Do đó, ta cần chương trình thứ hai không thể ghi đè toàn bộ các dấu hỏi. Cách dựng cho Small và Large khác nhau.

Chương trình thứ hai cho Small

Trong Small, \(B\) luôn chỉ gồm 1, nên chương trình đầu là 0? lặp \(L\) lần. Với \(B=\) 111, nó là 0?0?0?.

Chương trình thứ hai cần ghi đè được hai dấu ? bất kỳ để có thể in mọi chuỗi có nhiều nhất hai số 1, nhưng không được ghi đè cả ba vì khi đó có thể in \(B\). Tổng quát, chỉ cần dùng 1 lặp \(L-1\) lần, không phải \(L\) lần. Với \(B=\) 111, chương trình thứ hai là 11.

Chương trình thứ hai cho Large

Với \(B\) bất kỳ, cần một chương trình mà khi coi là chuỗi, nó chứa mọi chuỗi độ dài \(L-1\) làm dãy con — các ký tự giữ thứ tự nhưng không cần kề nhau — để sinh mọi đầu ra khác \(B\), nhưng không chứa \(B\) làm dãy con.

Khi ghép chương trình này với chương trình đầu, ta có thể ghi đè tối đa \(L-1\) dấu hỏi theo mọi mẫu vì mọi dãy con độ dài \(L-1\) đều có mặt. Nhưng không thể ghi đè cả \(L\) vị trí để tạo \(B\), vì \(B\) không phải dãy con của chương trình thứ hai.

Có nhiều cách dựng; cách sau không ngắn nhất nhưng dễ giải thích:

1. Sao chép \(B\) nhưng bỏ ký tự cuối.
2. Thay mỗi 0 bằng 10, mỗi 1 bằng 01.

Ví dụ, với \(B=\) 010, chương trình thứ hai là 1001: 0 đầu thành 10, 1 thành 01, còn ký tự cuối của \(B\) bị bỏ.

Ta kiểm tra hai yêu cầu. Chia chương trình thứ hai thành \(L-1\) cặp lệnh kề nhau. Mỗi cặp chứa một 0 và một 1, nên bằng cách chọn một ký tự từ mỗi cặp, ta thu được mọi dãy con nhị phân độ dài \(L-1\).

Ngược lại, thử tìm \(B=\) 010 trong 1001. Số 0 đầu tiên sớm nhất ở vị trí 2; số 1 tiếp theo sớm nhất ở vị trí 4. Tổng quát, do cách dựng, mỗi khi tham lam tìm ký tự kế tiếp của \(B\), ta phải đi qua hai ký tự của chương trình. Chương trình chỉ dài \(2L-2\), nên không đủ để tìm trọn \(B\) dài \(L\). Vì thế chương trình thứ hai hợp lệ.

Chương trình đầu dài \(2L\), chương trình sau dài \(2L-2\), tổng \(4L-2\le198\), đáp ứng giới hạn 200 và có đúng \(L\) dấu ?. Việc dựng tốn \(O(L)\) thời gian.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 3.