Contest Duration: - (local time) (100 minutes) Back to Home

## C - chokudai Editorial by en_translator

Let $$dp[i][j]$$ be “the number of combinations of $$j$$ characters chosen out of the first $$i$$ characters of $$S$$ so that the resulting string is equal to the first $$j$$ characters of chokudai.
Here, the following recurrence relations are satisfied, where $$N=|S|$$ and $$T=$$chokudai:

$$\displaystyle dp[i][j] = \begin{cases} 1 & ( j = 0) \\0 & ( i=0 , 1 \leq j \leq 8) \\dp[i-1][j]& ( 1 \leq i \leq N , 1\leq j \leq 8, S[i] \neq T[j] ) \\dp[i-1][j] + dp[i-1][j-1] & (1 \leq i \leq N , 1\leq j \leq 8, S[i] = T[j])\end{cases}$$

If you do not understand the reason of the recurrence relations

• If $$j=0$$
We have “the first $$0$$ characters of chokudai” if and only if no characters is underlined. There are $$1$$ such combinations.

• If $$i=0$$ and $$1 \leq j \leq 8$$
No combinations of characters chosen from the first $$0$$ characters of $$S$$ is equal to the first $$j (j \geq 1)$$ characters of chokudai, so there are $$0$$ such combinations.

• If $$1 \leq i \leq N$$ and $$1\leq j \leq 8$$

• If $$S[i] \neq T[j]$$
What we want is “the number of combinations of characters chosen out of the first $$i$$ characters of $$S$$ so that the resulting string is equal to the first $$j$$ characters of $$T$$.” However, since the $$i$$-th character of $$S$$ and the $$j$$-th character of $$T$$ are different, we do never underline the $$i$$-th character of $$S$$. Therefore, the desired number is equal to “the number of combinations of characters out of the first $$(i-1)$$ characters of $$S$$ so that the resulting string is equal to the first $$j$$ characters of $$T$$,” that is, $$dp[i-1][j]$$.

• If $$S[i] = T[j]$$

• If the $$i$$-th character of $$S$$ is not underlined
The number of such combinations is $$dp[i-1][j]$$ by the discussion above.

• If the $$i$$-th character of $$S$$ is underlined
The number of such combinations is equal to “the number of combinations of characters chosen from the first $$(i-1)$$ characters of $$S$$ so that the resulting string is equal to the first $$(j-1)$$ characters of $$T$$.”

Overall, the total number is $$dp[i-1][j] + dp[i-1][j-1]$$

One can find every $$dp[i][j]$$ in the increasing order of $$i$$ and $$j$$ with double for statements.
The final result is $$dp[N][8]$$.
The computational complexity of this algorithm is $$O(N)$$, which is fast enough.

posted:
last update: