CCC 2009 Wireless

The Canadian Computing Competition is a prestigious programming competition for high school students with considerable programming experience willing to take on a challenge.

For over a year now, I have been rather struggling to solve the last problem from the 2009 senior section, Wireless. The reason I have been struggling was not that my solution didn't generate the correct outputs, but that the algorithm was not efficient enough to pass the SPOJ online judging system, with a rather strict time limit.

My original solution which was just straight forward 2D array processing, with an O(N log N) algorithm complexity failed to pass the judge as it exceeded the time limit. Mind you, this was implemented in Java, which I realize now is horrible for online competitions. Perhaps another time I will post my thoughts on Java vs C/C++.

Anyways, after several failed attempts, I decided to change my language to C++, and while talking with one of my friends, I came up with a rather odd sort and count solution that at the time I didn't think was sufficient enough.

Here is an outline of how it works:

On every row, all wirelesses have a (possibly empty) range of columns it covers.
This is translated into a set of commands for that row, consisting of a column number and the change in bitrate, with every wireless leading to two commands:
An increase in rate at the start of the range, and a similar decrease at the end of the range. By combining the commands and considering them in order of column number, the cumulative bitrates can be calculated over the range of the whole row.

NOTE: With N rows and K wirelesses, the complexity of this implementation is O(N*K*InK), the K*InK factor arising from the fact that a simple Quick sort is used to sort the commands, plus the fact that a Binary search is used to find the ranges within each row (Pythagoras). Better algorithms may be possible.

Once I coded this, to my surprise, it finally got accepted!
Time: 11.25 sec
MEM: 2.6 M

Now I have to prepare for the upcoming regional ECOO programming contest held at York University. Usually the problems are very trivial, so i'm not worried at all.

My SPOJ account

2009 CCC Wireless Solution C++