Bài toán khó đến mức nào?

Thoạt nhìn, Test Set 1 có vẻ có thể giải được ngay cả bằng tay, vì chỉ cần một thiết kế và ta khá tự do chọn số máy tính. Nhưng hóa ra rất khó đồng thời thỏa mãn cả ba yêu cầu sau:

• Mỗi máy tính phải dùng đúng 4 liên kết.
• Mạng phải liên thông.
• Các máy tính phải phân biệt được duy nhất ngay cả sau khi ID bị hoán vị, và ta phải biết cách phân biệt chúng.

Ví dụ, ta có thể tạo một vòng các máy tính, trong đó mỗi máy nối với hai hàng xóm và với hai hàng xóm của các hàng xóm đó. Thiết kế này thỏa mãn điều kiện bậc 4 và liên thông, nhưng có tính đối xứng rất cao, khiến các máy càng khó phân biệt. Ta có thể đưa vào một vài chỗ bất quy tắc bằng cách đổi một số cạnh — sẽ nói thêm ở dưới — để phá đối xứng. Tuy nhiên, khi ấy càng khó quan sát thiết kế bằng mắt, và sau khi bộ chấm hoán vị danh tính của các máy, làm thế nào ta có thể “tìm lại” từng máy của mình?

Khó hơn vẻ bề ngoài

Ta cần một cách gán cho mỗi máy tính một nhãn duy nhất. Các nhãn phải có những tính chất sau:

• Không phụ thuộc ID: nhãn của một máy chỉ phụ thuộc vào cấu trúc liên kết, không phụ thuộc ID của chính nó hay của máy khác.
• Tồn tại những mạng mà mỗi máy có một nhãn duy nhất; hơn nữa, ta có thể tìm được những mạng ấy tương đối hiệu quả.
• Có thể tính hiệu quả các nhãn của một mạng đã cho.

Nếu có một phương pháp gán nhãn với đủ các tính chất này thì lời giải gần như tự hoàn thành: tìm một mạng có kích thước phù hợp, tính nhãn trên mạng đó và trên mạng đã xáo trộn do bộ chấm cung cấp, rồi ghép các máy tính có cùng nhãn.

Có nhiều phương pháp gán nhãn khả dĩ, và thử nghiệm có thể giúp tìm ra chúng. Dưới đây là hai phương pháp: một phương pháp thiên về lý thuyết và một phương pháp thủ công hơn. Cũng tồn tại các cách xây dựng tường minh những mạng bảo đảm phù hợp với một phương pháp gán nhãn cụ thể. Tuy nhiên, cả cách xây dựng lẫn cách gán nhãn như vậy đều khá phức tạp, cần xét nhiều trường hợp, và chỉ những cách xây dựng có nhãn tính được nhanh mới dùng được trong bài này. Việc xây dựng tất nhiên dễ hơn đáng kể đối với Test Set 1, vì ta chỉ cần dựng một mạng và có thể chọn bất kỳ kích thước nào từ 10 đến 50.

Nhãn bằng số đường đi

Hãy bắt đầu với phương pháp lý thuyết vì nó ngắn hơn. Mô hình hóa mạng thành một đồ thị vô hướng mà mọi đỉnh đều có bậc 4. Lấy ma trận kề của đồ thị rồi tính lũy thừa bậc \(p\) của nó; ô \((i,j)\) trong ma trận thu được là số đường đi độ dài \(p\) từ đỉnh \(i\) tới đỉnh \(j\). Trong bài này, bản thân các đường đi không đặc biệt quan trọng; điều quan trọng là số đường đi của một cặp đỉnh \((i,j)\) phụ thuộc vào toàn bộ cấu trúc của mạng. Vì vậy, nếu đủ may mắn, tập các giá trị ở hàng \(i\), tức \((i,1),(i,2),\ldots\), sẽ là duy nhất cho mỗi \(i\).

Thực tế, phần lớn đồ thị của một kích thước cho trước cho các nhãn duy nhất khi \(p=7\), và rất có thể các giá trị \(p\) khác cũng hoạt động. Nhóm tác giả đã sinh đồ thị cho mọi kích thước từ 10 đến 50; chỉ ở hai kích thước họ mới phải thử lần thứ hai, và không bao giờ phải thử lần thứ ba.

Nhãn tinh chỉnh từ lân cận

Với một cách thủ công hơn, trước hết nhận thấy rằng nếu chỉ nhìn riêng từng máy thì mọi máy đều giống nhau: tất cả đều có bốn liên kết đi ra. Điều tương tự đúng với từng hàng xóm trong bốn hàng xóm của một máy. Nhưng ta có thể xét cách các hàng xóm được nối với nhau.

