Can someone please post an editorial or just answer what technique/algorithm is required to solve CSUBSEQ and CTREE problem.
5 Likes
For CSUBSEQ, the recursive dp solution by @vsp4 is pretty easy to understand.
https://www.codechef.com/viewsolution/17481074
It was converted to iterative because it gave TLE.
Let’s see how to calculate the number of subsequences of type “CHEF”
let c be the number of subsequences of type “C”
let ch be the number of subsequences of type “CH”
let che be the number of subsequences of type “CHE”
let chef be the number of subsequences of type “CHEF”
(untill current index)
Iterating from 1 to N
Everytime we find a character ‘F’, ‘F’ can be appended to each subsequence of type “CHE” to get “CHEF”, hence chef+=che
Similar thing can be done for each of the above mentioned types.
For the actual problem, a naive solution would be to either take or not take each of the characters and find the value of k for it, if it is equal to k, compare removals with global min and print the min value.
But an important observation here is that if any of c,ch,che,chef exceeds k, there is no need to knw the exact value, since it can be treated as infinity (k+1).
Hence a state can be given by dp[i][c][ch][che][chef] where i is the current index of the string which can either be taken or not taken.
Hence max values of the dp table dp[MAXN][MAXK][MAXK][MAXK][MAXK]
The exact recurrence relation is pretty neatly mentioned in the code.
Complexity: O(N*k^4)
2 Likes
@vivek_shah98 we need to iterate till k+1 because once count of chef exceeds k (k+1,k+2…k+n) they all contribute INF to the ans(dp table)… Hence calculating till k+1 is sufficient(saving memory and time) Refer this and your doubt will surely get cleared.