USACO 3.2 Sweet Butter – CPP solution

This problem seems relatively straightforward, but we need a few optimizations to pass it:
– Floyd would not work since P^3 is too much.
– We could use Dijkstra. We will find what is the shortest path from every cow to every pasture. Normally this gives us N*P*P. Is it fast enough? No -> this is 320000000 iterations. Can we improve it? Use a heap or a red-black tree.
– heap vs red-black tree. Usually, the time complexity for the operations is the same, though the heap usually runs a little faster. We can use a heap by using the priority_queue container in c++ or access an implementation of a red-black tree using the set container. Personally, I have tried the priority_queue and it have not run enough fast to past the last test. I was able to pass it with a set container.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define INF 9999999
#define pii pair<int,int>

FILE *in,*out;

int n,p,c;

int cows[501];
int g[802][802];

struct order2 {
 bool operator() (const pii &a, const pii &b) {
    if (a.second!= b.second) return a.second < b.second;
    return a.first < b.first;

 }
};


int total[802] = {0};

int dist[802];
int used[802];

void dijkstra(int k) {
    //priority_queue<pii,vector<pii>,order> pq;
    set<pii,order2> pq;
    for (int i = 1; i<= p; ++i) {
        dist[i] = g[k][i];
        used[i] = 0;
    }
    pq.insert(pii(k,0));
    int cnt = 0;
    while(!pq.empty()) {
        pii node = *pq.begin();
        pq.erase(pq.begin());
        if (used[node.first]==1) continue;
        used[node.first] = 1;
        ++cnt;
        if (cnt==p) break;
        for (int i = 1; i<= p; ++i) {
            if (dist[i]>=node.second+g[node.first][i] && g[node.first][i]<INF && used[i]==0) {
                dist[i]=node.second+g[node.first][i];
                pq.insert(pii(i,dist[i]));
            }
        }
    }
    for (int i = 1; i<= p; ++i) {
        //cout << dist[i] << endl;
        total[i]+=dist[i];
    }
}

int solve() {
    int ans = INF;
    for (int i = 0; i< n; ++i) {
        dijkstra(cows[i]);
    }
    for (int i = 1; i<= p; ++i) {
        ans = min(ans,total[i]);
    }
    return ans;
}

int main() {
    in = fopen("butter.in","r");
    fscanf(in,"%d%d%d",&n,&p,&c);
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d",&cows[i]);
    }
    int a,b,k;
    for (int i = 1; i<= p; ++i) {
        for (int j = i+1; j<=p; ++j) {
            g[i][j] = g[j][i] = INF;
        }
    }
    for (int i = 0; i < c; ++i) {
        fscanf(in,"%d%d%d",&a,&b,&k);
        g[a][b] = min(g[a][b],k);
        g[b][a] = g[a][b];
    }
    for (int i = 1; i<=p; ++i) g[i][i] = 0;
    fclose(in);

    out = fopen("butter.out","w");
    fprintf(out,"%dn",solve());
    fclose(out);
    return 0;
}

USACO 3.2 Feed Ratios – CPP solution

We have just 101^3 possible mixture of ratios. We could just generate every solution and print the smallest one.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;



ifstream in;
ofstream out;

struct item {
    int a,b,c;
    int sum;
};

#define pii pair<item,int>
#define MAX 30001

item q[4];
item best;
int bestI,bestJ,bestR,bestSum=MAX,bestRes;

int euclid (int a, int b) {
    return b == 0 ? a : euclid (b,a%b);
}

int ok(item tmp) {
    double a,b,c;
    if (q[0].a == 0) {
        if (tmp.a!=0) return -1;
        a = -2;
    } else {
        a =  tmp.a/q[0].a;
    }
    if (q[0].b == 0) {
        if (tmp.b!=0) return -1;
        b = -2;
    } else {
        b =  tmp.b/q[0].b;
    }
    if (q[0].c == 0) {
        if (tmp.c!=0) return -1;
        c = -2;
    } else {
        c =  tmp.c/q[0].c;
    }
    if ((a==-2 || tmp.a/a == q[0].a) && (b==-2 || tmp.b/b == q[0].b) && (c==-2 || tmp.c/c == q[0].c) && (a==b || a==-2 || b ==-2) && (b==c || b==-2 || c==-2)) return max(a,max(b,c));
    return -1;
}


