Test Set nhỏ

Các giới hạn của Test Set nhỏ gợi ý rằng ta có thể sinh mọi hệ thống cầu trượt, nhưng kỳ vọng đó vẫn quá lạc quan. Biểu diễn hệ thống bằng đồ thị có hướng \(G\): mỗi đỉnh là một tòa nhà, cạnh \(i\to j\) là cầu từ tòa nhà \(i\) tới \(j\). Cách trực tiếp nhất quyết định có hoặc không có từng cầu trong \(B(B-1)\) cầu khả dĩ, tức phải xét \(2^{B(B-1)}\) hệ thống. Ngay với \(B=6\), con số này xấp xỉ \(2^{30}\), khoảng một tỷ.

Một nhận xét giúp giảm mạnh số trường hợp: không thể có chu trình nằm trên bất kỳ đường hợp lệ nào từ 1 tới \(B\). Nếu có, ta có thể đi quanh chu trình tùy ý nhiều lần trước khi tiếp tục tới đích, tạo vô hạn đường hợp lệ. Đồ thị \(G\) vẫn có thể chứa một chu trình không nằm trên đường hợp lệ nào, nhưng xóa chu trình đó không thay đổi số đường; do đó chỉ cần xét các đồ thị hoàn toàn không có chu trình.

Vì vậy, một đường hợp lệ không thể thăm lại cùng tòa nhà và có độ dài tối đa \(B\). DFS từ đỉnh 1 tốn \(O(B)\) cho mỗi đường tìm được. Nếu tìm thấy hơn \(M\) đường, ta dừng ngay vì hệ thống hiện tại không hợp lệ. Thời gian xấu nhất để kiểm tra một hệ thống là \(O(MB)\). Ta cũng có cận nhỏ hơn cho số hệ thống cần xét: với mỗi cặp tòa nhà \(i,j\), đúng một trong ba khả năng xảy ra:

• có cầu từ \(i\) tới \(j\);
• có cầu từ \(j\) tới \(i\);
• không có cầu theo cả hai hướng.

Có \(B(B-1)/2\) cặp, nên số hệ thống không vượt quá \(3^{B(B-1)/2}\). Với \(B=6\), con số khoảng 14 triệu, đủ để kiểm tra.

Một nhận xét nữa làm Test Set nhỏ dễ hơn: đồ thị không chu trình là DAG nên có thứ tự topo. Với mọi lời giải đúng, ta có thể đánh số lại các tòa nhà ngoài 1 và \(B\) sao cho đầu cuối của mọi cầu mang số lớn hơn đầu đầu. Vì thế chỉ cần xét các cầu đi từ số nhỏ tới số lớn.

Test Set lớn

Test Set lớn cần cách hiệu quả hơn. Trước hết, số đường lớn nhất từ tòa nhà 1 tới \(B\) có thể là bao nhiêu? Một cách dựng có vẻ tạo nhiều đường là xây cầu \(i\to j\) cho mọi \(1\le i<j\le B\). Mỗi đường từ 1 tới \(B\) tương ứng duy nhất với một tập các số phân biệt trong \(\{2,\ldots,B-1\}\) — những tòa nhà trung gian được thăm. Ví dụ, với \(B=5\), tập \(\{2,4\}\) ứng với đường \(1\to2\to4\to5\), còn tập rỗng ứng với \(1\to5\). Có \(B-2\) số trung gian, mỗi số có thể được chọn hoặc không, nên có \(2^{B-2}\) tập và do đó \(2^{B-2}\) đường.

Đây thật sự là số lớn nhất. Giả sử tồn tại hệ thống có \(M>2^{B-2}\) đường. Mỗi đường ứng với một tập tòa nhà trung gian, nhưng chỉ có \(2^{B-2}\) tập, nên theo nguyên lý Dirichlet có hai đường thăm đúng cùng tập tòa nhà. Khi đó tồn tại hai tòa nhà \(i,j\) sao cho \(i\) đứng trước \(j\) trên một đường nhưng đứng sau \(j\) trên đường kia. Nếu không có cặp như vậy thì hai đường hoàn toàn giống nhau, vì không tòa nhà nào được thăm hai lần. Ta đi được từ \(i\) tới \(j\) và cũng từ \(j\) tới \(i\), tạo chu trình, mâu thuẫn. Vì thế không thể có đúng \(M>2^{B-2}\) đường.

Giờ xét \(M<2^{B-2}\). Trước hết, xây mọi cầu \(i\to j\) với \(2\le i<j\le B\). Có đúng \(2^{B-1-i}\) cách đi từ tòa nhà \(i\) tới \(B\), bởi mỗi đường tương ứng duy nhất với một tập con của \(\{i+1,\ldots,B-1\}\), gồm \(B-1-i\) phần tử. Nếu thêm cầu \(1\to i\) với \(1<i<B\), số đường từ 1 tới \(B\) tăng đúng \(2^{B-1-i}\).

Điều này cho phép dựng mạng có đúng \(M\) đường bằng biểu diễn nhị phân. Viết \(M\) ở hệ nhị phân; nếu bit thứ \(i\) tính từ phải, bắt đầu từ 1, bằng 1 thì thêm cầu từ tòa nhà 1 tới tòa nhà \(B-i\). Cạnh ấy đóng góp đúng \(2^{i-1}\) đường mới. Lặp cho mọi bit sẽ cho tổng chính xác bằng \(M\). Cách này hoạt động khi \(M\) có nhiều nhất \(B-2\) bit, tức \(M\le2^{B-2}-1\).

Giá trị lớn nhất \(M=2^{B-2}\) dùng đồ thị đầy đủ theo thứ tự tăng đã mô tả trước đó. Tương đương, lấy cấu hình cho \(2^{B-2}-1\) rồi thêm cầu trực tiếp \(1\to B\). Vậy chỉ và chỉ khi \(M\le2^{B-2}\) thì có lời giải, và phép dựng trên xử lý mọi giá trị như vậy.

Để minh họa, dưới đây là các đáp án hợp lệ cho \(B=5\) và \(M\) từ 1 đến 8:

M = 1 M = 2 M = 3 M = 4 M = 5 M = 6 M = 7 M = 8

00010 00100 00110 01000 01010 01100 01110 01111
00111 00111 00111 00111 00111 00111 00111 00111
00011 00011 00011 00011 00011 00011 00011 00011
00001 00001 00001 00001 00001 00001 00001 00001
00000 00000 00000 00000 00000 00000 00000 00000

Các lời giải chỉ khác nhau ở dòng đầu. Dòng đầu cho \(M=1\) đến 7 là biểu diễn nhị phân của 1, 2, ..., 7 rồi thêm một 0 ở cuối. Với \(M=8\), đó là biểu diễn nhị phân của 7 rồi thêm 1 ở cuối: cạnh trực tiếp từ tòa nhà 1 tới 5 nâng tổng lên 8. Với \(M\ge9\), đáp án là IMPOSSIBLE.

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 1C.