USACO 2018 January Contest, Gold Problem 2 - Cow at Large

 Problem Link

Time Complexity: O(N)
Algorithm used: BFS
Official Editorial

In this problem, the layout of a farm is given along with Bessie's initial barn number, where the barns are numbered from 1 to N. From there, Bessie will try to leave the farm from an exitpoint, which is a barn that is connected to exactly one other barn. Barns are connected to each other by roads. There is one path from one barn to another. To stop Bessie from escaping, farmers are initially located at the exitpoints. Bessie and the farmers can move from one barn to another in one unit of time. If a farmer and Bessie are located at the same barn at the same time or are located on the same road at the same time, then Bessie has successfully been caught. The goal of this problem is to successfully catch Bessie using as few farmers as possible.

This problem can be represented as a graph problem, where the barns are nodes in a graph and the roads are the edges. In particular, this graph is a tree because there is exactly one path between any two nodes. Henceforth, the nodes which are exitpoints will be called leaves, and the node where Bessie is initially located will be called the root.

In order for a farmer to be able to catch Bessie, the farmer must be able to reach any node at the same time, or before Bessie reaches that node, otherwise Bessie will always be at least one step ahead of the farmer. Since the farmer wants to reach the node as quickly as possible from their leaf, find the shortest path from the node to any leaf. Here, the shortest path from every leaf to the node is not needed, because that would indicate that a farmer is being placed at every leaf, which would not give the optimal answer. By finding the shortest path from the node to any leaf, we ensure that we find one farmer who can reach the spot the quickest.

To know the minimum amount of time Bessie will take to reach any node in the tree, run one BFS starting from the root, since all the edge weights are the same. Next, to find the length of the shortest path from a node to any leaf, run a BFS from every leaf and reduce the distances for every node. While this may seem to take O(N²) time, the trick is to stop the BFS for every leaf if no distances get reduced because only if the distances of the nodes closest to the leaf get reduced, then the other nodes may get reduced. This gives an O(N) time complexity. 

Once the distances from the root to all nodes and the distances from every node to its nearest leaf have been computed, it is time to use these two pieces of information to find out the minimum number of farmers. To do this, run one final BFS, starting from the root. If Bessie can reach a node before a farmer can reach the node, then increment the number of farmers needed by one, because no other farmer added so far can reach the node. If Bessie cannot reach the node before a farmer, then it means that Bessie will not be able to visit any of the node's children either, since the farmer will always be at least one step ahead of Bessie. So, there is no need to the node's children to the BFS queue.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100001;

vector <int> adj[MAX_N];

bool visited[MAX_N];

//stores distance from node i to nearest leaf.

int dis_from_leaf[MAX_N];

//stores distances from root to node i

int root_dis[MAX_N];

int main()

{

    freopen("atlarge.in", "r", stdin);

    freopen("atlarge.out", "w", stdout);

    int n, root;

    cin >> n >> root;

    for (int i = 0; i < n-1; i++){

        int a, b;

        cin >> a >> b;

        adj[a].push_back(b);

        adj[b].push_back(a);

    }

    fill(dis_from_leaf, dis_from_leaf+n+1, INT_MAX);

    fill(root_dis, root_dis+n+1, INT_MAX);

    //find shortest path from every node to any leaf

    for (int i = 1; i <= n; i++){

        if (adj[i].size() == 1){ //node i is a leaf

            queue <pair <int, int>> q;

            q.push({i, 0});

            dis_from_leaf[i] = 0;

            while (!q.empty()){

                int a = q.front().first, p = q.front().second;

                q.pop();

                for (auto i : adj[a]){

                    if (i == p)

                        continue;

                    if (dis_from_leaf[i] > dis_from_leaf[a] + 1){

                        dis_from_leaf[i] = dis_from_leaf[a] + 1;

                        q.push({i, a});

                    }

                }

            }

        }

    }

    //bessie's initial position is the root in the tree

    //find the length of the path from the root to every node

    queue <pair <int, int>> q;

    q.push({root, 0});

    root_dis[root] = 0;

    while (!q.empty()){

        int a = q.front().first, p = q.front().second;

        q.pop();

        for (auto i : adj[a]){

            if (i == p)

                continue;

            root_dis[i] = root_dis[a] + 1;

            q.push({i, a});

        }

    }

    int ans = 0;

    q.push({root, 0});

    /* for every node, check: if bessie can reach node i before a farmer can

        reach node i, then add one farmer to the answer, since a farmer

        must be able to reach every node at the same time or before bessie.

    */

   // root_dis[i] is the distance travelled by bessie to node i

   //dis_from_leaf[i] is a farmer's shortest path from node i to the nearest leaf.

    while (!q.empty()){

        int a = q.front().first, p = q.front().second;

        q.pop();

        for (auto i : adj[a]){

            if (i == p)

                continue;

            if (dis_from_leaf[i] <= root_dis[i])

                ans++;

            else

                q.push({i, a});

        }

    }

    cout << ans << '\n';

}