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.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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
may be because of my poor use of English language people have downvoted.
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)
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.
A lot of things come with practice, and you seem to have not practiced well yet. Practice more.
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.