NETWORK - Editorial

editorial
july11
medium
network

#1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

I’ll be the first to admit that needless optimization problems are not very fun. In this case, however, the intended solution complexity was either O(C * S^2) or O(C^2), so the 2 second time limit was actually quite generous. Unfortunately, many passing solutions had worse complexity but relied on constant-factor optimization tweaks, which is why it might have felt like a needless optimization problem.

We treat the problem as a network flow problem. There is a node for each access point, and one for each computer, as well as a source node and sink node. There’s an edge from the source to each of the access points with capacity equal to the access point’s capacity. There’s an edge from each computer to the sink with capacity 1. Initially, there are no other edges. For each computer, we will add edges to the graph until an augmenting path is possible. These additional edges correspond to connections from a computer to an access point, and are added in ascending order by distance. Once an augmenting path is found, the length of the longest edge is output. The augmenting path algorithm used is the key to this problem, and 2 different versions follow.

Solution 1

This is the solution used by the setter. Consider paths of length 2 in the residual graph of the flow network. Construct a secondary graph with S+1 nodes: one for each of the access points, and one for the sink. The number of edges between any two nodes in this graph is constructed as the number of paths of length 2 between the corresponding nodes in the residual graph of the flow network. Additionally, we keep a (S+1) * (S+1) boolean matrix, where cell (i,j) indicates whether there exists any path from node i to node j in the secondary graph. This matrix is stored as an array of bitsets.

Now consider the operation of adding an edge to the flow network. At most 1 edge is added to the secondary graph, and at most S bitset operations are needed to update the matrix. We can now check if an augmenting path exists by checking the matrix at positions (i,j) where i is an access point not yet at capacity, and j is the sink. If an augmenting path exists, the path can be found in O(S^2) using a depth-first search, the secondary graph updated in O(S^2), and the matrix rebuilt using the Floyd-Warshall algorithm in O(S^2) bitset operations. Thus, adding an edge to the graph takes O(S), and augmenting the graph takes O(S^2). Since O(C * S) edges are added to the graph, and O© augments are performed, the total complexity is O(C * S^2), where bitset operations are assumed to take constant time.

Solution 2

This is the solution used by the tester. When adding a new computer to the network, we place the computer in a queue, and mark all access points as unvisited. We then repeat the following process until either the queue is empty, or we visit an access point which is not yet at capacity: Take a computer from the queue, and find all unvisited access points which have an edge to this computer (this can be done in a single bitset operation). If any of these access points is below capacity (which can be checked with a single bitset operation), we’ve found an augmenting path. Otherwise, for each of these access points, mark it as visited and add all of the computers it services to the queue. If the queue is emptied before an augmenting path is found, another edge is added to the graph. If the computer corresponding to the new edge was previously queued, it is queued again, and the above process continues. Since each computer is queued at most once per augmenting path plus once per edge added, the total runtime is O(C^2), where bitset operations are again assumed to take constant time.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.