Hey guys. I've got a challenging programming problem for you, if you have an hour or two.
The question is called "
Pinball Ranking", and it's part of the "
Canadian Computing Competition".
All of the details of the problem are outlined here:
http://cemc.math.uwaterloo.ca/ccc/20...r/pinball2.pdf
Now, at first glance, this problem is deceptively simple. Intuitively, one will attempt:
for each score
insert a node
sort
obtain the index
summate
output the average
However, no matter how you choose to insert and sort, it's going to cost you at least
O(nlogn). Do that N times and you've got yourself an
O(n^2logn).
"But Saaaaaane!? What's so wrong with an N^2 algorithm? Surely I can't write anything better in 1 hour!" --You ask?
Well, sorry. You're right. You can't write anything better in an hour. But you will still have to. Because this is the CCC. If you want to win, you will need an
O(nlogn) solution written in an hour and a half. Tops.
See the attached input file? That's the file used by the judges to test your algorithm. An N^2 algorithm can't finish it. You would win the competition if you can solve that input file.
I've managed to write an
O(nlogn). It's small and simple. But rather difficult to implement within the given time.
I've emailed the professor who runs the CCC, and we've chatted about the algorithm complexity of this problem. He tells me that solutions exist that are simpler to implement than mine. He told me they involve dynamic programming to remember states, and there are some hashing tricks. But I can't think of anything...
I won't tell you what I did, as it may taint your approach. All I'll tell you is it can complete the attached input file in a couple seconds.
That would win the competition. But I want to see what you guys can do, and if you can figure out a solution that's more feasible for the alloted time.
I will post my solution once I get a couple of yours. Let's see what you've got PFO! Good luck.
