Codeforces Div.3 F ques

Can we discuss Codeforces F in today’s doubt clearing session
https://codeforces.com/contest/1426/problem/F
Prob. 3 and Prob. 5 from below link
https://codeforces.com/blog/entry/83100

1 Like

Hey @ckant_787, since this is a DP problem, we can cover this later in detail when we will have DP doubt sessions. It would not be relevant for other people as that doubt session is about sorting. For now, I can discuss my approach:
Let dp[i][j] be the total number of subsequences which are equal to prefix length j of the string “abc”, in all strings that can be made using the prefix length i of the original string. We will store dp[i][j] for each i in 0…n and 0…3 (assuming 1 based indexing everywhere)
E.g. Let s = “ab?c”, then dp[3][2] will contain the total number of “ab” subsequences in all strings made using the prefix of length 3. Its easy to see that all strings possible using 3 length suffixes are: {“aba”, “abb”, “abc”}. So in this case dp[3][2] will hold 1 + 2 + 1 = 4.

To calculate dp[i][j], we have the base case:
dp[0][0] = 1, dp[0][1] = dp[0][2] = dp[0][3] = 0.
For all i > 1, dp[i][j] can be calculated as follows:
if s[i] = ‘?’, then we can replace that with either an ‘a’, ‘b’ or ‘c’ (3 ways). So the recurrence would be:
dp[i][0] = 3 * dp[i-1][0]; // Since all strings will have this 0 length subsequence, irrespective of we appending ‘a’, ‘b’ or ‘c’.
dp[i][1] = dp[i-1][0] + 3 * dp[i-1][1]; // append ‘a’ to 0 length subsequences - “” to get 1 length subsequences - “a”, and also count the existing 1 length subsequences, which will be there irrespective of we appending ‘a’, ‘b’ or ‘c’.
dp[i][2] = dp[i-1][1] + 3 * dp[i-1][2]; // append ‘b’ to 1 length subsequences - “a” to get 2 length subsequences - “ab”, and also count the existing 2 length subsequences, which will be there irrespective of we appending ‘a’, ‘b’ or ‘c’.
dp[i][3] = dp[i-1][2] + 3 * dp[i-1][3]; // append ‘c’ to 2 length subsequences - “ab” to get 3 length subsequences “abc”, and also count the existing 3 length subsequences, which will be there irrespective of we appending ‘a’, ‘b’ or ‘c’.

if s[i] is ‘a’, then we don’t have any choice. So in that case:
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][0] + dp[i-1][1]; // existing 0 length + “a” to get 1 length, and existing 1 length
dp[i][2] = dp[i-1][2];
dp[i][3] = dp[i-1][3];

Similarly we can handle ‘b’ and ‘c’ cases.
dp[n][3] will hold our final answer. And don’t forget to take MOD everywhere.

2 Likes