USACO 3.3 Riding the Fences – CPP solution

A relatively simple problem. We just need to implement the algorithm to find an Eurlerian tour/path. Because I had decided to use an adjacency list to store the graph, I also had to determine a fast way to find the current node in the list. To do so, I have implemented a binary search. Time complexity approximation: O(logn * n).

#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 502

FILE * in, *out;
int n;
vector<int> list[MAX];
stack<int> ans;

bool comparator(int a,int b) {
    return a>b;
}

void remove(int index, int element) {
    int l = 0;
    int r = list[index].size()-1;
    int mid;
    while (l<=r) {
        mid = (l+r)/2;
        if (list[index][mid]<element) {
            r = mid-1;
        } else if (list[index][mid]>element) {
            l = mid+1;
        } else {
            list[index].erase(list[index].begin()+mid);
            return;
        }
    }
}

void euler(int start) {
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int index = s.top();
        if (list[index].size()==0) {
            s.pop();
            ans.push(index);
        } else {
            int cpy = list[index].back();
            s.push(cpy);
            list[index].pop_back();
            remove(cpy,index);
        }
    }
}

int determine_start() {
    int cntOdd = 0;
    int odd[2] = {MAX};
    int minEven = MAX;
    for (int i = 0; i < MAX; ++i) {
        if (list[i].size()==0) continue;
        if (list[i].size()%2==1) {
            odd[cntOdd]=i;
            if (cntOdd+1>2) {
                return -1;
            }
            ++cntOdd;
        } else if (minEven == MAX) {
            minEven = i;
        }
    }
    if (cntOdd == 0) return minEven;
    return min(odd[0],odd[1]);
}

int main() {
    in = fopen("fence.in","r");
    fscanf(in,"%d",&n);
    int a,b;
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d%d",&a,&b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
    for (int i = 0; i < MAX; ++i) {
        sort(list[i].begin(),list[i].end(),comparator);
    }
    fclose(in);
    euler(determine_start());
    out = fopen("fence.out","w");
    while (!ans.empty()) {
        fprintf(out,"%dn",ans.top());
        ans.pop();
    }
    fclose(out);
    return 0;
}

USACO Magic Squares – CPP Solution

This is a relatively easy problem, but we still need to make some “optimizations” or at least to have a good idea how to make fast queries/checks.
It is similar to the lamp problem from USACO where we could have used either bfs or a trick with pre-computation. However, here we can use only BFS. There aren’t a lot of possible permutations (just 8!).
We can just start the bfs and memorize every possible state (square) we have made. However, we will have to check whether we have made that state previously. There are a few ideas:
– Use a red-black tree. We could the set<> container.
– Use the map container where the key is going to be a string.
– Use an array whether the index is going to be the state. The biggest state which can be generated is 87654321. However, it would be really hard to go from one state to another.
We will stick to the idea about using the map container with a string for a key.

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

FILE * in, *out;

#define psb pair<string,bool>
#define pss pair<string,string>

map<string,bool> table;

string state;

string move(char c, string s) {
    if (c=='A') {
        char tmp;
        for (int i = 0; i < 4; ++i) {
            tmp = s.at(i);
            s.replace(i,1,1,s.at(i+4));
            s.replace(i+4,1,1,tmp);
        }
    } else if (c=='B') {
        char tmp = s.at(3);
        char tmp2;
        for (int i = 0; i < 4; ++i) {
            tmp2 = s.at(i);
            s.replace(i,1,1,tmp);
            tmp = tmp2;
        }
        tmp = s.at(7);
        for (int i = 4; i < 8; ++i) {
            tmp2 = s.at(i);
            s.replace(i,1,1,tmp);
            tmp = tmp2;
        }
    } else {
        char tmp[4];
        tmp[0] = s.at(1);
        tmp[1] = s.at(2);
        tmp[2] = s.at(5);
        tmp[3] = s.at(6);
        s.replace(2,1,1,tmp[0]);
        s.replace(6,1,1,tmp[1]);
        s.replace(5,1,1,tmp[3]);
        s.replace(1,1,1,tmp[2]);
    }
    return s;
}

