Codejam 2015 - Round 3 - Runaway Quail

5 Jan 2016

I cannot solve this problem because I cannot write a proof. That actually happens quite a lot. I can imagine an axiom which turns out to be wrong because I cannot write a fucking proof.

For this problem, I kind of feel that we should chase after the fastest quail only. It is almost right. It turns out that we only care about the fastest quail and the slower ones that are further. Brute-forcing only those cases is fast enough to solve the large problem set.

Ok, let's write a proof.

First, the axiom is “It's always better to catch the fastest one that is further”. For example, if we have p0 = 3, s0 = 3, p1 = 2, s1 = 2, we don't need to try p1 because that case is always worse.

The intuition is that, if we don't catch p0, it will go even further. If we catch it now, we pay X. But if we catch it later, we definitely pay X + d. Therefore, we should catch it now.

What about a case where p0 = 3 and p1 > 3? Should we go for p1? In this case we have to try both because it depends on the other side as well. If p0 go beyond p1, then we should catch p0 first. If p0 doesn't go beyond p1, we can go the other side and catch p1 later.