Nishu_Coder's blog

Need Advice
By Nishu_Coder, history, 22 months 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 (6)
| Write comment?
»
22 months 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
  • »
    »
    22 months 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
»
22 months 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
»
22 months 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
»
22 months 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
»
22 months 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