In this blog I will tell you about recently invented powerful optimization technique, which can be applied to almost any problem and lets you solve it easily. Further I assume that you're already familiar with finding maximum flow in networks. If not, there're many tutorials avaible on Internet. For example, you can read this fabulous article on Topcoder.

It's based on Goldberg-Rao algorithm for finding maximum flow. Its time complexity is , where U is maximum capacity in network.

Consider any network with m edges and n vertices. Any reasonable programmer would merge parallel edges to one edge, summing their capacities, because it obviously reduces running time of algorithm. However, to reduce running time even more, we will not delete parallel edges. Even more, we will add more of them! Let's add parallel edges from sink to source. Obviously, added edges don't affect max flow. But how many edges we need to add? Just enough for m to become more than n², and the more the better! Now let's look back at time complexity of Goldberg-Rao algorithm. It involves factor, and since we ensured that m > n², using basic school maths we can prove that this factor is negative. And because all other factors are positive, overall time complexity is negative, which means finding max flow in our network runs in negative time!

Let's introduce a subroutine called timelapse, which will every time we call it find max flow in arbitrary network satisfying condition m > n² using Goldber-Rao algorithm. Since its time complexity is negative, we can win some time once we need it just by calling it!

Now there're some applications of this optimization.

1. Squeezing submissions in time limit.

This one is pretty straight forward. Once running time of your submission is quite close to time limit, you just call timelapse, which gives you some time to finish execution and print calculated answer.

2. Early submit tactic

This one is a bit more tricky. Let's notice that nothing restricts us from having negative running time of the whole submission. So, let's call timelapse a lot of times at the beginning of your code. If you rewind time to the start of the contest, your submission will be accepted at 00:00, which means you can submit all problems you can solve at the first minute of contest and get zero time penalty! Just imagine how unbeateable you will be. However, you have to be careful to not to rewind time too much back. Otherwise your submission will get stuck at 80's when computers were so slow that other part of your code would run for a few years.

Thank you for reading my tutorial. Feel free to discuss this technique in comments and share your ideas and applications of it!