Connecting Two Barns

#1

Problem Link: USACO

I understand the official algorithm, but my previous algorithm timed out despite being similar to the official solution.

My previous algorithm timed out for the last 5 test cases. Here’s a description: Get all the connected components using dfs. Then for each of the connected components, use binary search to get the closest distance from that component to the component with farm 1 and from the component containing farm n.

I don’t understand why this times out even though I am presumably checking n nodes.

#2

Your algorithm seems correct. Could you paste your code? Would make it easier to debug(How to ask for help on a problem)

#3

Are you sure about that? A common mistake on the binary search is which array you’re binary searching on… Check my code here for more information on how to do this.

#4

I am in the process of commenting my code. I will share it with you alll soon.
Edit:

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <string>

using namespace std;

typedef long long ll;

const ll maxn = 1e5 + 10;
const ll zer = 0;
const ll bignumber = 9999999999999;

//input
ll n, m;

//adjacency list
vector <ll> adj[maxn];
//visited array for dfs
bool visited[maxn];

bool works(ll constraint) {
    return true;
}

//clear adjacency list and visited
void init() {
    for (ll i = 1; i <= n; i++) {
        adj[i].clear();
        visited[i] = false;
    }
}

//stores the connected components
vector <vector <ll>> cc;
//stores the ids of each of the nodes
ll id[maxn];
//used to get the connected components
vector <ll> temp;

//self-explanatory dfs
void dfs(ll node) {
    for (ll k = 0; k < adj[node].size(); k++) {
        if (!visited[adj[node][k]]) {
            visited[adj[node][k]] = true;
            temp.push_back(adj[node][k]);
            dfs(adj[node][k]);
        }
    }
}

//computes the ID of each of the n nodes
void computeID() {
    for (ll k = 0; k < cc.size(); k++) {
        for (ll i = 0; i < cc[k].size(); i++) {
            id[cc[k][i]] = k;
        }
    }
}

void floodfill() {
    //clear everything from previous test cases
    cc.clear();
    temp.clear();

    for (ll i = 1; i <= n; i++) id[i] = -1;
    
    //get the connected components and build cc
    for (ll i = 1; i <= n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            temp.push_back(i);
            dfs(i);
            
            sort(temp.begin(), temp.end());
            
            cc.push_back(temp);
            temp.clear();
        }
    }
    
    //compute the IDs of each of the n nodes
    computeID();
}

//since lower bound returns the first index >=, I might need the returned index or the returned index minus 1 (if possible)
//a and b are the ids of two connected components
ll calculateCost(ll a, ll b) {
    //If they are the same component, return 0
    if (a == b) {
        return 0;
    }
    
    //set ret to a big number
    ll ret = bignumber;
    
    //traverse the array with smaller size
    if (cc[a] > cc[b]) {
        swap(a, b);
    }
    
    //check each element of cc[a] and binary search on cc[b]
    for (ll k = 0; k < cc[a].size(); k++) {
        ll index1 = lower_bound(cc[b].begin(), cc[b].end(), cc[a][k]) - cc[b].begin();
        ll index2 = index1 - 1;
                
        if (index1 >= 0 && index1 < cc[b].size()) {
            ret = min(ret,  (cc[b][index1] - cc[a][k]) * (cc[b][index1] - cc[a][k]));
        }
        
        if (index2 >= 0 && index2 < cc[b].size()) {
            ret = min(ret, (cc[b][index2] - cc[a][k]) * (cc[b][index2] - cc[a][k]));
        }

    }
    
    return ret;
}




void solve()
{
    cin >> n >> m;
    
    init();
    
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    //get the cc's
    floodfill();
    
    //If 1 and N are in the same component, print 1
    if (id[1] == id[n]) {
        cout << 0 << endl;
        return;
    }
    
    //This covers the case where only one path is built
    ll ans = calculateCost(id[1], id[n]);
    
    //pick all middle components and get the cost
    for (ll middle = 0; middle < cc.size(); middle++) {
        ll cost1 = calculateCost(id[1], middle);
        ll cost2 = calculateCost(middle, id[n]);
        ll totalcost = cost1 + cost2;
                
        ans = min(ans, totalcost);
    }
    

    cout << ans << endl;
    
}


int main()
{
    //init();
    
    //do all test cases
    
    ll t;
    cin >> t;
    
    while (t--) {
        solve();
    }

}
1 Like
#5

Have you tried stress testing it?

#6

I tried using the code in the usaco guide solution but it only passed the first 5 test cases.

#9

Please see the updated code on the same link provided.

#10

It worked. All I had to do was to make sure that I was binary searching on the larger component

1 Like