int main() {
    in.open("ratios.in");
    for (int i = 0; i < 4; ++i) {
        in >> q[i].a >> q[i].b >> q[i].c;

        q[i].sum = q[i].a+q[i].b+q[i].c;
    }

    item sum;
    for (int i = 0; i <= 100; ++i) {
        sum.a = q[1].a*i;
        sum.b = q[1].b*i;
        sum.c = q[1].c*i;
        for (int j = 0; j <= 100; ++j) {
            sum.a += q[2].a*j;
            sum.b += q[2].b*j;
            sum.c += q[2].c*j;
            for (int r = 0; r <= 100; ++r) {
                sum.a += q[3].a*r;
                sum.b += q[3].b*r;
                sum.c += q[3].c*r;
                int res = ok(sum);
                if (res!=-1 && i+j+r<bestSum) {
                    if (res==-2) {
                        res = 0;
                    }
                    bestI = i;
                    bestJ = j;
                    bestR = r;
                    bestSum = i+j+r;
                    bestRes = res;
                }
                sum.a -= q[3].a*r;
                sum.b -= q[3].b*r;
                sum.c -= q[3].c*r;
            }
            sum.a -= q[2].a*j;
            sum.b -= q[2].b*j;
            sum.c -= q[2].c*j;
        }
    }
    in.close();
    out.open("ratios.out");
    if (bestSum==MAX) {
        out << "NONE" << endl;
    } else {
        out << bestI << " " << bestJ << " " << bestR << " " << bestRes << endl;
    }
    out.close();
    return 0;
}

The problem could be also solved with linear algebra.

USACO 3.1 Agri-Net – CPP Solution

A basic minimum spanning tree (MST) problem. I have used Prim’s algorithm to solve it.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define MAX 9999999

ifstream in;
ofstream out;

int n;

int g[101][101] = {0};
int used[101] = {0};

int ans = 0;

void prim() {
    used[0] = 1;
    while (1) {
        int l = 9999999;
        int node = -1;
        for (int i = 0; i < n; ++i) {
            if (used[i]==1) {
                for (int k = 0; k < n; ++k) {
                    if (g[i][k]>0 && used[k]!=1 && g[i][k]<l) {
                        node = k;
                        l = g[i][k];
                    }
                }
            }
        }
        if (node==-1) break;
        used[node] = 1;
        ans += l;
    }
}

int main() {
    in.open("agrinet.in");
    in >> n;
    int a;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            in >> a;
            g[i][j] = g[j][i] = a;
        }
    }
    in.close();
    prim();
    out.open("agrinet.out");
    out << ans << endl;
    out.close();
    return 0;
}

USACO 3.1 Score Inflation – CPP Solution

A really basic DP problem. The same as the 0-1 Knapsack problem. I believe I have seen it before on USACO.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define MAX 9999999

#define pii pair<int,int>

FILE * in, *out;

int m,n;
int dp[10001] = {0};
vector<pii> q;
int ans = 0;

int main() {
    in = fopen("inflate.in","r");
    fscanf(in,"%d%d",&m,&n);
    int a,b;
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d%d",&a,&b);
        q.push_back(pii(a,b));
        dp[b] = a;
    }
    fclose(in);
    int sz = q.size();
    for (int i = 0; i<m; ++i) {
        if (dp[i]>0) {
            for (int j = 0; j < sz; ++j) {
                if (i+q[j].second <= m) {
                    if (dp[i+q[j].second] < (dp[i] + q[j].first)) dp[i+q[j].second] = dp[i] + q[j].first, ans = max(ans,dp[i+q[j].second]);
                }
            }
        }
    }

    out = fopen("inflate.out","w");
    fprintf(out,"%dn",ans);
    fclose(out);
    return 0;
}

USACO 2.4 The Tamworth Two – CPP solution

