Solving "Welcome to Code Jam" from Google Code Jam 2009

Question

I am trying to solve the following code jam question,ive made some progress but for few cases my code give wrong outputs.. Welcome to Code jam

So i stumbled on a solution by dev "rem" from russia. I've no idea how his/her solution is working correctly.. the code...

const string target = "welcome to code jam";

char buf[1<<20];

int main() {
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);

        gets(buf);
        FOR(test, 1, atoi(buf)) {
                gets(buf);
                string s(buf);
                int n = size(s);
                int k = size(target);
                vector<vector<int> > dp(n+1, vector<int>(k+1));
                dp[0][0] = 1;
                const int mod = 10000;
                assert(k == 19);
                REP(i, n) REP(j, k+1) {// Whats happening here
                        dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod;
                        if (j < k && s[i] == target[j])
                                dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%mod;
                }
                printf("Case #%d: %04d\n", test, dp[n][k]);
        }

        exit(0);
}//credit rem

Can somebody explain whats happening in the two loops?

Thanks.

Answer 1

Whoa, I was practicing this problem few days ago and and stumbled across this question.

I suspect that saying "he's doing dynamic programming" won't not explain too much if you did not study DP.

I can give clearer implementation and easier explanation:

string phrase = "welcome to code jam"; // S
string text; getline(cin, text); // T
vector<int> ob(text.size(), 1);
int ans = 0;
for (int p = 0; p < phrase.size(); ++p) {
    ans = 0;
    for (int i = 0; i < text.size(); ++i) {
        if (text[i] == phrase[p]) ans = (ans + ob[i]) % 10000; 
        ob[i] = ans;
    }
}
cout << setfill('0') << setw(4) << ans << endl;

To solve the problem if S had only one character S[0] we could just count number of its occurrences.

If it had only two characters S[0..1] we see that each occurrence T[i]==S[1] increases answer by the number of occurrences of S[0] before index i.

For three characters S[0..2] each occurrence T[i]==S[2] similarly increases answer by number of occurrences of S[0..1] before index i. This number is the same as the answer value at the moment the previous paragraph had processed T[i].

If there were four characters, the answer would be increasing by number of occurrences of the previous three before each index at which fourth character is found, and so on.

As every other step uses values from the previous ones, this can be solved incrementally. On each step p we need to know number of occurrences of previous substring S[0..p-1] before any index i, which can be kept in array of integers ob of the same length as T. Then the answer goes up by ob[i] whenever we encounter S[p] at i. And to prepare ob for the next step, we also update each ob[i] to be the number of occurrences of S[0..p] instead — i.e. to the current answer value.

By the end the latest answer value (and the last element of ob) contain the number of occurrences of whole S in whole T, and that is the final answer.

Notice that it starts with ob filled with ones. The first step is different from the rest; but counting number of occurrences of S[0] means increasing answer by 1 on each occurrence, which is what all other steps do, except that they increase by ob[i]. So when every ob[i] is initially 1, the first step will run just like all others, using the same code.

Answer 2

What he is doing: dynamic programming, this far you can see too.

He has 2D array and you need to understand what is its semantics. The fact is that dp[i][j] counts the number of ways he can get a subsequence of the first j letters of welcome to code jam using all the letters in the input string upto the ith index. Both indexes are 1 -based to allow for the case of not taking any letters from the strings.

For example if the input is:

welcome to code jjam

The values of dp in different situations are going to be:

 dp[1][1] = 1; // first letter is w. perfect just the goal
 dp[1][2] = 0; // no way to have two letters in just one-letter string
 dp[2][2] = 1; // again: perfect
 dp[1][2] = 1; // here we ignore the e. We just need the w.
 dp[7][2] = 2; // two ways to construct we: [we]lcome and [w]elcom[e].

The loop you are specifically asking about calculates new dynamic values based on the already calculated ones.