TCO 2013 2A

This round was spent in agony, as any other round I participate after several months of inactivity.

My biggest mistake in this round was pretty silly: I expected 300 to be a standard math/greedy problem and couldn't realise it was the simplest dynamic programming problem ever met on Topcoder.

After an hour of looking for "universal greedy" I gave up and prepared several test cases for challenge phase.

I got lucky during challenge phase and could achieve 50 pts. It is not much but I still consider myself quite lucky getting something in room full of red-yellow coders.

Ironically, a lot of bluish-yellowish coders solved 300 with no problems. Next time, after spending N minutes on greedy solution, I will pivot to dp, as I did it before.

After the round this solution seems the most obvious thing. Unfortunately I did a wrong assumption that no dp is applicable.

The funny thing is: a lot of coders failed with greedy solutions on system test phase and I jumped to fourth hundred. That spoiled round gave me some positive rating and lesson for future.

Code

300 solved right after round:

pair<string, string> dp[100][100];
string res;

class TheLargestString {
public:
    string find(string s, string t) {
        int n = s.size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++) {
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
                dp[i+1][j+1] = max(dp[i+1][j+1], mp(
                    dp[i][j].first+s[i], dp[i][j].second+t[i]));
            }

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++) {
                res = max(res, dp[i][j].first + dp[i][j].second);
            }
        return res;
    }
};