A relatively basic problem, which for the given constraints could be solved by simulation of the moves of the farms and the cows. However, if the matrix had been bigger, we could not have been able to solve it in this way. What is the other idea to solve the problem. At some point, the object (farmer or cow) will get to its start point again facing to the north. This mean that we would have found a cycle and the length of the cycle. For instance, in the first sample we have a cycle of 49 moves. Which means that the farmer will be at the same place every 49 moves. The cows for example would be at the same place every 77 moves. If we find, that both objects are at some point at a given place, then they are bound to meet there at some point.
Let us have the equation: 49*x + p = 77*y = z, where p and z are the number of moves till we get to that place.
We could do some math and rearrange it to 49x – 77y = z-p which is basically a linear diophantine equation. We just have to find such integers x and y, so that we have a correct answer. I won’t get in details, but we will have to use Euclid fast gcd algorithm. I haven’t coded that since a simple simulation is fast enough:

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define MAX 99999

ifstream in;
ofstream out;

char g[11][11];

int xp[4] = {-1,0,1,0};
int yp[4] = {0,1,0,-1};

bool ok(int x, int y) {
    if (x<0 || y < 0 || x>=10 || y >=10 || g[x][y]=='*') return false;
    return true;
}

int coordN[2][2];
int dir[2] = {0};

void move(int obj) {
    int nx = xp[dir[obj]] + coordN[obj][0];
    int ny = yp[dir[obj]] + coordN[obj][1];
    if (ok(nx,ny)) {
        coordN[obj][0] = nx;
        coordN[obj][1] = ny;
    } else {
        dir[obj] = (dir[obj]+1)%4;
    }
}

int ans = MAX;

int main() {
    in.open("ttwo.in");
    int fX,fY,cX,cY;
    for (int i = 0; i < 10; ++i) {
        for (int j = 0; j < 10; ++j) {
            in >> g[i][j];
            if (g[i][j]=='n') {
                --j;
                continue;
            }
            if (g[i][j]=='F') coordN[0][0] = i, coordN[0][1] = j;
            if (g[i][j]=='C') coordN[1][0] = i, coordN[1][1] = j;
        }
    }
    in.close();
    out.open("ttwo.out");
    ans = 0;
    while (ans < MAX) {
        move(0);
        move(1);
        ++ans;
        if (coordN[0][0] == coordN[1][0] && coordN[0][1]==coordN[1][1]) {
            break;
        }

    }
    if (ans == MAX) ans = 0;
    out << ans << endl;
    out.close();
    return 0;
}

USACO 2.4 Cow Tours – CPP solution

It is a rather interesting problem with a little catch. Probably, if you’re reading this, you have had a problem with test NO. 7 getting a smaller output than the correct answer. Let us think of a solution:
We are talking about shortest paths. We will definitely need an algorithm of that sort. We will have to know the shortest path between all nodes in all the components. Floyd-Warshall’s algorithm would do just fine, though we could code Dijkstra with a priority queue to get a total time complexity of O(n^2 * lgn) The input constraints are rather small and Floyd would run enough fast.
What’s the maximum value we expect as an output. That would be 141421.0. Everything is ok till now. However, after coding the solution we might get a wrong answer for test No 7 (at least I got a wrong answer -> an answer smaller than the correct one). How could that be if our algorithm is correct for every other case. As it is stated in the task, the fields could intersect or even there could be nested fields. We will have to compare also the biggest diameter for every field with the diameter of the combined fields.

#include <iostream>
#include <cstdio>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

FILE * in, *out;

#define pii pair<int,int>
#define NO_PATH 9999999.0

int n;
pii v[151];
char g[151][151];
double d[151][151];
double r[151] = {0.0};
vector<int> cmp[151];
double cmpD[151] = {0.0};
int used[151];
int cmpSize = 0;

double dist(int i, int j) {
    return sqrt((v[i].first-v[j].first)*(v[i].first-v[j].first) + (v[i].second-v[j].second)*(v[i].second-v[j].second));
}

void floyd() {
    for (int i = 0; i < n; ++i) d[i][i] = 0.0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (d[j][k] > d[j][i] + d[i][k]) {
                    d[j][k] = d[j][i] + d[i][k];
                    d[k][j] = d[j][k];
                }
            }
        }
    }
}

