https://cses.fi/problemset/task/2174
i am clueless for this problem. please help me .
I have solved the easy verison of problem using O(N) dp.
I have spent a good amount of time thinking but could not find any solution.
It would be nice if i get any hints.. instead of actual solution...
I have given thoughts about matrix exponentiation, or any observation patterns ... nothing seems to workout.
How to solve this kind of adhoc problems actually...
Auto comment: topic has been updated by ASHWANTH_K (previous revision, new revision, compare).
Did you try greedy?
Notice that you always take the biggest digit to subtract.
Now the remaining problem is to quickly simulate it.
You will encounter a lot of 9s in form of ABCD999999E.
If we know how to solve D999999E, in maybe O(1), (with the maximum digit before it being some F), then we can reduce it to ABC9999999?, which is easier.
For answers of digit in form ????A99999B (with C as the max digit before A), we always reduce 9 until it become A90000B, then we will have A8999?, which is a smaller subproblem — see the DP here?
i understand this fast simulation idea .. i will try to work on it.
thank you
Can't you just go greedy and subtract the largest digit that there is currently.
let's say you manage to subtract $$$9$$$ in every iteration, and let's say you get the largest digit in $$$O(1)$$$, your idea is still $$$O(\frac{n}{9})$$$, and $$$n\le 10^{18}$$$ :)