You are not logged in. Please login at www.codechef.com to post your questions!

×

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

dollarakshay's gravatar image

4★dollarakshay
17617
accept rate: 4%


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)

link

answered 19 Feb '18, 14:05

abdullah768's gravatar image

5★abdullah768
2.4k420
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) vivek_shah985★

@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.

link

answered 21 Feb '18, 22:24

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 21 Feb '18, 22:50

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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