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 and books (i also found this blog insightful). But till this point i haven't understood anything except the very idea of the 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 am i just not good enough in DP lol). How do you know if "you" are not able to come up with a greedy strategy or this problem is not a greedy one? Or do you first think about DP, then greedy ?

There are a lot of instances when i waste 1.5 hours on a problem in a contest trying to find a greedy strategy just to know it was a DP problem. Few examples are this and this.

Some types of dp like knapsack, dp with bitmasks, even matrix chain multiplication 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.