string solve() {
    queue<pss> q;
    string tmp;
    q.push(pss("12348765",tmp));
    int cnt = 0;
    while (!q.empty()) {
        pss current = q.front();
        q.pop();
        ++cnt;
        if (current.first == state) {
            return current.second;
        }
        for (char i = 'A'; i<='C'; ++i) {
            tmp = move(i,current.first);
            if (table.find(tmp) == table.end()) {
                table.insert(psb(tmp,true));
                string moves = current.second;
                moves.append(1,i);
                q.push(pss(tmp,moves));
            }
        }
    }
    return "";
}

int main() {
    in = fopen("msquare.in","r");
    int b;
    state = "00000000";
    for (int i = 0; i < 8; ++i) {
        fscanf(in,"%d",&b);
        int index;
        if (i<4) {
            index = i;
        } else {
            index = 7-(i-4);
        }
        state.replace(index,1,1,((char)(b+'0')));
    }
    /*
    string sol = "BCABCCB";
    cout << state << endl;
    for (int i = 0; i < 7; ++i) {
        state = move(sol.at(i),state);
        cout << state << endl;
    }
    return 0;
    */

    //cout << move('A',state) << endl << move('B',state) << endl << move('C',state) << endl;
    //return 0;

    fclose(in);
    out = fopen("msquare.out", "w");
    string ans = solve();
    int sz = ans.length();
    char print[61];
    int index = 0;
    fprintf(out,"%dn",sz);
    if (sz == 0) {
        fprintf(out,"n");
    }
    for (int i = 0; i < sz; ++i) {
        print[index] = ans.at(i);
        if (index==60 || i+1==sz) {
            if (index!=60) {
                print[index+1] = '\0';
            }
            index = 0;
            fprintf(out,"%sn",print);
        } else {
            ++index;
        }
    }
    fclose(out);
    return 0;
}

USACO 3.2 Spinning Wheels – CPP solution

I am not quite sure whether there is a faster solution. However, the key idea is that at most after 360 seconds the wheels would be at their initial position.
So, we just check the first 360 seconds and see whether we have any “collisions” (overlaps).

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

#define pii pair<int,int>
#define MAX 361

struct element {
    int v,w;
    pii el[5];
} el[5];

void move() {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < el[i].w; ++j) {
            el[i].el[j].first = (el[i].el[j].first+el[i].v)%360;
            el[i].el[j].second = (el[i].el[j].second+el[i].v)%360;
        }
    }
}

bool exists(int a, pii b) {
    if (a >= b.first && a <= b.second) return true;
    if (b.second<b.first && (a>=b.first || a<=b.second)) return true;
    return false;
}

bool passLight(pii a, pii b, pii c, pii d, pii e) {
    int to=0;
    if (a.second < a.first) {
        to = 360;
    }
    for (int i = a.first; i<=(a.second+to);++i) {
        if (exists(i%360,b) && exists(i%360,c) && exists(i%360,d) && exists(i%360,e)) return true;
    }
    return false;
}

bool check() {
    for (int i = 0; i < el[0].w; ++i) {
        for (int j = 0; j < el[1].w; ++j) {
            for (int k = 0; k < el[2].w; ++k) {
                for (int z = 0; z < el[3].w; ++z) {
                    for (int q = 0; q < el[4].w; ++q) {
                        if (passLight(el[0].el[i],el[1].el[j],el[2].el[k],el[3].el[z],el[4].el[q])) return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    ifstream in("spin.in");
    for (int i = 0; i < 5; ++i) {
        in >> el[i].v >> el[i].w;
        int a,b;
        for (int j = 0; j < el[i].w; ++j) {
            in >> a >> b;
            el[i].el[j] = pii(a,(a+b)%360);
        }
    }
    in.close();
    ofstream out("spin.out");
    int ans = MAX;
    for (int i = 0; i < MAX; ++i) {
        if (check()) {
            ans = i;
            break;
        } else {
            move();
        }
    }
    if (ans==MAX) {
        out << "none" << endl;
    } else {
        out << ans << endl;
    }
    out.close();
}