USACO 4.3 Street Race

Use DFS to do brutal force search given the small data size. There are two problems:

Decide the unavoidable points. This can be solved by iterating over each point (except the starting and ending point 0 and N, respectively) and assume the current point is being taken out of the graph. If in such a graph starting from 0 there is still a path to N then the current point being taken out is not an unavoidable point. Otherwise, the current point is an unavoidable point.
Decide the splitting points. The splitting points must be a subset of unavoidable points. So iterating through all the unavoidable points figured out in first step, and do two search from 0 and the current iterating point respectively, and record the sets of point that two search could reach. If the two sets intersect, then the current point can’t be a splitting point by definition; otherwise the current point is a splitting point.

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

using namespace std;

int N;
bool graph[55][55];
bool visited[55];
set<int> st;
int split;

bool dfs(int v, int j) {
    visited[v] = true;
    for (int i = 0; i <= N; ++i) {
        if (visited[i] || !graph[v][i] || i == j || i == v) continue;
        if ((i == N && graph[v][i]) || dfs(i, j)) return true;
    }
    return false;
}

void dfs(int s) {
    st.insert(s);
    for (int i = 0; i <= N; ++i) {
        if (st.count(i) || !graph[s][i] || s == i || i == split) continue;
        dfs(i);
    }
}

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

    memset(graph, 0, sizeof(graph));
    int n = 0;
    while(!fin.eof()) {
        fin >> n;
        if (n == -2) {
            ++N;
            continue;
        }
        if (n == -1) break;
        graph[N][n] = true;
    }
    --N;

    vector<int> r1, r2;
    for (int i = 1; i <= N - 1; ++i) {
        memset(visited, 0, sizeof(visited));
        if (!dfs(0, i)) r1.push_back(i);
    }

    cout << r1.size(); fout << r1.size();
    for (auto r : r1) {
        st.clear();
        cout << " " << r; fout << " " << r;
        split = r; dfs(0); auto stt = st; st.clear(); dfs(r);
        std::vector<int> common_data;
        set_intersection(st.begin(), st.end(), stt.begin(), stt.end(),
                         std::back_inserter(common_data));
        if (!common_data.empty()) continue;
        r2.push_back(r);
    }
    cout << endl; fout << endl;

    cout << r2.size(); fout << r2.size();
    for (auto r : r2) {
        cout << " " << r; fout << " " << r;
    }
    cout << endl; fout << endl;
}

2017-01-13

USACO

USACO 4.3 Buy Low

Essentially a longest decreasing sequence problem that is easy to solve using typical DP approach. Counting the number of such sequences is also not hard, the real problem is that the counts could be too big to fit in 32 or 64 bit integers, so need to use big integers struct.


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

using namespace std;

const int base = 1000000000;
const int base_digits = 9;

struct BigInteger {
    vector<int> a;
    int sign;

    BigInteger() : sign(1) {}
    BigInteger(long long v) {
        *this = v;
    }

    void operator=(const BigInteger &v) {
        sign = v.sign;
        a = v.a;
    }

    void operator=(long long v) {
        sign = 1;
        a.clear();
        if (v < 0) {
            sign = -1, v = -v;
        }
        for (; v > 0; v = v / base) {
            a.push_back(v % base);
        }
    }

    BigInteger operator+(const BigInteger &v) const {
        if (sign != v.sign) return *this - (-v);
        BigInteger res = v;
        for (int i = 0, carry = 0;
             i < (int) max(a.size(), v.a.size()) || carry; ++i) {
            if (i == (int) res.a.size())
                res.a.push_back(0);
            res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
            carry = res.a[i] >= base;
            if (carry) res.a[i] -= base;
        }
        return res;
    }

