UASCO 3.3 Riding The Fence

This is a problem to find Euler Path of the graph. As this is an undirected graph, the Euler Path exists iff:

All graph vertices have even degree. Or,
All graph vertices have even degree, except two vertices have odd degree. And these two vertices will be start / end of the Euler Path.

This problem explicitly stated that the Euler Path existing, so no need to do the test to find out if the path exists or not. Instead, the job is to find out the exact path with the constraint that vertices should be sequenced in ascending order. There are a couple of well studied algorithm can solve the Euler Path finding problem, however for this test data set I find that we can just use DFS - which is not strictly a Euler Path finding solution because the DFS solution here alone can’t decide if an edge we are going to remove is a ‘bridge edge’ (which, if removed will never makes us traverse back to the graph). I think the solution here is not sound to cover any type of Euler Path, but is just lucky enough to pass the existing test data set.

#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stack>

using namespace std;

const int LIMIT = 501;
int F;
vector<int> degree(LIMIT, 0);
vector<vector<int>> adj(LIMIT, vector<int>(LIMIT, 0));
stack<int> path;

void dfs(int idx) {
    if (!degree[idx]) {
        path.push(idx);
        return;
    }
    
    for (int i = 1; i < LIMIT; ++i) {
        if (adj[idx][i] <= 0) continue;
        --adj[idx][i]; --adj[i][idx]; --degree[idx]; --degree[i];
        dfs(i);
    }
    path.push(idx);
}

int main() {
    ifstream fin("fence.in");
    ofstream fout("fence.out");
    fin >> F;
    int v1, v2;
    for (int i = 0; i < F; ++i) {
        fin >> v1 >> v2;
        adj[v1][v2]++; adj[v2][v1]++;
        degree[v1]++; degree[v2]++;
    }
    int start = 1;
    for(int i = 1; i < LIMIT; ++i){
        if(degree[i] % 2){
            start = i;
            break;
        }
    }

    dfs(start);
    
    while (!path.empty()) {
        cout << path.top() << endl;
        fout << path.top() << endl;
        path.pop();
    }
}

2016-11-23

USACO

USACO 3.2 Sweet Butter

This problem is essentially a shortest path problem: given a graph, find a single node in the graph (where we will put the butter) such that the combined distances from this graph node (the butter) to a set of graph nodes (the graph nodes where the cows are placed) is minimized.
The basic idea is for every node (pasture) in the graph, we calculate the shortest distances between this node and the rest of the nodes. Then for every node (pasture), we sum up the distances between itself and the pastures where cows are placed. The calculation of shortest paths between current pasture and the rest of pasture could be further optimized, as we only care about pasture with cows, so we can skip the pastures pairs where both pastures don’t have cows. But even without this optimization the code pass the test data set. The code use a slightly modified version of Dijkstra algorithm I posted earlier, otherwise there would be too much redundant computations that leads to timeout errors for large test data set.

I suspect this problem can also be solved using Bellmen-Ford or SFPA, and that would be a good exercise at some point in future…

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <queue>

using namespace std;

int N /* cows */, P /* pastures */, C /* paths */;
vector<int> c2p;// [to node index, edge weight] pair.
typedef std::pair<int, int> edge;
// [node index, distance to source] pair.
typedef std::pair<int, int> element;
vector<vector<edge>> graph;
vector<int> dist;
vector<bool> visited;

class compare {
public:
    bool operator()(const element&a, const element &b) {
        return a.second > b.second;
    }
};

void dijkstra(const vector<vector<edge>> &graph, int source) {
    std::fill(visited.begin(), visited.end(), false);
    std::fill(dist.begin(), dist.end(), INT_MAX);
    dist[source] = 0;
    priority_queue<element, vector<element>, compare> pq;
    pq.emplace(make_pair(source, 0));
    while (!pq.empty()) {
        int v = pq.top().first;
        pq.pop();
        if (visited[v]) continue;
        for (auto &edge : graph[v]) {
            int u = edge.first; // vertice u that connects to v.
            int w = edge.second; // weight of edge that connects u and v.
            if (visited[u]) continue;
            if (dist[v] + w < dist[u]) {
                dist[u] = dist[v] + w;
                pq.emplace(make_pair(u, dist[u]));
            }
        }
        visited[v] = true;
    }
}

