what is the best strategy to prove greedy approach in least amount of time? i encounter a lot of greedy problems but do not able to prove its correctness? help
1 Like
Usually you need to think of corner cases where your code fails. If you cannot think of one usually the greediness is correct. Even after this, if the tester gives WA and you don’t know why it is failing, use the below method.
If you have enough time, you can write a brute force solution and test case generator to test if the greedy solution is correct or not.
This is what I use to debug greedy solution’s implementation bugs. This can also be used for DP problems too.
Eg: For the may long challenge CHSIGN I used this technique to debug/verify my code. Find my code here
If you notice I wrote my greedy/DP solution in solve() and brute force solution in brute_solve(). Even though brute-force solution could only handle small size test cases, it is enough in most cases to give you a test case where you logic fails. I hope this answers your question.
What if I m the problem setter and calculating brute Force soln is not possible due to less computation power
Most of the time, if it works for small test cases, it will work for large cases too.
Otherwise greediness of a solution can be proved mathematically some way or other. For this I would suggest the classic greedy problem Activity Selection. It is not intuitive in the problem to sort by finish time. But by proving that there is no way to make the greedy solution better for any input or by proving any other optimal solution result in the same answer validates the greedy solution.
1 Like