I have gathered a lot of things to ask so i decided to write a blog.

Question 1.

(i) How often do you stress test during a contest ? (ii) How much time do you take to write the brute solution ? Does it actually take around 5 mins like Dominater069 said in this blog. (iii) When should i stress test a problem during contest ? Only after getting a WA ?

Question 2.

(i) How to be sure if my greedy solution is optimal or not? (ii) Do i need to emphasize on standard techniques for proving greedy solutions mentioned in books, or i just have to take a gist of their ideas?

I have tried to learn proving techniques like exchange arguments and greedy stays ahead from a lot of youtube videos, books and this blog. Until now, i have not understood anything except the very idea of these techniques. Although, i think my problem solving skills of greedy and constructive problems have improved a lot, only by knowing these ideas.

(iii) For the people who are Candidate Masters and above, how often do you think about these proofs of correctness when solving greedy problems ? Does it now get just intuitive ? (iv) Is there a way to know that this problem is not a greedy one ? Or do you first think about DP, then greedy ?

There are many instances where I waste around 90 minutes on a problem during a contest trying to find a greedy strategy, only to realize that it was actually a DP problem. Few examples are this and this problem.

Some types of dp patterns like knapsack, dp with bitmasks, matrix chain multiplication, etc. can be seen directly, atleast in easier problems. But things like interval dp and partition dp is pretty hard to find. Can you tell me the patterns which signals you to think about these ?

Please share if you have any good resources related to proving a greedy solution, finding out DP v/s greedy or stress testing.

PS: The number of times i have edited this blog is worth worrying about lol :)