int main() {
    ifstream fin("butter.in");
    ofstream fout("butter.out");

    fin >> N >> P >> C;
    c2p = vector<int>(N + 1, 0);
    graph = vector<vector<edge>>(C + 1, vector<edge>());
    dist = vector<int>(C + 1, INT_MAX);
    visited = vector<bool>(C + 1, false);

    for (int i = 1; i < N + 1; ++i) {
        fin >> c2p[i];
    }
    for (int i = 0; i < C; ++i) {
        int s, d, w;
        fin >> s >> d >> w;
        graph[s].emplace_back(make_pair(d, w));
        graph[d].emplace_back(make_pair(s, w));
    }

    long long ret = INT_MAX;
    for (int i = 1; i <= P; ++i) {
        long long ans = 0;
        dijkstra(graph, i);
        for (int j = 1; j <= N; ++j) {
            ans += dist[c2p[j]];
        }
        ret = std::min(ret, ans);
    }

    fout << ret << endl;
    cout << ret << endl;
}

2016-11-19

USACO

USACO 3.2 Magic Squares

Typical solution for ‘minimum’ or ‘maximum’ problems:

Greedy
Dynamic Programming
BFS

For this problem, it is not obvious about overlapping sub-problems so BFS is an obvious solution.
The tricky parts are:

How to encode the transforms (the A, B, and C).
How to test if a state has been explored.
How to perform backtracking once we have hit desired states.

I think this problem is very good on testing implementation skills, as the algorithm itself is not very complicated.

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <map>
#include <unordered_map>
#include <climits>
#include <sstream>
#include <queue>

using namespace std;

vector<vector<int>> tx = {
    {8,7,6,5,4,3,2,1}, // A
    {4,1,2,3,6,7,8,5}, // B
    {1,7,2,4,5,3,6,8}, // C
};

struct state {
    vector<int> val;
    state() {
        val = vector<int>(8, 0);
        std::iota(val.begin(), val.end(), 1);
    }
};

queue<state> q;
const int MAX_STATES = 40500;
vector<bool> visited(MAX_STATES, false);
// Stores state_hash:(previous state hash : transform index)
vector<vector<int>> trace(MAX_STATES, vector<int>(2, -1));
// Stores state_hash:transform index
vector<int> transforms(MAX_STATES, 0);
vector<int> factorial = {1, 1, 2, 6, 24, 120, 720, 5040};
// Expected state (read from input.).
vector<int> target(8, 0);

int steps;

int hashing(vector<int> state) {
    int sum = 1, t = 0;
    for (int i = 0; i < 7; ++i) {
        t = 0;
        for (int j = i + 1; j < 8; ++j) {
            if(state[j] < state[i]) ++t;
        }
        sum += t * factorial[7 - i];
    }
    return sum;
}

void bfs() {
    int hash = 0;
    trace[1][1] = 0;
    visited[1] = true;
    q.emplace(state());

    while(!q.empty()) {
        auto cur = q.front();q.pop();
        hash = hashing(cur.val);
        if(cur.val == target)
            break;
        for (int i = 0; i < 3; ++i) {
            state next;
            for (int j = 0; j < 8; ++j) {
                next.val[j] = cur.val[tx[i][j] - 1];
            }
            int next_state_hash = hashing(next.val);
            if (visited[next_state_hash]) continue;
            q.push(next);
            visited[next_state_hash] = true;
            trace[next_state_hash][0] = hash;
            trace[next_state_hash][1] = i;
        }
    }

    while (trace[hash][0] != -1) {
        transforms[steps]= trace[hash][1];
        hash = trace[hash][0];
        ++steps;
    }
}

void output(ofstream &fout) {
    cout << steps << endl;
    fout << steps << endl;
    for(int i = steps - 1; i >= 0; --i) {
        char c = transforms[i] + 'A';
        cout << c; fout << c;
    }

    fout << endl; cout << endl;
}

int main() {
    ifstream fin("msquare.in");
    ofstream fout("msquare.out");
    for (int i = 0; i < 8; ++i) {
        fin >> target[i];
    }
    bfs();
    output(fout);
}