    BigInteger operator-(const BigInteger &v) const {
        if (sign != v.sign) return *this + (-v);
        if (abs() < v.abs()) return -(v - *this);
        BigInteger res = *this;
        for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
            res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
            carry = res.a[i] < 0;
            if (carry)
                res.a[i] += base;
        }
        res.trim();
        return res;
    }

    void operator+=(const BigInteger &v) {
        *this = *this + v;
    }
    void operator-=(const BigInteger &v) {
        *this = *this - v;
    }

    bool operator<(const BigInteger &v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (a.size() != v.a.size())
            return a.size() * sign < v.a.size() * v.sign;
        for (int i = (int)a.size() - 1; i >= 0; i--)
            if (a[i] != v.a[i])
                return a[i] * sign < v.a[i] * sign;
        return false;
    }

    bool operator>(const BigInteger &v) const {
        return v < *this;
    }
    bool operator <= (const BigInteger &v) const { return !(v < *this); }
    bool operator >= (const BigInteger &v) const { return !(*this < v); }
    bool operator == (const BigInteger &v) const {
        return !(*this < v) && !(v < *this);
    }
    bool operator != (const BigInteger &v) const { return *this < v || v < *this; }

    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            sign = 1;
    }

    BigInteger operator-() const {
        BigInteger res = *this;
        res.sign = -sign;
        return res;
    }

    BigInteger abs() const {
        BigInteger res = *this;
        res.sign *= res.sign;
        return res;
    }

    friend ostream& operator<<(ostream &stream, const BigInteger &v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.a.empty() ? 0 : v.a.back());
        for (int i = (int) v.a.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.a[i];
        return stream;
    }
};

int N;
vector<int> num, dp;
vector<BigInteger> cnt;

int main() {
    ifstream fin("buylow.in");
    ofstream fout("buylow.out");
    fin >> N;
    num = vector<int>(N, 0);
    dp = vector<int>(N, 0);
    cnt = vector<BigInteger>(N, BigInteger(0));

    for (int i = 0; i < N; ++i) {
        fin >> num[i];
    }
    dp[0] = 1; cnt[0] = 1;
    for (int i = 0; i < N; ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (num[j] > num[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }

        for (int j = 0; j < i; ++j) {
            if (num[j] > num[i] && dp[i] == dp[j] + 1) {
                cnt[i] += cnt[j];
            }
        }
        if (cnt[i] == 0) cnt[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (num[j] == num[i] && dp[j] == dp[i]) {
                cnt[i] -= cnt[j]; // remove duplicates.
            }
        }
    }

    int maxLen = *std::minmax_element(dp.begin(), dp.end()).second;
    BigInteger finalCnt = 0;
    for (int i = 0; i < N; ++i) {
        if (maxLen == dp[i]) {
            finalCnt += cnt[i];
        }
    }
    cout << maxLen << " " << finalCnt << endl;
    fout << maxLen << " " << finalCnt << endl;
}

2017-01-08

USACO

USACO 4.2 Job Processing

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

using namespace std;

int N, M1, M2;
vector<int> va, vb, cost, ta, tb;

void compute(const vector<int> &vec, vector<int> &table) {
    int size = (int)vec.size();
    cost = vector<int>(size, 0);
    for (int i = 0; i < N; ++i) {
        int min = INT_MAX, index;
        for (int j = 0; j < size; ++j) {
            int delay = cost[j] + vec[j];
            if (min <= delay) continue;
            min = delay; index = j;
        }
        cost[index] = min;
        table[i] = min;
    }
}

int main() {
    ifstream fin("job.in");
    ofstream fout("job.out");
    int ansA, ansB = INT_MIN;
    fin >> N >> M1 >> M2;
    va = vector<int>(M1, 0), vb = vector<int>(M2, 0);
    ta = vector<int>(N, 0), tb = vector<int>(N, 0);
    for (int i = 0; i < M1; ++i) fin >> va[i];
    for (int i = 0; i < M2; ++i) fin >> vb[i];
    compute(va, ta); compute(vb, tb);
    sort(ta.begin(), ta.end());
    sort(tb.begin(), tb.end(), [] (int a, int b) { return a > b; });
    ansA = ta[N - 1];
    for (int i = 0; i < N; ++i) {
        ansB = std::max(ta[i] + tb[i], ansB);
    }
    fout << ansA << " " << ansB << endl;
    cout << ansA << " " << ansB << endl;
}