Circles?

As I was doing some last minute practice problems before tomorrows CCC I thought of a possible mathematical paradox involving a simple geometric problem with circles. The problem itself is not the interesting part but the thought is:

As everyone knows, a circle is defined as the locus of all points equidistant from a center. Furthermore, a circle has both a diameter(d) and a circumference (c), and the relationship between the two is:

However, one must realize that pi is an irrational number (some of you might know where i'm going with this), which means we can never say with absolute certainty what the value is. Therefore, even if we know the diameter with absolute certainty, we can never know the circumference, and if we know the circumference with absolute certainty, then the diameter is in doubt. Therefore, we can say that one can never know both the diameter and circumference of a circle. Since a circle has to have both a definable diameter and circumference. We run into a mathematical paradox.

Then I began to think, "Ok, so what does this mean? What's the resolution to this paradox" and soon enough I compiled a list of possible outcomes:

1) There are no such things as circles or any other geometric figure that's dependent on pi.

2) String Theory is to blame as higher dimensions account for the uncertainty in circle geometry (ie. 2D Euclidean Geometry is a simplification even in the flattest worlds).

3) Pi is not a constant but somehow we say it is. Kind of like a mathematical illusion.

4) Pi is in fact a rational number.

5) Because Chuck Norris said so ..

Another thing to consider after this realization: Is circle uncertainty the mechanism behind Heisenberg Indeterminacy? If so, how does it effect observation?

... Worth a thought? At least this distracted me for a while so that I don't fall asleep before the competition.

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++