×

# Requesting editorial for CSUBSEQ and CTREE from COOK91

 5 1 Can someone please post an editorial or just answer what technique/algorithm is required to solve CSUBSEQ and CTREE problem. asked 19 Feb '18, 11:52 176●1●7 accept rate: 4%

 2 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) answered 19 Feb '18, 14:05 2.4k●4●20 accept rate: 17% what was the need to iterate till k+1, can u explain @abdullah768 in the given link? (21 Feb '18, 17:55)
 0 @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. answered 21 Feb '18, 22:24 71●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,638
×228

question asked: 19 Feb '18, 11:52

question was seen: 875 times

last updated: 21 Feb '18, 22:50