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

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

synch's gravatar image

2★synch
11
accept rate: 0%

edited 27 Jun '18, 16:32


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])

link

answered 27 Jun '18, 18:07

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

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:

×2,220
×355

question asked: 27 Jun '18, 16:29

question was seen: 101 times

last updated: 27 Jun '18, 18:07