An optimization week

The Sep 24 - Sep 30 had two contests on Sunday; Open Cup 2018-19 Grand Prix of Eurasia was the first one (results, top 5 on the left). Team Past Glory needed just over one half of the allotted time to complete all 11 solutions and cruise to another well-deserved first place. Well done!

TopCoder SRM 738 followed a few hours later (problems, results, top 5 on the left, analysis, my screencast with commentary). tourist's advantage after the coding phase was so huge that even scott_wu's 150 challenge points did not bring him into contention. Congratulations on the win!

My screencast of this round is a great demonstration of stubbornness. The hard problem has two numbers in the input, but the most straightforward dynamic programming solution that comes to mind has a nice property: when solving the maximum possible case, it also solves all other possible cases on the way, so in a sense there's just one possible input.

The catch is: given that it's a straightforward dynamic programming solution, and this is a hard problem from a TopCoder round, it's kind of expected that the solution does not fit into the time limit, and one needs to think a bit and come up with a faster solution.

This was not the path I've chosen, though. My idea was: even though the solution does not fit into the time limit, it is only several times slower than required. Given that there's just one interesting input, we essentially have to speed up a concrete program on a concrete input by a few times. Let's forget about the problem statement and approach this speedup formally: let's try to change the program in such a way that the result does not change and the speed improves.

The first idea that brought me within 3x of the time limit was: let's find the computations that do not lead to changes in the dynamic programming array, and skip them. There's an inner loop which is less likely to do any changes as it progresses; let's record at which position does it do the last update for each iteration of the outer loop, and only run it until this point.

The problem is that, since we have 30000 iterations of the outer loop, this requires to add 30000 constants to the program, and the compiler doesn't like such large methods/classes. However, we can notice that this array of 30000 constants is quite compressible with run-length encoding.

Then I moved from 3x the time limit to 2x the time limit using one seasoned trick: switching from Java from C++ :)

In order to make the last 2x jump, I've essentially dumped the state of the program in the middle of its execution as another constant array. If the input lies in the first half, I execute the program from scratch, otherwise I start from the middle. Once again this state is 30000 numbers, and once again we can compress it enough using run-length encoding.

Coming up with all this required quite a lot of experimentation, and thus my score on the problem was not particularly good. The entire mess could be avoided by thinking a bit more algorithmically, of course :)

Thanks for reading, and check back for more!