USACO

USACO 2.3 Cow Pedigrees 

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

using namespace std;

int N, K;
const int MOD = 9901;

int main() {
    ifstream fin("nocows.in");
    ofstream fout("nocows.out");
    fin >> N >> K;
    vector<vector<int>> dp(K + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= K; ++i) {
        dp[i][1] = 1;
    }

    for (int i = 1; i <= K; ++i) {
        for (int j = 1; j <= N; j+= 2) {
            for (int k = 1; k <= j - 2; ++k) {
                dp[i][j] = (dp[i][j] +
                            dp[i - 1][k] * dp[i - 1][j - k - 1]) % MOD;
            }
        }
    }

    int result = (dp[K][N] - dp[K - 1][N] + MOD) % MOD;
    fout << result << endl;
}
USACO

USACO 2.3 Longest Prefix

Typical dyanmic programming problem as the string matching can be broken into sub problems which overlap with each other.

Key observations:

  • Let’s have dp[i] represents the longest possible prefix starting at index i, with i in the range of 0 to size - 1, with size being the length on the source string under match. The state transformation equation is: dp[i] = max(dp[i], dp[i] + j - i), if and only if substring starting from index i with length j - i is one of the dictionary string. With this, we search starting from the end of the string and once we finish, the answer would be dp[0].
  • Compute the state transformation from end to start of string (as we are searching for longest prefix.).

Traps:

  • The input string to match can span across multiple lines! So a single read will not possibly grab the entire source string; instead multiple reads might be required.
  • The important constraint when matching against primitives: primitives are all in length 1..10. Without this constraints, it is very easy to get timeout error on the last test case.
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <unordered_set>

using namespace std;
int main() {
    ifstream fin("prefix.in");
    ofstream fout("prefix.out");
    unordered_set<string> pset;

    string cur;
    fin >> cur;
    while (cur != ".") {
        pset.insert(cur);
        fin >> cur;
    }

    string s;
    while (!fin.eof()) {
        string str;
        fin >> str;
        s += str;
    }

    int size = (int)s.size();
    vector<int> dp(size, 0);
    if (pset.count(s.substr(size - 1))) {
        dp[size - 1] = 1;
    }

    for (int i = size - 1; i >= 0; --i) {
        for (int j = i + 1; j <= i + 10 && j < size; ++j) {
            string str = s.substr(i, j - i);
            if (pset.count(str)) {
                dp[i] = std::max(dp[i], dp[j] + j - i);
            }
        }
    }

    fout << dp[0] << endl;
}

USACO

USACO 2.2 Party Lamps

Search space would be huge so reducing and consolidating states is required. Key observations:

  1. Press same button twice yield no effect. Thus there is at most 2 ^ 4 = 16 switch state.
  2. The switch state can be further reduced by enumerating all possible switch states and consolidate. Essentially, when the count of key press is larger than three, every switch state (among the maximum 16 states in total) could possibly appear.
  3. The lamp state has a cycle of six.
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <bitset>
#include <cstring>

using namespace std;

// Total # of lamps.
int N;
// Total # of button pressed.
int C;
int cur;

// All possible final state, with different key combinations.
//char lampStates[][7] =
vector<string> lampStates = {
     "111111",  // (),(1,2,3)
     "011011",  // (1,2,3,4),(4)
     "101010",  // (1,2),(3)
     "001110",  // (1,2,4),(3,4)
     "010101",  // (1,3),(2)
     "110001",  // (1,3,4),(2,4)
     "000000",  // (1),(2,3)
     "100100"   // (1,4),(2,3,4)
};

// Number of key presses required to reach a given lampState[index].
vector<vector<int>> keyStates = { {0,3},{1,4},{1,2},{2,3}, {1,2},{2,3},{1,2},{2,3} };
vector<bool> on(6, false);
vector<bool> off(6, false);

bool validate(int index) {
    for (int i = 0; i < 7; ++i) {
        if ((on[i] && lampStates[index][i] == '0') ||
            (off[i] && lampStates[index][i] == '1')) {
            return false;
        }
    }
    return true;
}

struct Result {
    string s;
    bool operator < (const Result& a) const {
        return strcmp(s.c_str(),  a.s.c_str()) < 0;
    }
} result[8];

void parseInput() {
    ifstream fin("lamps.in");
    fin >> N;
    fin >> C;
    int cur;
    fin >> cur;
    while (cur != -1) {
        on[(cur - 1) % 6] = true;
        fin >> cur;
    }

    fin >> cur;
    while (cur != - 1) {
        off[(cur - 1) % 6] = true;
        fin >> cur;
    }
}

int main() {
    parseInput();
    ofstream fout("lamps.out");
    int count = 0;
    if(C < 3) {
        for(int i = 0; i < 8; ++i)
            for(int j = 0; j <= 1; ++j) {
                if((keyStates[i][j] == C ||
                    keyStates[i][j] == C - 2) && validate(i))
                    result[count++].s = lampStates[i];
            }
    } else {
        for(int i = 0; i < 8; ++i)
            if(validate(i)) {
                result[count++].s = lampStates[i];
            }
    }

    if(count == 0) {
        fout << "IMPOSSIBLE" << endl;
    } else {
        sort(result, result + count);
        for(int i = 0; i < count; ++i) {
            int k = N;
            while(k >= 6) {
                fout << result[i].s;
                k -= 6;
            }
            int j = 0;
            while(j < k) {
                fout << result[i].s[j++];
            }
            fout << endl;
        }
    }
    return 0;
}