Test Set 1

Ta bắt đầu bằng mô hình mạng luồng. Dựng đồ thị có hướng \(G\) với tập đỉnh

trong đó \(S\) là tập các ô chứa đồn, còn \(B\) là tập các ô không chứa đồn nhưng nằm trong phạm vi ít nhất một đồn. Các cạnh là

Mỗi đường từ source đến sink nối một đồn cụ thể với một ô cụ thể. Gán dung lượng \(|B|\) cho cạnh \(\text{source}\to s\), và dung lượng \(1\) cho mọi cạnh còn lại. Mỗi luồng nguyên hợp lệ là hợp của các đường source–đồn–ô–sink; dung lượng bảo đảm mỗi ô thuộc không quá một đường. Luồng cực đại phủ mọi ô trong \(B\), nên các luồng cực đại tương ứng với các cách phân công. Bài toán trở thành tối thiểu hóa hiệu giữa luồng lớn nhất và nhỏ nhất qua các cạnh đi ra từ source trong một luồng cực đại của \(G\).

Muốn đặt cận trên \(U\) cho luồng qua mỗi cạnh đi ra từ source, đổi dung lượng các cạnh ấy thành \(U\). Muốn thêm cận dưới \(L\), thay mỗi cạnh bằng hai bản sao: một cạnh dung lượng \(L\), chi phí \(0\), và một cạnh cho phần dung lượng còn lại tới \(U\), chi phí \(1\); mọi loại cạnh khác có chi phí \(0\). Dùng luồng cực đại chi phí nhỏ nhất thay vì luồng cực đại sẽ ưu tiên đưa ít nhất \(L\) đơn vị qua mỗi đồn. Nếu luồng thu được không dùng hết mọi cạnh dung lượng \(L\), thì không tồn tại luồng thỏa cận dưới.

Từ đó, có thể thử mọi cặp \((L,U)\), loại các cặp không tạo được luồng tổng \(|B|\) đồng thời bão hòa mọi cạnh chi phí \(0\) đi ra từ source. Đáp án là \(U-L\) nhỏ nhất trong các cặp còn lại.

Cả \(L\) và \(U\) không vượt \(|B|\le RC\). Kích thước \(G\) là \(O(SRC)\). Luồng cực đại chi phí nhỏ nhất trên đồ thị chỉ có chi phí \(0,1\) mất thời gian tuyến tính cho mỗi đường tăng luồng và bậc hai tổng thể. Thuật toán thô có độ phức tạp \(O(S^2R^4C^4)\), có thể quá chậm ngay cả cho bộ 1. Chỉ cần một trong các tối ưu sau để vượt qua:

• Chỉ thử các cặp có khả năng cải thiện. Nếu \((L,U)\) không khả thi thì \((L+1,U),(L+2,U),\ldots\) cũng không khả thi, nên chuyển sang \((L,U+1)\). Nếu \((L,U)\) khả thi thì \((L,U+1),(L,U+2),\ldots\) cũng khả thi nhưng có hiệu lớn hơn, nên chuyển thẳng sang \((L+1,U)\). Nhờ đó chỉ kiểm tra tuyến tính thay vì bậc hai số cặp.
• Một phiên bản đơn giản hơn là thử mọi giá trị của chỉ \(L\) hoặc chỉ \(U\), rồi tìm kiếm nhị phân giá trị tối ưu của biến kia. Số cặp chưa xuống tuyến tính theo \(|B|\) nhưng đã trở thành gần tuyến tính.
• Luồng cho \((L,U)\) cũng hợp lệ cho \((L,U+1)\). Thay vì tính lại từ đầu, tái sử dụng nó để giảm mạnh tổng số đường tăng luồng cần tìm.

Test Set 2

Ở bộ 2, \(R,C\) quá lớn để xuất hiện tuyến tính trong thời gian chạy. Ta phải cải thiện ít nhất hai mặt: kích thước \(G\), vốn tuyến tính theo \(R,C\) và ảnh hưởng mọi thuật toán chạy trên \(G\); và số cặp \((L,U)\) cần thử, cũng đang ít nhất tuyến tính.

