TopCoder

TopCoder SRM 698

DIV2 500

Problem Statement

Brutal force with LCS: this problem is easy if we can identify and transform the core matching algorithm it requires to LCS. Here two implementations of LCS are provided, one is through recursion the other is through explicitly maintaining a lookup table. For some reasons, the recursion solution time out on one system test.


using namespace std;

// This will get TLE on one system test..
int lcs(const string &s1, const string &s2, int m, int n) {
    if (m == 0 || n == 0) return 0;
    if ((s1[m - 1] == s2[n - 1]) && (m > 0 && n > 0))
        return 1 + lcs(s1, s2, m - 1, n - 1);
    else
        return max(lcs(s1, s2, m, n - 1), lcs(s1, s2, m - 1, n));
}

int lcs2(const string &s1, const string &s2, int m, int n) {
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; ++i){
        for (int j = 0; j <= n; ++j) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

class RepeatStringEasy {
public:
    int maximalLength(string s) {
        if (s.empty()) return 0;
        int ret = 0;
        for (int i = 0; i < s.size(); ++i) {
            string s1 = "", s2 = "";
            for (int m = 0; m <= i; ++m) s1 += s[m];
            for (int n = i + 1; n < s.size(); ++n) s2 += s[n];
            ret = std::max(ret, 2 * lcs2(s1, s2, (int)s1.size(), (int)s2.size()));
        }
        return ret;
    }
}
USACO

USACO 2.2 Runaround Numbers

Straight forward brutal force approach. Mainly test implementation skills.

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

using namespace std;

int N;

bool isRunaroundNumber(int n) {
    vector<int> num;
    unordered_map<int, int> map;
    while (n) {
        int d = n % 10;
        if (map.find(d) != map.end()) {
            return false;
        }
        map[d] = 0;
        num.push_back(d);
        n /= 10;
    }

    reverse(num.begin(), num.end());
    int size = (int)num.size(), index = 0, next = -1;
    map[num[0]] = 1;

    while (next != 0) {
        int next = (index + num[index]) % size;
        if (next == 0) {
            for (int i = 0; i < size; ++i) {
                if (map[num[i]] != 1)
                    return false;
            }
            return true;
        }
        if (map[num[next]] == 1)
            return false;
        map[num[next]]++;
        index = next;
    }
    return false;
}

int main() {
    ifstream fin("runround.in");
    ofstream fout("runround.out");
    fin >> N;
    ++N;
    while (!isRunaroundNumber(N++));
    fout << --N << endl;
}
USACO

USACO 2.2 Subset Sum

It’s tempting to solve this using brutal force search like dfs:

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

using namespace std;

int result;
int expected;
int N;
set<unsigned long> st;
bitset<32> bset;

void dfs(int sum, int index) {
    if (sum == expected && !st.count(bset.to_ulong())) {
        st.insert(bset.to_ulong());
        ++result;
    }

    if (sum > expected) return;

    for (int i = index; i <= N ; ++i) {
        bset.set(i);
        dfs(sum + i, i + 1);
        bset.flip(i);
    }
}

int main() {
    ifstream fin("subset.in");
    ofstream fout("subset.out");
    bset.reset();
    fin >> N;
    expected = (N + 1) * N / 2;
    if (expected % 2)
        return 0;

    expected /= 2;
    dfs(0, 1);
    fout << result / 2 << endl;
}

This solution however does not pass all tests, which has a time limit of 1 sec and a space limit of 16MB. The reason is the simple search will yield an exponential algorithm, given the state that we are about to explore is as much as 2^N, where N could be as large as 39. That said, it might be possible to optimize the search based algorithm using data structures that provides very optimized memory foot print with fast lookup, but I’ve not yet found such a data structure that satisfy the constraints.

Thinking from another perspective, the set / sum exhibits recursive nature and there are sub problems when solving each set partition, so dynamic programming is here for rescue:

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

using namespace std;

int N;
int expected;
int result;

int main() {
    ifstream fin("subset.in");
    ofstream fout("subset.out");
    fin >> N;
    vector<vector<unsigned long long>> dp(40, vector<unsigned long long>(800, 0));
    expected = (N + 1) * N / 2;
    if (expected % 2) {
        fout << 0 << endl;
        return 0;
    }

    expected /= 2;

    cout << "expected :" << expected << endl;

    for (int i = 0; i <= N; ++i) {
        dp[i][0] = 1;
    }
    cout << N << " " << expected << endl;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= expected; ++j) {
            dp[i][j] += dp[i - 1][j];
            if (i <= j) {
                dp[i][j] += dp[i - 1][j - i];
            }
        }
    }
    fout << dp[N][expected] / 2 << endl;
}