2019 USACO Open Silver Problem 3

Problems and Contests
#1

I am working on this problem : http://www.usaco.org/index.php?page=viewproblem2&cpid=944

My code works on the first 6 test cases but it times out on the last 4. Can someone show me how to make this code more efficient?

Strategy: I am using a DFS to find all the cows in a group. And I store the cow numbers of all the cows in the group. Then I calculate the perimeter. Also, to make this more efficient I remove all the cows that I visited in the DFS because a DFS on the other cows in the same system would result in the exact same perimeter.

Code:
const int MN = 1e5 + 10;
vector adj_list[MN];
bool visited[MN];
int N, M;
vector current;

void dfs(long node) {
visited[node] = true;
for (long u:adj_list[node]) {
if (!visited[u]) {
current.push_back(u);
dfs(u);
}
}
}

int main() {
freopen(“fenceplan.in”, “r”, stdin);
freopen(“fenceplan.out”, “w”, stdout);
cin >> N >> M;
map<long, pair<long, long>> inputs;
for (int i = 0; i < N; i++) {
long x, y;
cin >> x >> y;
inputs.insert({i + 1, make_pair(x, y)});
}
for (int i = 0; i < M; i++) {
int cow1, cow2;
cin >> cow1 >> cow2;
adj_list[cow1].push_back(cow2);
adj_list[cow2].push_back(cow1);
}

vector<int> cows;
for (int i = 1; i <= N; i++) {
    cows.push_back(i);
}
long ans = 1000000000000;
long x, y;
long minX = 100000000;
long miny = 1000000000;
long maxX = -1000000000;
long maxY = -1000000000;

while (cows.size() != 0) {


    current.clear();
    current.push_back(cows[0]);

    dfs(cows[0]);


    minX = 100000000;
    miny = 1000000000;
    maxX = -1000000000;
    maxY = -1000000000;
    for (int i = 0; i < current.size(); i++) {

        cows.erase(std::remove(cows.begin(), cows.end(), current[i]), cows.end());
        x = inputs[current[i]].first;
        y = inputs[current[i]].second;
        minX = min(x, minX);
        miny = min(y, miny);
        maxX = max(x, maxX);
        maxY = max(y, maxY);

    }

    ans = min(ans, 2 * (maxX - minX) + 2 * (maxY - miny));
}
cout << ans;
return 0;

}

how can I make this faster?

#2 
const int MN = 1e5 + 10;
vector adj_list[MN];
bool visited[MN];
int N, M;
vector current;

void dfs(long node) {
    visited[node] = true;
    for (long u:adj_list[node]) {
        if (!visited[u]) {
            current.push_back(u);
            dfs(u);
        }
    }
}

int main() {
    freopen("fenceplan.in", "r", stdin);
    freopen("fenceplan.out", "w", stdout);
    cin >> N >> M;
    map<long, pair<long, long>> inputs;
    for (int i = 0; i < N; i++) {
        long x, y;
        cin >> x >> y;
        inputs.insert({i + 1, make_pair(x, y)});
    }
    for (int i = 0; i < M; i++) {
        int cow1, cow2;
        cin >> cow1 >> cow2;
        adj_list[cow1].push_back(cow2);
        adj_list[cow2].push_back(cow1);
    }

    vector<int> cows;
    for (int i = 1; i <= N; i++) {
        cows.push_back(i);
    }
    long ans = 1000000000000;
    long x, y;
    long minX = 100000000;
    long miny = 1000000000;
    long maxX = -1000000000;
    long maxY = -1000000000;

    while (cows.size() != 0) {


        current.clear();
        current.push_back(cows[0]);

        dfs(cows[0]);


        minX = 100000000;
        miny = 1000000000;
        maxX = -1000000000;
        maxY = -1000000000;
        for (int i = 0; i < current.size(); i++) {

            cows.erase(std::remove(cows.begin(), cows.end(), current[i]), cows.end());
            x = inputs[current[i]].first;
            y = inputs[current[i]].second;
            minX = min(x, minX);
            miny = min(y, miny);
            maxX = max(x, maxX);
            maxY = max(y, maxY);

        }

        ans = min(ans, 2 * (maxX - minX) + 2 * (maxY - miny));
    }
    cout << ans;
    return 0;
}

FTFY.

#3

Also, do you know the complexity of your solution? Why it’s TLE-ing shouldn’t be too hard to figure out.

#4

Here is my solution for this problem…

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;

vector<pi> cows(100000);
vector<int> adj[100000];
bool visited[100000];

int minX, minY, maxX, maxY;

void DFS(int node){
    if(visited[node]){
        return;
    }
    minX = min(cows[node].first, minX),
    maxX = max(cows[node].first, maxX),
    minY = min(cows[node].second, minY),
    maxY = max(cows[node].second, maxY);
    visited[node] = true;
    for(int connected: adj[node]){
        DFS(connected);
    }
}

int main(){
    freopen("fenceplan.in", "r", stdin);
    freopen("fenceplan.out", "w", stdout);
    int n, m; cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> cows[i].first >> cows[i].second;
    }
    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int perimeter = 400000000;
    for(int i=0; i<n; i++){
        if(!visited[i]){
            minX = cows[i].first, 
            maxX = cows[i].first,
            minY = cows[i].second, 
            maxY = cows[i].second;
            DFS(i);
            perimeter = min(perimeter, 2 * (maxX - minX) + 2 * (maxY - minY));
        }
    }
    cout << perimeter << endl;
}

The reason you get TLE is that the solution should be O(N + M). However, you made it an O(N^2 + M) solution, which doesn’t satisfy the problem constraints…

You should rethink your logic. Also, make sure to reformat your code…

#5

You should just run a DFS for each node if not visited. Find the minx, maxx, miny, miny. This will create a box and then your done.

#6

Which is exactly the logic of my code…

#7

The logic u provided could be wrong. What if (maxx - minx) is at its minimum but (maxy - miny) is super large. That won’t work. Instead, you should compute the maximum perimeter, rather than finding each individual component…

#8

No, my logic was simplified greatly, but I can put my code if u want. Its correct.

#9

It should be the minx, maxx, miny, maxy of the current connected component, though.

#10

Yeah that’s what I put in my code. Sorry if I didn’t specify in this chat.