Vasiljko's blog

Cut number in optimal way
By Vasiljko, history, 6 years ago, In English

Given string S of N (N<=100 000) characters (each character is digit). Also given, L and R (L <= R <= 109 ). Find maximum sum that is possible to obtain cutting the string in such a way that every part has value <=R and >=L.

Input: N L R S

Test case:
8 13 997
81196054

Output: 1825

Explanation: These are all possible cuts. Last cut is best
1. 81|19|60|54
2. 81|196|054
3. 811|96|054
4. 811|960|54

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

dp[i] = maximum answer on prefix. Every iteration, try all numbers with digits [i+1 ... r) and update dp[r]. r can't go far from i.

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

    I don't understand the part with digits [i+1,r). Also r can be up to 1e9

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

      It's not r from the statement. You may call it j. You move j to the right from i and try to add the number formed by the digits a[i] ... a[j]. As L, R <= 1e9, j — i <= 10.

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

        Yes that's what i did but going to left so i couldn't handle big number of leading zeros. Thank you

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Nevermind

        → Reply