catastropher2606's blog

By catastropher2606, history, 3 years ago, In English

Arya has a habit of recording all the expenses in a year. Last year she was busy so she told her son Ryan to do this for her. Ryan used to write all the expenses in a diary. Some months later he realized that he forgot to add any space or comma between the expenses, so now he has only one large number.

However, he remembers that every time the new expense was strictly greater than all of the earlier expenses. Also, expenses do not contain any leading zeroes. He needs your help to find out the number of ways in which he can split the number into a set of expenses keeping in mind the above conditions.

Print the answer modulo 109+7.

Input Format

The first line of input contains a single integer n (1<=n<=5000)

The second line contains a positive number consisting of n digits from 0 to 9.

Output Format

Print a single integer – the number of ways modulo 109+7.

Sample Testcase #0

Testcase Input

5 32745

Testcase Output

4 Explanation

There are 4 possible ways:

32745 3 27 45 3 2745 32 745 Sample Testcase #1

Testcase Input

6 288399

Testcase Output

8 Explanation

In this case, there are 8 possible ways:

288399 2 88399 2 88 399 2 8 8399 2 8 83 99 28 8399 28 83 99 288 3999

please solve this problem, i am stuck in it.

  • Vote: I like it
  • -3
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Why downvote?

Are you familiar to DP? Take a look at this, this and further reading.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You can solve it with dp + Binary Search. And the time complexity will be N*N*logN.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You know what binary search is not required, it could be solvable with only dp, time complexity N*N.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you tell me how would you do it in n2? Even the n2log(n) solution is not clear to me. Its easy to see a n3 dp.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is an array called dp[i][j] (1<=j<=i<=n), contains how many ways there we could divide the array with length 1...i, if we take the last peace with j length.

        And to calculate that we need the sum of dp[i-j][1], dp[i-j][2], ... dp[i-j][min(j, i-1)]. We could use here a partial sum for all i. But the main problem is can we take the length of j-th length for (i-j)-th index.

        And a little bit of brute force this problem could be solvable. Again time complexity N*N, and it will pass.