Doubt related to proof of existence

https://www.codechef.com/problems/FGFS I understand how to approach and solve this problem but facing difficulty in proving the “greedy stays ahead property” and also is it good to have proof of all greedy algos in contests as it seems quite time consuming

In short contests you want to be right and right the first time, even if you don’t have a solid proof, you should have at least some kind of reasoning as to why you’re greedy logic works. Ideally you should have some proof sketch in mind.

For that particular question, the problem of selecting maximum number of disjoint intervals (linked in the editorial) is very well known and is one of the first problems discussed on greedy algorithms. The major task you have (once you are familiar with the above problem) is to make the observation that you can consider people who prefer the same table separately and add the answer for each. I think this should be fairly easy to figure to out.

For the greedy property, you can think of it this way, initially you have some number of choices of people (say coming at s_i and leaving at t_i) to choose from, your goal is to maximize the number of people you admit. Who would be the first guy to choose? Say the first guy chosen is (s_k, t_k), then you won’t be able to choose anyone with starting time less than t_k. So the lesser the t_k, the weaker is you’re restriction on the second person you want to select. So I always want to choose a person with smallest t_k.

For a formal proof sketch:
Say you have a solution and you didn’t pick the guy with the smallest t_k, now there can only be one person intersecting with (s_k, t_k) that you had in your solution. (Work out why for yourself). If someone intersects with (s_k,t_k) remove him and add (s_k,t_k) instead. See that your algorithm (of choosing the guy with smallest t_k) never decreases the number of people you have.

This is a very common way to prove greedy algorithms. You assume that you have an optimal solution and you argue that tweaking it according to your hypothesized greedy property only makes the answer better.

These formal proofs are all nice and everything but as you can see most times a formal proof doesn’t really explain how to land at the algorithm in the first place. A formal proof is necessary to convince everyone that your solution works, but you should already have an idea as to why it does.

5 Likes