Cụ thể, gán nhãn cho máy \(X\) bằng một đa tập gồm bốn giá trị \(Y_i\), mỗi giá trị ứng với một máy nối với \(X\), trong đó \(Y_i\) là số máy khác đồng thời là hàng xóm của cả \(X\) lẫn máy thứ \(i\) đó. Ví dụ, giả sử máy 1 nối trực tiếp với các máy 2, 3, 4 và 5; ngoài ra có các liên kết trực tiếp 2–3, 2–4 và 4–5, còn mọi liên kết khác của 2, 3, 4 và 5 đi tới các máy khác. Khi ấy đa tập của máy 1 là \(\{1,1,2,2\}\).

Cách gán nhãn này chưa đủ để phân biệt các máy vì không có nhiều nhãn khả dĩ ở dạng trên. Nhưng ta có thể đẩy ý tưởng đi sâu hơn. Gọi các nhãn vừa mô tả là nhãn mức 1. Sau đó, nhãn mức 2 của mỗi máy là đa tập các nhãn mức 1 của các hàng xóm, tức một đa tập gồm bốn đa tập. Ta còn có thể định nghĩa nhãn mức 3 là đa tập các nhãn mức 2 của các hàng xóm, rồi tiếp tục tương tự. Thực tế, nhãn mức 4 đủ mạnh để phân biệt các máy, ít nhất trong khoảng từ 10 đến 50 máy tính.

Hơn nữa, việc gán nhãn một máy chỉ cần xem bốn hàng xóm của nó và một số hữu hạn các liên kết có thể có giữa chúng. Vì thế, một vòng gán nhãn mất \(O(\text{số máy tính})\) thời gian, và toàn bộ quá trình lấy nhãn mức 4 cũng có cùng độ phức tạp. Cách này hiệu quả hơn những phương án khác, chẳng hạn gán nhãn một máy theo chu trình nhỏ nhất hoặc lớn nhất chứa nó.

Sinh mạng để thử các nhãn

Khi đã có một trong hai phương pháp gán nhãn, ta chỉ còn cần tạo các thiết kế mạng để thử. Nếu chọn cạnh hoàn toàn ngẫu nhiên thì xác suất mọi đỉnh đều có bậc đúng 4 rất thấp, nên cần một cách tốt hơn. Một khả năng đơn giản là tạo danh sách chứa đúng bốn bản sao của mỗi ID, xáo trộn danh sách, rồi nối ID thứ nhất với thứ hai, thứ ba với thứ tư, và cứ thế. Nếu xuất hiện vòng tự nối hoặc cạnh lặp thì làm lại cho tới khi không còn lỗi. Xác suất có vòng tự nối hoặc cạnh lặp đủ nhỏ để cách này nhanh chóng hoàn tất ở mọi kích thước.

Một cách sinh đồ thị ít hỗn loạn hơn là bắt đầu từ thiết kế vòng đã nói ở trên, rồi liên tục biến đổi nó như sau:

1. Chọn ngẫu nhiên một máy \(A\) và một hàng xóm \(B\) của nó.
2. Chọn ngẫu nhiên một hàng xóm \(C\) của \(A\) và một hàng xóm \(D\) của \(B\), sao cho \(C\) chưa là hàng xóm của \(B\) và \(D\) chưa là hàng xóm của \(A\).
3. Xóa các liên kết \(A\)–\(C\) và \(B\)–\(D\), rồi thêm các liên kết \(A\)–\(D\) và \(B\)–\(C\).

Phép biến đổi này bảo đảm mỗi máy luôn có bốn liên kết và mạng vẫn liên thông. Trước phép đổi ta có đường \(C\)–\(A\)–\(B\)–\(D\), còn sau phép đổi ta có đường \(C\)–\(B\)–\(A\)–\(D\); do đó, hai máy bất kỳ vốn nối trực tiếp hoặc gián tiếp trước đó vẫn nối với nhau sau phép đổi.

Phần lớn mạng được sinh theo cách này, chẳng hạn sau 1000 phép biến đổi, có nhãn duy nhất cho mọi máy. Nếu gặp một mạng không có tính chất đó — vì mạng vốn có đối xứng hoặc vì phương pháp gán nhãn chưa đủ mạnh đối với mạng ấy — ta chỉ việc bỏ mạng và thử lại. Chiến lược này chỉ mất nhiều nhất vài giây để tìm các thiết kế dùng được cho mọi bộ test có thể; phần còn lại chỉ là cài đặt việc tương tác với bộ chấm.

Cuối cùng, nếu cần, có thể tính trước ngoại tuyến các đồ thị cho mọi kích thước cần thiết rồi viết cứng chúng trong lời giải. Miễn là phương pháp gán nhãn hiệu quả, quá trình tìm đồ thị có hơi chậm cũng không sao, với điều kiện nó hoàn tất trong thời gian cuộc thi. Tuy vậy, mọi ý tưởng trình bày ở trên đều đủ nhanh và không cần tính trước.

Dựa trên phân tích chính thức của Google Code Jam.