i am a beginner in dp, i read the editorial but cant understand anyting!
"Let me try. First of all, in C2 we can do what’s written in the editorial: split the number in two parts(6 digits each), now while the first part is fixed, all we need to know about it is the biggest digit. So we calculate two arrays: cnt[dig][n] — how many operations we need to get to negative number if we can subtract maximum of dig and biggest digit of n, and decr[dig][n] — what is the first negative number we reach this way(here 0 ≤ dig < 10, 0 ≤ n < 10^6). After that, we can decrease first part by one in O(1) time and that’s it.
C3’s solution is almost the same, we calculate arrays cnt and decr again using memoization, but we split the number into the first digit and remainder."
Source: ABBYY Cup 3.0 — Finals. Solutions - Codeforces
This makes it quite clear, I guess?
i have read it but unable to get it…can you plz elaborate it ?
can anyone please explain a bit !