Trước hết, định nghĩa lại \(G\) bằng nén tọa độ. Gọi \(B'\) là một tập các tập ô tạo thành một phân hoạch của \(B\). Cắt toàn bộ lưới theo tối đa \(2S\) đường ngang và \(2S\) đường dọc tại biên phạm vi của từng đồn. Trong mỗi hình chữ nhật thu được, tập các đồn có thể đến mọi ô là như nhau. Mỗi hình chữ nhật chỉ đại diện các ô không chứa đồn bên trong nó.

Giờ \(G\) có các đỉnh \(\{\text{source},\text{sink}\}\cup S\cup B'\) và các cạnh source–đồn, đồn–hình chữ nhật có thể tuần tra, hình chữ nhật–sink. Cần điều chỉnh dung lượng: cạnh \(\text{source}\to s\) vẫn có dung lượng \(|B|\), coi như vô hạn; cạnh \(s\to b'\) cũng vậy; cạnh \(b'\to\text{sink}\) có dung lượng \(|b'|\). Mỗi đỉnh \(b'\) hợp nhất nhiều đỉnh \(b\) của đồ thị cũ, nên dung lượng cạnh ra bằng tổng dung lượng các cạnh ra cũ. Đồ thị mới có \(O(S^2)\) đỉnh và kích thước \(O(S^3)\).

Một đường \(\text{source}\to s\to b'\to\text{sink}\) mang luồng \(X\) biểu thị giao \(X\) ô trong \(b'\) cho đồn \(s\). Luồng không còn song ánh với cách phân công nếu phân biệt từng ô, nhưng sẽ song ánh khi coi mọi hoán vị các ô trong cùng hình chữ nhật là tương đương. Vì các ô ấy hoàn toàn tương đương với bài toán, như vậy là đủ. Ta vẫn cần luồng cực đại sao cho hiệu giữa luồng lớn nhất và nhỏ nhất trên các cạnh đi ra từ source là nhỏ nhất.

Không thể thử mọi \(L,U\), nên dùng thêm lý thuyết. Gọi \(G_C\) là bản sao của \(G\) trong đó dung lượng mọi cạnh \(\text{source}\to s\) đổi thành \(C\). Khi đó \(G=G_{|B|}\). Mọi luồng hợp lệ trong \(G_C\) cũng hợp lệ trong \(G_{C'}\) với \(C'\ge C\).

Gọi \(U\) là giá trị nhỏ nhất sao cho \(G_U\) cho phép luồng tổng \(|B|\). Gọi \(L\) là giá trị lớn nhất sao cho tồn tại luồng cực đại kích thước \(|S|L\) trong \(G_L\), tức một luồng bão hòa mọi cạnh \(\text{source}\to s\).

Mọi luồng cực đại trong \(G\) có ít nhất một cạnh \(\text{source}\to s\) mang luồng không nhỏ hơn \(U\); nếu không, luồng ấy hợp lệ trong \(G_{U-1}\), mâu thuẫn định nghĩa \(U\). Mọi luồng cực đại trong \(G\) cũng có ít nhất một cạnh \(\text{source}\to s\) mang luồng không lớn hơn \(L\). Nếu tất cả đều lớn hơn \(L\), có thể bớt luồng trên các đường mang hơn \(L\) cho đến khi mỗi đồn mang đúng \(L+1\), tạo luồng kích thước \(|S|(L+1)\) trong \(G_{L+1}\) và mâu thuẫn định nghĩa \(L\).

Cuối cùng, bắt đầu từ luồng trong \(G_L\) chứng minh định nghĩa của \(L\) và coi nó là luồng hợp lệ trong \(G_U\). Có thể mở rộng nó thành luồng cực đại \(F\) của \(G_U\) bằng các đường tăng luồng. Vì đường tăng không chứa chu trình, chúng không giảm luồng trên cạnh \(\text{source}\to s\). Do đó \(F\) có hiệu lớn nhất–nhỏ nhất đúng bằng \(U-L\). Theo định nghĩa, luồng cực đại của \(G_U\) cũng là luồng cực đại của \(G\). Các cận trên chứng minh không luồng nào trong \(G\) đạt hiệu nhỏ hơn \(U-L\), nên đáp án chính là \(U-L\).

Tìm kiếm nhị phân độc lập \(L\) và \(U\) theo các định nghĩa ban đầu cho thuật toán \(O(S^5\log(RC))\).

Nội dung trên được chuyển ngữ đầy đủ từ phân tích chính thức của Google Code Jam 2018, Chung kết thế giới, bài Jurisdiction Restrictions.