double solve() {
    floyd();
    for (int i = 0; i < n; ++i) {
        if (used[i]!=1) {
            used[i] = 1;
            cmp[cmpSize].push_back(i);
            for (int j = 0; j < n; ++j) {
                if (d[i][j]!=NO_PATH && used[j]!=1) {
                    used[j] = 1;
                    cmp[cmpSize].push_back(j);
                }
            }
            ++cmpSize;
        }
    }
    for (int i = 0; i < cmpSize; ++i) {
        int iSz = cmp[i].size();
        for (int k = 0; k < iSz; ++k) {
            for (int p = k+1; p < iSz; ++p) {
                //if (k==p) continue;
                r[cmp[i][k]] = max(r[cmp[i][k]],d[cmp[i][k]][cmp[i][p]]);
                r[cmp[i][p]] = max(r[cmp[i][p]],d[cmp[i][k]][cmp[i][p]]);
                cmpD[i] = max(cmpD[i],max(r[cmp[i][p]],r[cmp[i][k]]));
            }
            //cout << cmp[i][k] << " " << r[cmp[i][k]] << " " << sqrt(r[cmp[i][k]]) << endl;
        }
    }
    for (int i = 0; i < cmp[0].size(); ++i) {
        //cout << r[cmp[0][i]] + r[cmp[1][0]] + dist(cmp[0][i],cmp[1][0]) << endl;
    }
    double ans = 200000.0;
    for (int i = 0; i < cmpSize; ++i) {
        int iSz = cmp[i].size();
        for (int j = i+1; j < cmpSize; ++j) {
            int jSz = cmp[j].size();
            for (int k = 0; k < iSz; ++k) {
                for (int p = 0; p < jSz; ++p) {
                    ans = min(ans,max(r[cmp[i][k]] + r[cmp[j][p]] + dist(cmp[i][k],cmp[j][p]),max(cmpD[i],cmpD[j])));
                }
            }
        }
    }
    //cout << ans << endl;
    return ans;
}

int main() {
    in = fopen("cowtour.in","r");
    fscanf(in,"%d",&n);
    int a,b;
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d%d",&a,&b);
        v[i] = pii(a,b);
    }
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%s",&g[i]);
        for (int j = 0; j < n; ++j) {
            if (g[i][j]=='1') {
                d[i][j] = dist(i,j);
                d[j][i] = d[i][j];
            } else {
                d[i][j] = NO_PATH;
                d[j][i] = NO_PATH;
            }
        }
    }
    fclose(in);
    out = fopen("cowtour.out","w");
    fprintf(out,"%.6fn",solve());
    fclose(out);
    return 0;
}

As you have probably noticed, I don’t need to compute the sets of connected components. Anyway, with or without computing them, the time complexity is still the same -> O(n^3).

USACO 2.4 Overfencing – CPP solution

This solution is a simple BFS problem. We start a BFS from every exit and find the distance to every possible position. After we have run the two BFSs, we just check every node what is the minimum distance to one of the exits. After selecting the best exits to every node, we select the worst case (the maximum optimized distance). The tricky part is how to read the input data. We will use getline and check whether there aren’t any empty spaces at the end (exits).

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

ifstream in;
ofstream out;

#define pii pair<int,int>
#define ppp pair<pii,pii>

vector<pii> ex;

int w,h;

char g[203][203];

int used[2][203][203] = {0};

int x[4] = {0,0,-1,1};
int y[4] = {-1,1,0,0};

bool isBorder(int i, int j) {
    if (i == 0 || j == 0 || i == h-1 || j == w-1) return true;
    return false;
}

bool ok(int i, int j, int k) {
    if (i < 0 || j < 0 || i >= h || j >= w) return false;
    if (used[k][i][j]>0) return false;
    if ((int)g[i][j] == 32) return true;
    return false;
}

void print() {
    for (int i = 0; i < h; ++i) {
        cout << g[i] << endl;
    }
    cout << endl;
}

void bfs(int k) {
    queue<ppp> q;
    q.push(ppp(ex[k],pii(-1,-1)));
    used[k][ex[k].first][ex[k].second] = 1;
    int nx,ny;
    ppp node,tmp;
    while (!q.empty()) {
        node = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            nx = node.first.first + x[i];
            ny = node.first.second + y[i];
            if (ok(nx,ny,k)) {
                tmp = ppp(pii(nx,ny),node.first);
                used[k][nx][ny] = used[k][node.first.first][node.first.second] + 1;
                q.push(tmp);
            }
        }
    }
}

