USACO 2.3 Controlling Companies

This is a search problem that can be solved using brutal force DFS. We first have a pass to initialize the states of companies’ controlling states by bootstrapping controlling companies and controlled companies, and also gather company share statistics for each companies. Then we have a second pass to update the global control state where for each company A, if it controls company B (initialized in first pass by calculating if A has over 50% shares of B), then A should also have same number shares for each company C that company B has shares in. This process continues and the global state should converge and reach a fixed state, as for each company, we will do DFS for every other company only once.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;

int N;
const int C = 100;

int main() {
    ifstream fin("concom.in");
    ofstream fout("concom.out");
    fin >> N;
    vector<vector<pair<int, int>>> nodes(C + 1, vector<pair<int,int>>(0));
    int f, c, p;
    for (int i = 0; i < N; ++i) {
        fin >> f >> c >> p;
        nodes[f].push_back(make_pair(c, p));
    }
    
    vector<unordered_map<int, int>> map(C + 1, unordered_map<int, int>());
    vector<set<int>> result(C + 1, set<int>());
    vector<bool> visited(C + 1, false);
    
    for (int i = 1; i <= C; ++i) {
        for (auto &pair : nodes[i]) {
            map[i][pair.first] += pair.second;
            if (pair.second <= 50) {
                continue;
            }
            result[i].insert(pair.first);
        }
    }
    
    for (int i = 1; i <= C; ++i) {
        std::fill(visited.begin(), visited.end(), false);
        stack<int> s;
        for (auto &c : result[i]) {
            s.push(c);
        }
        while (!s.empty()) {
            int c = s.top();
            s.pop();
            if (visited[c]) continue;
            for (auto &cc : nodes[c]) {
                map[i][cc.first] += cc.second;
                if (map[i][cc.first] > 50) {
                    result[i].insert(cc.first);
                    s.push(cc.first);
                }
            }
            visited[c] = true;
        }
    }
    
    for (int i = 1; i <= C; ++i) {
        if (result[i].empty()) continue;
        for (auto iter = result[i].begin(); iter != result[i].end(); ++iter) {
            if (i == *iter) continue;
            fout << i << " " << *iter << endl;
        }
    }
}

2016-09-26

USACO

USACO 2.3 Money System

Very classic DP problem.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
int COINS;
vector<long long> dp(100001, 0);
vector<long> coins;
void compute() {
    dp[0] = 1;
    for (int i = 0; i < COINS; ++i) {
        for (int j = coins[i]; j <= N; ++j) {
            dp[j] += dp[j - coins[i]];
        }
    }
}

int main() {
    ifstream fin("money.in");
    ofstream fout("money.out");
    fin >> COINS >> N;
    for (int i = 0; i < COINS; ++i) {
        int c; fin >> c; coins.emplace_back(c);
    }
    compute();
    fout << dp[N] << endl;
}

2016-09-25

USACO

USACO 2.3 Zero Sum

Brutal force DFS search.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
vector<char> ops = {'+', '-', ' '};
vector<char> s;
vector<vector<char>> res;

void dfs(int i) {
    if (i == N) {
        int sum = 0, cur = 1, sign = 1;
        for (int i = 2; i <= N; ++i) {
            char op = s[i - 2];
            if (op == ' ') {
                cur = cur * 10 + i;
            } else {
                sum += cur * sign;
                cur = i;
                if (op == '+') {
                    sign = 1;
                } else {
                    sign = -1;
                }
            }
        }
        sum += cur * sign;
        if (sum == 0) {
            res.push_back(s);
        }
        return;
    }

    for (auto &c : ops) {
        s.push_back(c);
        dfs(i + 1);
        s.pop_back();
    }
}

int main() {
    ifstream fin("zerosum.in");
    ofstream fout("zerosum.out");
    fin >> N;
    dfs(1);
    sort(res.begin(), res.end());
    for (auto &result : res) {
        for (int i = 1; i < N; ++i) {
            fout << i << result[i - 1];
        }
        fout << N << endl;
    }
}