Test Set 1

Trong Test Set 1, chuỗi chỉ có \(10\) vị trí. Ta có thể truy vấn từng vị trí rồi gửi toàn bộ chuỗi mà không cần lo về dao động lượng tử nào, vì dao động tiếp theo chỉ xảy ra nếu ta gửi truy vấn thứ \(11\).

Test Set 2

Sau đây là một trong nhiều cách giải Test Set 2. Trước tiên, ta truy vấn mười vị trí đầu tiên của chuỗi thật, rồi tạo một tập khả năng gồm toàn bộ \(1024\) chuỗi dài \(20\) ký tự có tiền tố là \(10\) ký tự vừa biết. Tiếp đó, ta cập nhật tập khả năng để nó chứa mọi chuỗi có thể sinh ra từ các chuỗi ấy sau lần dao động lượng tử kế tiếp. Đáp án đúng nằm đâu đó trong tập này; bây giờ ta cần thu hẹp tập!

Trước mỗi truy vấn tiếp theo, ta tìm vị trí trong chuỗi (từ \(1\) đến \(20\)) mà tại đó tỉ lệ ký tự 0 và 1 trong các chuỗi thuộc tập khả năng gần cân bằng nhất. Sau đó, ta truy vấn chuỗi thật tại vị trí ấy và loại khỏi tập khả năng mọi chuỗi không phù hợp với thông tin vừa nhận. Mỗi khi thật sự tìm được một vị trí có tỉ lệ cân bằng, ta chắc chắn giảm một nửa kích thước tập; nhưng nếu không có vị trí như vậy, ta có thể không loại được nhiều khả năng đến thế. Ta tiếp tục theo cách này, đồng thời nhớ mở rộng tập khả năng sau mỗi lần dao động lượng tử, cho đến khi chỉ còn đúng một khả năng; đó buộc phải là đáp án.

Không dễ chứng minh chiến lược này chắc chắn hội tụ về một đáp án. Về trực giác, mỗi dao động lượng tử làm kích thước tập khả năng tăng nhiều nhất \(4\) lần; ngay cả khi bằng cách nào đó mỗi lần lọc chỉ loại được \(20\%\) số phần tử, mức giảm ấy vẫn dễ dàng thắng mức tăng theo hệ số \(4\) và giúp ta tiến triển đủ để hoàn thành trong \(150\) truy vấn. Hơn nữa, các chuỗi trong tập khả năng không thể vừa đôi một khác nhau, vừa giống nhau đến thế tại mọi vị trí riêng lẻ (hãy nhớ rằng ta luôn chọn vị trí hữu ích nhất trong trường hợp xấu nhất). Ngoài ra, Test Set 2 là tập hiển thị kết quả, nên ta cũng có thể cứ gửi lời giải và xem kết quả.

Test Set 3

Chiến lược trên không dùng được cho chuỗi dài \(100\) ký tự vì tập khả năng sẽ lớn đến mức khủng khiếp. May thay, có một cách tiếp cận đơn giản hơn nhiều.

Giả sử ta tìm được hai vị trí cách đều tâm chuỗi và có cùng giá trị. Ta có thể dùng chúng để phát hiện một dao động lượng tử có bao gồm phép bù bit hay không (bất kể có kèm đảo ngược thứ tự). Ví dụ, giả sử ngay trước một dao động lượng tử, hai đầu chuỗi đều là 0. Sau dao động, ta kiểm tra vị trí đầu tiên. Nếu nó là 1 thì phép bù bit đã xảy ra; nếu không thì phép bù bit không xảy ra. Kết luận này đúng bất kể dao động đó có bao gồm phép đảo ngược thứ tự hay không.

Bây giờ, giả sử ta tiếp tục kiểm tra từng cặp vị trí theo cách này và mỗi lần tiến vào trong một bước. Sau mỗi dao động lượng tử, ta phải dành một truy vấn để kiểm tra phép bù bit, nhờ đó có thể cập nhật những gì đã biết về chuỗi nếu phép bù bit thực sự xảy ra. Nếu mọi cặp đều là cặp giống nhau như cặp đầu tiên, ta vốn không cần quan tâm đến phép đảo ngược thứ tự (vì chuỗi là một palindrome), và bài toán đã xong.

Nhưng nếu trong quá trình đó ta tìm thấy một cặp khác nhau thì sao? Những cặp như vậy cũng hữu ích theo cách riêng! Nếu sau một dao động lượng tử, ta truy vấn vị trí đầu của một cặp khác nhau và thấy bit đó đã đổi, ta biết rằng hoặc phép bù bit, hoặc phép đảo ngược thứ tự đã xảy ra, nhưng không phải cả hai.

Khi đã có một cặp khác nhau như vậy, ta có thể dùng nó cùng với cặp giống nhau, dành \(2\) trong mỗi \(10\) truy vấn để biết chính xác điều gì xảy ra trong mỗi dao động lượng tử. Ví dụ, nếu vị trí đầu của cặp giống nhau không đổi nhưng vị trí đầu của cặp khác nhau lại đổi, ta biết dao động lượng tử có đảo ngược thứ tự nhưng không bù bit.

Trong phân tích trên, ta giả sử sẽ gặp một cặp giống nhau trước. Tuy nhiên, nếu cặp đầu tiên là cặp khác nhau, ta có thể tiếp tục cho đến khi gặp một cặp giống nhau. Nếu không bao giờ gặp cặp giống nhau, ta không cần phân biệt phép bù bit với phép đảo ngược thứ tự, bởi hai thao tác đó tương đương đối với chính chuỗi này. Còn nếu gặp một cặp giống nhau, ta có thể tiếp tục như đã trình bày ở trên.

Trong trường hợp xấu nhất, ta cần bao nhiêu truy vấn? Ta có thể dùng cả \(10\) truy vấn đầu để thu thập dữ liệu, vì điều xảy ra trong dao động lượng tử ở đầu bài toán là không thể biết và cũng không quan trọng. Sau đó, trong mỗi nhóm \(10\) truy vấn, ta có thể phải dùng tối đa \(2\) truy vấn để xác định lại hướng và trạng thái trước khi dùng \(8\) truy vấn còn lại để thu thập dữ liệu. Vì vậy, để chắc chắn tìm được toàn bộ chuỗi, ta cần \(10\) truy vấn, cộng thêm \(11\) nhóm, mỗi nhóm \(10\) truy vấn và cho biết \(8\) vị trí (đưa tổng số vị trí đã biết lên \(98\)), rồi thêm \(2\) truy vấn để xác định lại trạng thái lần cuối và \(2\) truy vấn nữa để lấy hai vị trí cuối. Tổng cộng là \(124\) truy vấn, nhỏ hơn đáng kể giới hạn \(150\).

Về tên bài...

Năm ngoái có bài Dat Bae nói về việc các ký tự bị xóa khỏi một chuỗi trong cơ sở dữ liệu; tên bài là Data Base được biến đổi theo một cách phản ánh chủ đề. ESAb ATAd cũng tương tự, trong đó việc đổi kiểu chữ hoa/thường đóng vai trò gần giống phép bù bit. (Hãy tưởng tượng đội ngũ Code Jam đã vui đến mức nào khi lần nào cũng phải cố gõ đúng tên bài!)

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2020, Vòng loại, bài ESAb ATAd; kho Google Coding Competitions Archive (Apache-2.0).