Phân tích: Wi-fi Towers

Đồ thị liên kết

Chúng ta bắt đầu bằng cách biểu diễn bài toán dưới dạng một bài toán đồ thị. Mỗi tháp là một đỉnh trong đồ thị và có trọng số bằng điểm số của nó. Nếu tháp \(A\) có tháp \(B\) nằm trong phạm vi phủ sóng của nó, chúng ta biểu diễn điều này bằng một cạnh có hướng từ \(A\) đến \(B\). Bài toán trở thành: chọn một tập hợp các đỉnh có tổng trọng số lớn nhất sao cho đối với mọi cạnh từ \(A\) đến \(B\), nếu \(A\) được chọn thì \(B\) cũng phải được chọn. Trong phần tiếp theo, gọi \(V\) là số lượng tháp (đỉnh) và \(E\) là số lượng cạnh.

Chuyển đổi sang bài toán Lát cắt tối thiểu (MIN-CUT)

Để đưa bài toán về dạng MIN-CUT, chúng ta tạo một mạng luồng như sau:

1. Tạo một đỉnh nguồn (\(source\)), một đỉnh đích (\(sink\)), và một đỉnh cho mỗi tháp.
2. Giả sử một tháp có điểm số là \(s\):
3. Nếu \(s > 0\), tạo một cạnh từ đỉnh tháp đó đến đỉnh đích với dung lượng là \(s\).
4. Nếu \(s < 0\), tạo một cạnh từ đỉnh nguồn đến đỉnh tháp đó với dung lượng là \(|s|\).
5. Đối với mỗi cạnh trong đồ thị liên kết ban đầu (từ \(A\) đến \(B\)), tạo một cạnh tương ứng trong mạng luồng với dung lượng vô hạn (\(\infty\)).

Mạng luồng này có \(V + 2 = O(V)\) đỉnh và \(O(V + E)\) cạnh.

Mọi lát cắt có dung lượng hữu hạn trong đồ thị này đại diện cho một cách chọn các tháp — chúng ta chọn mọi tháp nằm cùng phía với đỉnh nguồn trong lát cắt. Các cạnh có dung lượng vô hạn đảm bảo rằng việc lựa chọn tuân thủ các ràng buộc đã cho (nếu không, chúng ta sẽ nhận được một lát cắt có trọng số vô hạn). Các cạnh từ nguồn và đến đích sẽ khấu trừ điểm một cách thích hợp cho việc chọn các tháp có điểm âm và việc không chọn các tháp có điểm dương. Nếu giá trị của lát cắt nhỏ nhất là \(C\), thì câu trả lời là \(S - C\), trong đó \(S\) là tổng các điểm số dương của tất cả các tháp.

Giải bài toán MIN-CUT

Theo định lý luồng cực đại - lát cắt tối thiểu, chúng ta có thể giải bài toán MIN-CUT bằng cách tính luồng cực đại trên cùng đồ thị đó. Để tính luồng cực đại, chúng ta có thể sử dụng:

• Thuật toán Edmonds-Karp: Một biến thể của Ford-Fulkerson sử dụng BFS để tìm đường tăng luồng, có độ phức tạp \(O(V(V+E)^2) = O(V^5)\). Trong thực tế, thuật toán này đủ nhanh để giải quyết tất cả các bộ thử nghiệm.
• Thuật toán Push-relabel: Với quy tắc chọn đỉnh FIFO, độ phức tạp là \(O(V^3)\).
• Thuật toán Ford-Fulkerson với kỹ thuật Capacity Scaling: Do các dung lượng là số nguyên, việc tìm các đường tăng luồng với trọng số là các lũy thừa của 2 giảm dần sẽ cho độ phức tạp \(O((V+E)^2 \log F) = O(V^4 \log F)\), trong đó \(F\) là giá trị luồng cực đại.

Giảm số lượng cạnh

Có một mẹo hình học giúp giảm số lượng cạnh \(E\) xuống còn \(O(V)\), từ đó giảm độ phức tạp của các thuật toán trên.
Đầu tiên, lưu ý rằng chúng ta có thể loại bỏ các cạnh mà không làm thay đổi kết quả cuối cùng miễn là bao đóng chuyển tiếp (transitive closure) của đồ thị không đổi.

Mẹo quan trọng là: nếu có hai cạnh có hướng \(A \to C\) và \(B \to C\), và góc \(\angle ACB\) nhỏ hơn 60 độ, chúng ta có thể loại bỏ cạnh dài hơn. Giả sử \(A \to C\) dài hơn \(B \to C\). Khi đó, nếu ta loại bỏ cạnh \(A \to C\), vẫn sẽ tồn tại một kết nối gián tiếp \(A \to B \to C\) (sử dụng các cạnh có độ dài ngắn hơn hoặc bằng), nhờ vào việc phạm vi của \(A\) là một hình tròn.

Nếu tiếp tục thực hiện việc này, mỗi đỉnh sẽ chỉ còn tối đa 6 cạnh đi vào, giúp giảm tổng số cạnh xuống còn tối đa \(6V\).

Thông tin thêm

Bài toán này tương đương với bài toán Minimum Closure Problem (Bài toán Bao đóng Tối thiểu), đã được nghiên cứu từ những năm 1970 và có ứng dụng trong ngành khai thác mỏ.

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