ASHWANTH_K's blog

Help please — Removing Digits II CSES
By ASHWANTH_K, history, 11 months ago, In English

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.

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve this kind of adhoc problems actually...

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

Auto comment: topic has been updated by ASHWANTH_K (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did you try greedy?

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

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?

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

    i understand this fast simulation idea .. i will try to work on it.
    thank you

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't you just go greedy and subtract the largest digit that there is currently.

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

    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}$$$ :)

    → Reply