spirited_away_'s blog

Help in combinatorics problem.
By spirited_away_, history, 5 years ago, In English

How to handle 0's in this problem. Like when you have input like 230005450569. When there is no 0's the answer will be 2^n-1 when C is infinity. Now for C we will count how many numbers we have to subtract from answer which are >= length of C. But how to handle 0's in this case like sample input above.

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

Comments Comments (9)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why don’t you just count the answer itself with DP? The length of possible number is maximum 10, so for every position you’d only need to check 10 possible numbers for validity.

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

    How can we do that. When we look for C length then what about rest of digits. How we will handle them . And specially zeros.

    Since 12 can be answer but 00 can't be.

    Can you describe your approach in more detail.

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

      $$$a_i$$$ – the amount of splits considering only the first $$$i$$$ digits.

      $$$a_0 = 1$$$

      $$$a_i = \sum_{j=\max(0, i-10)}^{i-1} a_j$$$, if number formed by digits $$$[j..i)$$$ is valid (has no leading zeroes and is $$$\leq C$$$)

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

        if the number formed by digits[j..i) is not valid then a[i] = 0. is it correct?

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

          I think you meant $$$a_j$$$, but yes, for that it’s enough to check first digit. Don’t forget that you still need to compare the whole number as well though.

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

            yes, sorry. if j to i-1 is not valid then a[ j ] = 0. and by max(0,i-10) you mean max(0,i-C).

            Please correct me if wrong.

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

              C is not the boundary of the length of a number. It is a boundary of a number. 10 is coming from the fact that the maximum allowed value of C has 10 digits.

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

can you provide problem link?

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I don't trust authors who use Latex but still manage to write $$$<=$$$ instead of $$$\le$$$.

→ Reply