title: Solving "Welcome to Code Jam" from Google Code Jam 2009
body: <p>I am trying to solve the following code jam question,ive made some progress but for few cases my code give wrong outputs..
  <a href="http://code.google.com/codejam/contest/90101/dashboard#s=p2" rel="nofollow">Welcome to Code jam</a></p>
  
  <p>So i stumbled on a solution by dev "rem" from russia.
  I've no idea how his/her solution is working correctly.. the code...</p>
  
  <pre><code>const string target = "welcome to code jam";
  
  char buf[1&lt;&lt;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&lt;vector&lt;int&gt; &gt; dp(n+1, vector&lt;int&gt;(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 &lt; k &amp;&amp; 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
  </code></pre>
  
  <p>Can somebody explain whats happening in the two loops?</p>
  
  <p>Thanks.</p>