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

×

# valid partition of a string such that segments are in increasing order

 0 A string of digits is given, for example, "12335457". A valid partition is a partition of the string such that each segment is strictly greater than that previous segment. For example, "12 | 33 | 54 | 57" is a valid partition and 57 > 54 > 33 > 12. Another valid partition can be "12 | 335 | 457" . How many valid partitions possible for the given string? The maximum length of the string can be 5000. If we use dynamic programming with parameter i and j, which means, the last segment was from i ... to ..j, then we can recurse on the remaining part. int solve(int i,int j) { // memoization need to be added int last_length = j - i + 1; int ans = 0; for(int k = j + last_length ; k < n ; k++) { if( segment(j+1,k) > segment(i,j) ) { // this is possible in O(1) even if segment lengths are equal // we should do some pre preocessing on the given string // which can take O(n^2) time // if segment(j+1,k) length is more than L , then it is trivial ans += solve(j+1 , k); } } }  But this approach will take O(n^3) time. How can we reduce it from O(n^3)? asked 27 Jun '18, 16:29 2★synch 1●1 accept rate: 0%

 0 Let dp[i][j] denotes the number of valid partition of string s[1:i] where the last partition ranges from s[j:i] So dp[i][j]=sum(dp[j-1][k]) Where $j-1-k < i-j$ i.e. $k>2*j-1-i$ if(s[j:i]>s[j-1-(i-j)][j-1]) dp[i][j]+=dp[j-1][j-1-(i-j)] Ohk ,so reasoning, If last segment is of length x,then we can obviously choose previous segment with length less than x . If previous segment is also of same length,then check if last is greater. Now basically u have to find sum(dp[j-1][k]) fast So basically when u have calculated dp[i][j] for a given i and all j,u can just calculate suffix[i][j] where suffix[i][j]=sum(suffix[i][j+1]+dp[i][j]) Basically suffix[i][j] will now store sum(dp[i][j] to dp[i][i]) answered 27 Jun '18, 18:07 1.6k●2●9 accept rate: 23%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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:

×2,220
×355

question asked: 27 Jun '18, 16:29

question was seen: 101 times

last updated: 27 Jun '18, 18:07