OK! Now you have an approach to solving a problem, but wait! Will this always work? Is there any counterexample that fails this algorithm? These are the questions that I constantly face nowadays.
Let me elaborate on this with some examples:
Empty Graph: In this problem, the first approach that I came up with was to just assign 10^9 to k smallest numbers. Of course, this was wrong, but I couldn't find a counterexample and I had to ask a friend.
Maximize the minimum: One of the approaches that came to my mind was to assign the maximum value of adjacent elements and do it k times. (tho it was a bit easier to find counterexamples for this approach)
There are two ways(that I know) that one can use to verify a solution:
- Prove it mathematically (using induction, contradiction, etc).
- Find a counterexample
I have talked about this to some of the people(who are doing great on codeforces) and most of them said that they usually go with the second approach. How do they find a counterexample? They say, and I quote "It usually comes with experience" but I'm here to know if there is a systematic way that we can follow to find counterexamples.
