Hướng dẫn cho Google Code Jam 2022 - Intranets

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Mô hình đồ thị

Ta dùng thuật ngữ đồ thị: các đỉnh là \(\mathbf{M}\) máy và các cạnh là \(\binom{\mathbf{M}}2\) liên kết.

Test Set 1

Xét quá trình gán độ ưu tiên cho các cạnh lần lượt từ cao nhất đến thấp nhất. Để tiện trình bày, gọi độ ưu tiên cao thứ \(i\) là ưu tiên \(i\), tức số nhỏ hơn biểu thị ưu tiên cao hơn.

Giả sử đã gán \(i\) độ ưu tiên cao nhất cho \(i\) cạnh và cần gán ưu tiên \(i+1\) cho một cạnh mới. Có ba loại lựa chọn. Gọi cạnh mới là \((u,v)\) và gọi \(S_i\) là tập các đỉnh xuất hiện trong \(i\) cạnh đã nhận ưu tiên cao nhất.

Nếu cả \(u\) và \(v\) chưa xuất hiện trong các cạnh đã gán, tức \(u\notin S_i\) và \(v\notin S_i\), có \(\binom{\mathbf{M}-|S_i|}{2}\) cạnh như vậy. Khi đó \(u,v\) tạo một intranet mới, số intranet tăng \(1\) và \(|S_{i+1}|=|S_i|+2\).
Nếu \(u\in S_i\) và \(v\notin S_i\) — hai vai trò có thể đổi cho nhau — có \(|S_i|(\mathbf{M}-|S_i|)\) cạnh như vậy. Khi đó \(v\) gia nhập intranet chứa \(u\), số intranet không đổi và \(|S_{i+1}|=|S_i|+1\).
Nếu \(u\in S_i\) và \(v\in S_i\), có \(\binom{|S_i|}{2}-i\) cạnh chưa được gán thuộc loại này. Cạnh mới không được kích hoạt, nên số intranet không đổi và \(|S_{i+1}|=|S_i|\).

Từ đó dùng quy hoạch động. Đặt \(\operatorname{dp}(i,j,k)\) là xác suất sau khi gán \(i\) độ ưu tiên cao nhất, tập đỉnh được \(i\) cạnh ấy đưa vào có kích thước \(j\), và đã hình thành \(k\) intranet. Các chuyển trạng thái suy ra trực tiếp từ ba trường hợp trên. Độ phức tạp là \(O(\mathbf{M}^4)\), đủ cho Test Set 1.

Có thể tăng tốc xuống \(O(\mathbf{M}^2)\) bằng cách bỏ \(i\) khỏi khóa trạng thái. Đặt \(\operatorname{dp}(j,k)\) là xác suất rằng sau khi gán một số \(i\) độ ưu tiên cao nhất nào đó, tập đỉnh đã xuất hiện có kích thước \(j\) và đã hình thành \(k\) intranet. Lần chuyển tiếp theo là gán độ ưu tiên cao nhất trong số các cạnh thuộc loại 1 và 2 ở trên; ta không còn quan tâm thứ tự ưu tiên của các cạnh loại 3. Xác suất tạo một intranet mới là

\[ \frac{\binom{\mathbf{M}-|S_i|}{2}} {\binom{\mathbf{M}-|S_i|}{2}+|S_i|(\mathbf{M}-|S_i|)}. \]

Quan sát cấu trúc đồ thị

Từ lời giải Test Set 1, mỗi intranet tương ứng với một cặp đỉnh \((u,v)\) sao cho cả \(u\) lẫn \(v\) đều kích hoạt cạnh \((u,v)\). Ta cũng có thể chứng minh trực tiếp điều này.

Cố định một cách gán độ ưu tiên và xét đồ thị có hướng trong đó các đỉnh là các máy, còn có cung \((u,v)\) khi máy \(u\) sử dụng liên kết nối \(u\) với \(v\). Đây là một đồ thị hàm — mỗi đỉnh có bậc ra bằng \(1\) — nên mỗi thành phần liên thông chứa đúng một chu trình, và có thể có các chuỗi đỉnh dẫn vào chu trình đó.

