Nishu_Coder's blog

Need Advice
By Nishu_Coder, history, 2 years ago, In English

what strategies do I need to follow to have a convenient grasp on proving various greedy and constructive strategies, approaches of a particular problem during the contests and while doing practice?

Basically what I am asking is how do I master the art of proving greedy and constructive approaches.

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

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

its a good post why do u get downvoted? i can claim most of people who downvoted u depend on proving by accepting in contests lol

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

    may be because of my poor use of English language people have downvoted.

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

One common technique while proving greedy algorithms is called exchange arguments.

While I have not watched the video I have linked, it is by Errichto so I am guessing it is good. Searching up exchange arguments also leads to some good articles if you would rather read than watch.

(https://www.youtube.com/watch?v=7hFWrKa6yRM&ab_channel=Errichto)

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My best wishes to all the people who downvoted that you prove all your greedy solutions during the contest. I hope all of you become LGM one day.

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

A lot of things come with practice, and you seem to have not practiced well yet. Practice more.

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

Proofs come from mathematical maturity. Rigorously proving greedy algorithms and constructive algorithms can be easier if one had done MO, specifically combinatorics, or I guess taking classes related to discrete mathematics would also help a lot. As you asked how to master this, maybe you could go on AoPS and find some handouts regarding combinatorics and solve some MO problems and if you can do that you have definitely mastered it. There are obviously other ways to go about it, but whichever method you take, just remember to practice writing proofs as rigorously as possible. Then, you would slowly develop intuition and would be able to prove things easily.

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is fantastic video on exchange argument: https://www.youtube.com/watch?v=5d5tVcUAzJU

It shows why in an unsorted array (the comparator while sorting is your greedy sorting strategy) you will always have a back to back or consecutive inversion.

In the optimal solution there must be
arr[i + 1] < arr[i] 
but your greedy strategy suggests  arr[i + 1] > arr[i] 
So i and i + 1 is a consecutive / back-to-back inversion

You should be be able to prove swapping arr[i], arr[i + 1] or removing the inversion reduces the cost function.

And after removing inversion the optimal solution or optimal order will become closer to your greedy order, and this also reduces cost. Eventually proving that after removing all inversions, you have only improved the cost or the cost is same as the optimal solution but did not become worse. So greedy solution or greedy order is just as good as optimal order or better.

This is the general trend in greedy sorting problems.

https://mirror.codeforces.com/blog/entry/63533#comment-1162495

→ Reply