### michaellin250's blog

By michaellin250, history, 3 weeks ago, , 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? Comments (9)
 » 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?
•  » » 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.
 » 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
•  » » Thank you so much!! Can you explain what you're doing in K == 2 compared to k == 3?
•  » » » 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.
•  » » » » Is pref a prefix sum?
 » 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.
•  » » Thanks!! What is dp0 and dp1 for index i and index j representing then?
•  » » » $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[j]$, then choosing $0$ as the next digit transitions to $dp0[j]$, choosing $1$ transitions to $dp1[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.