Nhận xét mở đầu

Với mọi số nguyên \(X>2\), ta có một cách đơn giản để dựng đồ thị có đúng \(X\) cây khung: nối \(X\) đỉnh thành một chu trình duy nhất.

Mỗi cây khung của chu trình phải thu được bằng cách xóa đúng một cạnh. Có \(X\) cách chọn cạnh cần xóa, và mỗi cách để lại một tập cạnh khác nhau. Vì vậy chu trình có đúng \(X\) cây khung.

Tuy nhiên, đề bài chỉ cho phép tối đa 22 đỉnh, nên cách này chỉ giải quyết trực tiếp được các giá trị \(K\le 22\).

Tiền xử lý toàn bộ đáp án

Đề bài bảo đảm tồn tại đáp án cho mọi \(K\in[3,10000]\). Chỉ có 9998 giá trị \(K\) có thể xuất hiện, vì vậy có thể tìm trước một đồ thị cho từng giá trị, trước cả khi tải dữ liệu thi. Khi xử lý input thật, ta chỉ việc tra bảng và in ma trận kề đã lưu.

Một hướng khám phá tự nhiên là sinh các đồ thị ngẫu nhiên rồi đếm số cây khung của từng đồ thị.

Đếm cây khung bằng định lý ma trận–cây Kirchhoff

Định lý ma trận–cây Kirchhoff đưa việc đếm cây khung về tính định thức.

Với đồ thị có \(n\) đỉnh, lập ma trận Laplace \(L\):

• \(L_{ii}\) bằng bậc của đỉnh \(i\);
• với \(i\ne j\), \(L_{ij}=-1\) nếu có cạnh \(i-j\), và bằng 0 nếu không có cạnh.

Xóa một hàng và cột cùng chỉ số bất kỳ khỏi \(L\). Định thức của ma trận \((n-1)\times(n-1)\) còn lại chính là số cây khung của đồ thị.

Có thể tự cài đặt phép tính định thức một cách cẩn thận hoặc dùng một thư viện, chẳng hạn SciPy. Cần chú ý tràn số: đồ thị đầy đủ 22 đỉnh có \(22^{20}\) cây khung. Nếu không làm việc với số hữu tỉ hoặc số nguyên chính xác, sai số cũng là một nguy cơ. Dù vậy, một lời giải nội bộ đã dùng khử Gauss với số thực double thành công.

Mỗi lần đếm bằng khử Gauss tốn \(O(n^3)\) thời gian và \(O(n^2)\) bộ nhớ, với \(n\le22\).

Tìm kiếm ngẫu nhiên

Ta có thể thay đổi số đỉnh và xác suất xuất hiện độc lập của mỗi cạnh, sinh nhiều đồ thị rồi lưu đáp án cho mọi số cây khung mới gặp được.

Tìm kiếm ngẫu nhiên thuần túy không tìm được toàn bộ các giá trị cần thiết, nhưng tìm được phần lớn trong số đó. Điều này cho thấy ta có thể lấp các khoảng trống bằng cách điều chỉnh thêm. Theo thực nghiệm của phân tích chính thức, đồ thị 13 đỉnh với xác suất tồn tại của mỗi cạnh là \(1/4\) hoạt động tốt.

Điều chỉnh đồ thị về một mục tiêu

Một chiến lược khác là sửa từng bước một đồ thị hiện tại:

1. Ghi nhớ các giá trị số cây khung chưa tìm được và chọn một giá trị làm mục tiêu.
2. Nếu đồ thị hiện tại có ít cây khung hơn mục tiêu, thêm một cạnh.
3. Nếu nó có nhiều cây khung hơn mục tiêu, xóa một cạnh, nhưng không được làm đồ thị mất liên thông.
4. Đếm lại số cây khung và tiếp tục cho đến khi đạt mục tiêu.
5. Chọn một mục tiêu chưa đạt khác và lặp lại.

Để quá trình kết thúc nhanh hơn, mỗi giá trị tình cờ đi qua cũng được đánh dấu là đã tìm thấy, ngay cả khi nó không phải mục tiêu hiện tại.

Thêm cạnh không thể làm giảm số cây khung, vì mọi cây khung cũ vẫn tồn tại và có thể xuất hiện thêm cây khung dùng cạnh mới. Tương tự, xóa một cạnh không thể làm tăng số cây khung. Điều kiện giữ liên thông khi xóa bảo đảm đồ thị vẫn có ít nhất một cây khung. Do đó hai thao tác đi đúng hướng về mặt số lượng, dù kích thước mỗi bước không bảo đảm bằng 1; đây vẫn là một quá trình tìm kiếm thực nghiệm chứ không phải một chứng minh hội tụ cho mọi mục tiêu.

Hai giá trị khó

Trong cả tìm kiếm ngẫu nhiên lẫn quá trình điều chỉnh, việc tìm đáp án cho \(K=13\) và \(K=22\) có thể mất rất lâu, vì dường như hai giá trị này đòi hỏi cấu trúc khá đặc biệt.

Ta xử lý chắc chắn chúng bằng construction ở phần đầu: dùng chu trình lần lượt có 13 hoặc 22 đỉnh.

Tính đúng đắn của các đáp án xuất ra

Mỗi đồ thị được lưu trong bảng chỉ sau khi định lý Kirchhoff xác nhận định thức tương ứng đúng bằng \(K\). Ma trận kề được in đối xứng, có đường chéo bằng 0 và có không quá 22 đỉnh, nên mô tả một đồ thị đơn hợp lệ. Vì định lý Kirchhoff đếm chính xác số cây khung, đồ thị xuất ra có đúng số cây khung mà test yêu cầu.

Riêng với construction chu trình, chứng minh ở phần đầu cho thấy mỗi cây khung tương ứng duy nhất với cạnh bị xóa, nên có đúng \(K\) cây khung.

Độ phức tạp

Giai đoạn tìm kiếm ngoại tuyến mang tính thực nghiệm nên không có một chặn thời gian tất định hữu ích; mỗi lần đánh giá một đồ thị tốn \(O(n^3)\) thời gian và \(O(n^2)\) bộ nhớ.

Sau khi đã tạo bảng đáp án, mỗi test chỉ cần in một ma trận kề kích thước không quá \(22\times22\), tức \(O(n^2)\) thời gian và \(O(n^2)\) dữ liệu lưu cho đáp án đó.

Ghi chú của phân tích chính thức

Đây vốn là một bài toán thực nghiệm, đòi hỏi nghiên cứu bằng máy tính thay vì chỉ viết một construction trên giấy. Phân tích chính thức không biết một lời giải construction tổng quát khả thi và mời chia sẻ nếu có. Kỹ năng nghiên cứu thăm dò như vậy có giá trị trong lập trình thực tế; đây cũng là một ví dụ đáng chú ý khi chiến lược ngẫu nhiên có thể hoạt động.

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức Google Code Jam 2017 - World Finals - Spanning Planning, kho Google Coding Competitions (Apache-2.0).