tgbaodeeptry's blog

Why this greedy approach is correct?
By tgbaodeeptry, history, 4 years ago, In English

Hello guys, Today, I'm trying to code this problem: 545C - Woodcutters. I used DP to solve it and I have read problem's Editorial (https://mirror.codeforces.com/blog/entry/17982). And I knew that there still have another approach to solve it: Greedy.

Also this problem can be solved by the next greedy algoritm. Let's fell leftmost tree to the left (it always doesn't make an answer worse). After that, try to fell the next tree. If we can fell it to the left, let's do it (because it also always doesn't make an answer worse). If we can't, then try to fell it to the right. If it is possible, let's do it. Last step is correct because felling some tree to the right may only prevent the next tree's fallen. So we may "exchange" one tree to another without worsing an answer.

But I don't know, why if a tree can fall right we should do it? (I think there are some cases that it will make answer worse ( may be :( )

Thanks very much, guys

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

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

Sorry ... can anyone help me

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    maybe I can help you

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    at first,if we can fell it to the left,let'do it,because by this we can add 1 to ans and do not affect anything in the later.else if we can fell it to right,we can also do it,because by doing this,in the later,we will decrease most 1 to ans,but we can add 1 to ans right now.so it's optimistic.(I am sorry my English is poor)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Let there be $$$(x_i, h_i)$$$ and $$$(x_{i_1}, h_{i+1})$$$, and $$$i_{th}$$$ tree cannot be fallen to the left. But $$$x_i + h_i < x_{i+1}$$$ (tree can be fallen to the right). Then if you do it, there "bad" variants:

  1. $$$(i+1)_{th}$$$ tree cannot be fallen to the right (not depends on decision to $$$i_{th}$$$ tree)
  2. $$$(i+1)_{th}$$$ tree cannot be fallen to the left ($$$x_{i+1} - h_{i+1} \le x_i + h_i$$$). But that means that even if you can fall $$$(i+1)_{th}$$$ tree to the left then you cannot fall $$$i_{th}$$$ tree to the right. So number of fallen trees not decrease.

In both variants it doesn't matter what will be with $$$(i+1)_{th}$$$ tree if you fall $$$i_{th}$$$ tree to the right.

I really hope that someone come and will write this more properly because I bad in prooving greedy:)

→ Reply