Problem 4: Welcome to Code Jam (Hard)

https://open.kattis.com/problems/welcomehard

Given a string S of length $n$, find the number of times "welcome to code jam" appears as a subsequence in the string.

Idea: use a (n + 1) x 20 DP array to count the number of appearances. (There are 19 letters in the string "welcome to code jam".)

Let's keep track of the target string in a variable target = "welcome to code jam" and the answer in an array dp[n+1][20](initialized to zeros).

For each char in the given string, compare it to each char "welcome to code jam". (Outer loop: go through each letter of the given string S; inner loop: iterate over target.) For the current char S[i] and a char target[l], the count at S[i] is equal to the count at S[i-1] plus the count at S[i] (with respect to target[l]).

Base case:

• dp[0][0] = 1

Recurrence relation:

• dp[i + 1][l] = dp[i][l] + dp[i + 1][l]

Additionally, if S[i] == target[l], then we also have dp[i + 1][l + 1] = dp[i][l] + dp[i + 1][l + 1]. Otherwise if they are not equal, then we don't perform the extra addition.

At the end, the answer we are looking for is stored at dp[n][19].

Note: after each arithmetic operation, remember to take the modulo 10000 of the result. Also, be careful with formatting the answer!