michaellin250's blog

By michaellin250, history, 3 weeks ago, In English,

Problem

Editorial

I don't understand the editorial when it says:

"dp0[i][j] = The higher i digits has already been decided, and there are j non-zero digits, and it has already been determined that it is less than N

dp1[i][j] = The higher i digits has already been decided, and there are j non-zero digits, and it has not yet been determined that it is less than N"

What does this mean?

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I do not even get the first sentence: "It is enough to consider the integers of N digits, by filling the higher digits with 0 if necessary.". What is "N digits" here?

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

    In the problem, the number N is the number we're reading in. I'm guessing that's what they mean by N in this case? I don't know.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

The editorial doesn't make sense to me, but since k = 3 and sz(n) = 100, I wrote a very straightforward brute force (solve it differently for each k): https://atcoder.jp/contests/abc154/submissions/15264239

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

    Thank you so much!! Can you explain what you're doing in K == 2 compared to k == 3?

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

      I'm just going over every single possible number with exactly k nonzero digits and then checking if it is bad, i.e., if it is > N. If it is not bad then the answer gets incremented by one.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think what they're talking about is ensuring that the number is bounded under $$$N$$$ whilst building it. Since the number is built from left to right, when we append a digit to the right, we need to know which digits we're allowed to append. If $$$N = 54321$$$ and our current number is $$$5432$$$, then "it has not yet been determined that it is less than $$$N$$$", so we are only allowed to append a $$$0$$$ or $$$1$$$. If we append something bigger like a $$$2$$$, then the number becomes $$$54322 > N$$$, which is not allowed.

On the other hand, if our current number is $$$5431$$$, then no matter what digit we append next, our number will still be less than $$$N$$$. Even the max digit of $$$9$$$ gives us $$$54319 < N$$$. Thus, "it has already been determined that it is less than $$$N$$$".

$$$dp0$$$ and $$$dp1$$$ thus represent the number of ways to build numbers fulfilling these conditions.

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

    Thanks!! What is dp0 and dp1 for index i and index j representing then?

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

      $$$i$$$ would be having the first $$$i$$$ digits of the number already set, and $$$j$$$ would be the number of non-zero digits used so far. When transitioning from $$$dp0[i][j]$$$ or $$$dp1[i][j]$$$ to another state, we iterate over all valid digits as mentioned above and move to the corresponding state. For example, if $$$N = 54321$$$ and we are currently at $$$dp1[4][j]$$$, then choosing $$$0$$$ as the next digit transitions to $$$dp0[5][j]$$$, choosing $$$1$$$ transitions to $$$dp1[5][j+1]$$$, and choosing any other digit is not permitted, since the 5th digit of $$$N$$$ is $$$1$$$ and we have not yet determined our number to be less than $$$N$$$.

      When the editorial says "the higher $$$i$$$ digits", I think that's just poor translation. I'd assume higher is akin to first or leftmost.