jhjfbsbfkbjfnfnfjfj's blog

Greedy way to do this? DIV3 496D
By jhjfbsbfkbjfnfnfjfj, history, 7 years ago, In English

Hello everyone, i just wanted to know why this solution cannot be solved using greedy approach https://codeforces.me/contest/1005/submission/76980469

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I guess, this is not the correct greedy approach. For number $$$20302$$$, your code gives answer $$$0$$$ whereas it should be $$$3$$$.

In my opinion, the correct greedy would be what you are doing, and additionally if you encounter $$$0$$$, $$$3$$$, $$$6$$$ or $$$9$$$ make a separator there.

→ Reply
  • »
    »
    7 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Exactly, the better greedy aprroach is using DP, then $$$dp_i$$$ means the answer when we consider first $$$i$$$ elements, it can be updated in two ways, the last block which has $$$ith$$$ position is divisible by 3, or not, if not then $$$dp_i$$$ will be equal to $$$dp_{i-1}$$$, and otherwise cut the smallest block which is divisible by 3, then $$$dp_i$$$ will be $$$dp_j+1$$$(finding the smallest block can be done whit a precalculation with $$$O(n)$$$ time).

    The whole problem will be $$$O(n)$$$.

    → Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This might help you.

→ Reply