Nhận xét quyết định là chu trình không thể dài từ \(3\) trở lên. Giả sử ngược lại rằng các đỉnh \(u_1,\ldots,u_c\) với \(c\ge3\) tạo một chu trình theo thứ tự ấy. Gọi độ ưu tiên của liên kết nối \(u_i\) và \(u_{i+1}\) là \(p_i\), với chỉ số lấy theo modulo \(c\); các liên kết này đôi một khác nhau. Vì máy \(u_i\) dùng liên kết có ưu tiên cao nhất, theo quy ước số nhỏ hơn là ưu tiên cao hơn, ta có \(p_i<p_{i-1}\). Điều này dẫn đến

\[ p_1>p_2>\cdots>p_c>p_1, \]

mâu thuẫn. Cạnh khuyên cũng không thể tồn tại, nên mọi chu trình trong đồ thị đều có độ dài \(2\).

Test Set 2

Gọi tập các cạnh được cả hai đầu mút kích hoạt là một ghép cặp hoạt động, vì chúng tạo thành một matching. Bài toán trở thành tính xác suất kích thước của ghép cặp hoạt động đúng bằng \(\mathbf{K}\).

Với một matching \(X\), đặt \(f(X)\) là xác suất ghép cặp hoạt động đúng bằng \(X\). Vì khó tính trực tiếp \(f(X)\), áp dụng nguyên lý bù trừ: đặt \(g(X)\) là xác suất ghép cặp hoạt động chứa \(X\), tức

\[ g(X)=\sum_{Y\supseteq X}f(Y). \]

Đảo biến đổi này cho

\[ f(X)=\sum_{Y\supseteq X}(-1)^{|Y|-|X|}g(Y). \]

Vì vậy đáp án là

\[ \begin{aligned} \sum_{|X|=\mathbf{K}}f(X) &=\sum_{|X|=\mathbf{K}}\sum_{Y\supseteq X}(-1)^{|Y|-|X|}g(Y)\\ &=\sum_{|Y|\ge\mathbf{K}}\binom{|Y|}{\mathbf{K}}(-1)^{|Y|-\mathbf{K}}g(Y)\\ &=\sum_{i\ge\mathbf{K}}\binom{i}{\mathbf{K}}(-1)^{i-\mathbf{K}} \sum_{|X|=i}g(X). \end{aligned} \]

Phần còn lại là tính \(g(X)\). Đại lượng này chỉ phụ thuộc vào \(|X|\); ta cần tính khi \(|X|=i\) với mỗi \(i=\mathbf{K},\mathbf{K}+1,\ldots,\lfloor\mathbf{M}/2\rfloor\). Có \(i!\) thứ tự ưu tiên có thể gán cho các cạnh trong \(X\). Cố định một thứ tự và gọi các cạnh của \(X\), từ ưu tiên thấp nhất đến cao nhất, là

\[ (u_1,v_1),(u_2,v_2),\ldots,(u_i,v_i). \]

Điều kiện ghép cặp hoạt động chứa \(X\) tương đương với việc, với mỗi \(j=1,2,\ldots,i\), cạnh \((u_j,v_j)\) có ưu tiên cao nhất trong số các cạnh chạm ít nhất một đỉnh thuộc \(u_1,v_1,\ldots,u_j,v_j\). Do đó

\[ g(X)=i!\prod_{j=1}^{i} \frac{1}{\binom{\mathbf{M}}2-\binom{\mathbf{M}-2j}{2}}. \]

Các mẫu số có thể phân tích nhân tử để thấy rằng chúng không chia hết cho \(10^9+7\). Số matching kích thước \(i\) là

\[ \frac{1}{i!2^i}\frac{\mathbf{M}!}{(\mathbf{M}-2i)!}. \]

Như vậy hoàn tất lời giải \(O(\mathbf{M})\); các phép chia có thể được thực hiện hiệu quả bằng cách dùng dạng phân tích nhân tử, dù điều này không bắt buộc.

Trên thực tế, có thể đồng thời tìm đáp án cho mọi \(K=1,\ldots,\lfloor\mathbf{M}/2\rfloor\) trong \(O(\mathbf{M}\log\mathbf{M})\): phép biến đổi từ \(g\) sang \(f\) có thể biểu diễn thành một phép chập, rồi tính bằng FFT.

Google Code Jam khuyến nghị luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1C.

Bình luận

Tải bình luận...

Không có bình luận nào.