Solving UVa 10369 – Arctic Network

This post will focus on UVa 10369 – Arctic Network. The problem isn’t especially difficult, but can be tricky to approach.

Essentially, you are given the location for up to 500 nodes on a 2d plane and told that up to S (1 ≤ S ≤ 100) nodes can be connected together at any distance. All nodes are also able to connect to each other, up to and including some distance D, and you are tasked to find the smallest D necessary to connect all nodes.

Approach

If there weren’t nodes that can connect at any distance with no cost, this would be a simple Minimum Spanning Tree problem. But there are S nodes that can connect at any distance so some nodes can be connected for free (which would further connect all of the other nodes they are connected to).

So we want to determine the smallest D required to create S (or less) subgraphs, since those could then be connected using the S nodes able to communicate at any distance.

Solution

At any single D value, it is really easy to see which nodes are in a single subgraph – run a depth first search.

void DFS(int node, double D)
{
    encountered[node] = true;
    
    for (int i = 0; i < NumNodes; ++i)
    {
        if (!encountered[i] && GetDistance(i, node) <= D)
            DFS(i, D);
    }
}

If the dfs must be run on more than S separate nodes (so it has more than S connected components) for a given value of D, then the graph will not be able to be completely connected – there will be at least one subgraph that isn’t connected.

// Would need to reset encountered every time this function is called.
bool CanConnectWithNumOutposts(int outposts, const double D)
{
    for (int i = 0; i < N && outposts >= 0; ++i)
    {
        if (!encountered[i])
        {
            DFS(i, D);
            --outposts;
        }
    }
    
    return outposts >= 0;
}

Then, we can just binary search on the value of D — if the dfs succeeds with the value of D, it is the highest D value that we need to consider, and if the dfs fails, then that D is too small. The code is approximately:

double minDistance = 0, maxDistance = GetMaxDistance();

// Epsilon is acceptable error, ~0.0001 for this problem
while (maxDistance - minDistance > Epsilon)
{
    double D = (minDistance + maxDistance) / 2;

    // TODO: Reset encountered to all false first.
    if (CanConnectWithNumOutposts(S, D))
        maxDistance = D; // Can possibly use less distance
    else
        minDistance = D + Epsilon; // Will need more distance
}

Code

My accepted code is on Github.

To increase the accuracy & simplicity of the program, I ran the binary search on a list containing the squared distances between the each pair of nodes. Also, I did not need to reset encountered every iteration due to using an int to determine if a node had been reached in the current iteration.

The complexity of the DFS is N2 (since it will need to use an adjacency matrix), and it is run log(N2) (or 2 × log(N)) times. So the complexity is N2log(N).

Similar Problems

Two problems requiring a similar approach are UVa 714 – Copying Books and UVa 1221 – Against Mammoths.

Alternative Approach – Minimum Spanning Tree

While this problem doesn’t seem to be solvable using a MST it can be solved using algorithms for MST. Instead of using a regular MST approach, where we aim to connect all of the nodes, we will instead connect using PS edges (where the edges are the lowest distance possible without joining two already connected nodes), creating S sub-graphs. Then, the remaining S sub-graphs are connected for free, just like the binary search solution.

Note that we would need to use Kruskal’s algorithm (or similar algorithms) to ensure that we create S cheapest sub-graphs (Prim’s algorithm would not necessarily create the correct S sub-graphs).
The distance of the final edge connected would be D.

An example solution was created by morris821028 on GitHub.

Leave a Reply

Your email address will not be published. Required fields are marked *

[TOP]