int main() {
    in.open("maze1.in");
    in >> w >> h;
    h = 2*h + 1;
    w = 2*w + 1;

    int c = 0;
    in.getline(g[0],w);
    for (int i = 0; i < h; ++i) {
        in.getline(g[i],w+1);
        int l = strlen(g[i]);
        if (l < w) {
            for (int j = l; j < w; ++j) g[i][j] = (char)32;
        }
        for (int j = 0; j < w; ++j) {
            if ((int)g[i][j] == 32 && isBorder(i,j)) {
                ex.push_back(pii(i,j));
            }
        }
    }
    in.close();
    for (int i = 0; i < ex.size(); ++i) {
        bfs(i);
    }
    int ans = 0;
    for (int i = 1; i < h-1; ++i) {
        for (int j = 1; j<w-1; ++j) {
            ans = max(ans,min(used[0][i][j],used[1][i][j]));
        }
    }
    out.open("maze1.out");
    out << ans/2 << endl;
    out.close();
}

USACO 2.3 Concom – CPP solution

Some observations:
– Company A = Company B, when A or B have 100% shares of the opposite company
– We will use double numbers for easier computations.
The solutions to this problem is very similar to the Floyd algorithm. Let us say we are looking at the pair of companies A and B. If A controls B or B controls A, we don’t have a reason to consider them -> we will just move one with the other pairs. If they don’t have the latter relation, we will just try to find one using a “middle” node. For example, let the middle node be C. If A controls C and C has some percent of shares at the B company, then A also has that share at B. We will just check every other node and sum the shares. If the percentage is >=50, then A controls B.
A little problem. Unlike the Floyd algorithm, we do some checks in order to do calculations. Basically, for some inputs this idea would not work, because if we consider the nodes A and B and there aren’t enough daughter-companies of A at this stage which have shares at B, then we would not find any relation between the two companies. However, at the end of the checks we would have probably added some companies (at least one) to our relation list. Basically, we will have to run our algorithm p times, where p denotes the biggest index of the companies.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

FILE * in, * out;

int n;
int q = 0;
double g[101][101] = {0.0};
int added[101][101][101] = {0};

void solve () {
    for (int m = 1; m<=q; ++m) {
    for (int i = 1; i<=q; ++i) {
        for (int j = 1; j <= q; ++j) {
            if (g[i][j]>=0.5) continue;
            for (int k = 1; k <= q; ++k) {
                if (g[i][k]>=0.5 && added[i][k][j]==0) {
                    added[i][k][j] = 1;
                    g[i][j]+=g[k][j];
                    if (g[i][j]>1.0) g[i][j] = 1.0;
                }
            }
        }
    }
    }

}

int main() {
    in = fopen("concom.in","r");
    int a,b,c;
    fscanf(in,"%d",&n);
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d%d%d",&a,&b,&c);
        if (g[a][b]==0.0) g[a][b] = ((double)c)/100.0;
        if (c==100) {
            g[b][a] = 1.0;
        }
        q = max(q,max(a,b));
    }
    fclose(in);
    out = fopen("concom.out","w");
    solve();
    for (int i = 1; i <= q; ++i) {
        for (int j = 1; j <= q; ++j) {
            if (i==j) continue;
            //cout << i << " " << j << " " << g[i][j] << endl;
            if (g[i][j]>=0.5) {
                if(g[i][j]!=1.0 || n==1) g[i][j] = g[j][i] = 0.0;
                fprintf(out,"%d %dn",i,j);
            }
        }
    }
    fclose(out);
}

USACO 2.3 Money – CPP solution

Probably the easiest problem since first problem in Chapter 1. This problem is very similar to the 1-0 Knapsack problem.
We will also use dynamic programming to solve this one. We will store the possible solutions in an array dp. So, if dp[x]>0 it means that we can more than 0 solutions to make the sum x. Then we will add every possible coin to x in order to generate bigger sums.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

ifstream in;
ofstream out;

long long dp[10001] = {0};
int n,q;
vector<int> p;

int main() {
    in.open("money.in");
    in >> n >> q;
    int tmp;
    for (int i = 0; i < n; ++i) {
        in >> tmp;
        p.push_back(tmp);
    }
    in.close();
    out.open("money.out");
    dp[0] = 1;
    for (int i = 0; i < p.size(); ++i) {
        for (int k = 0; k < q; ++k) {
            if (dp[k]>=1 && k+p[i]<=q) {
                dp[k+p[i]] += dp[k];
            }
        }
    }
    out << dp[q] << endl;
    out.close();
}