Sane

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:


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.

Attached Files

s5.txt (975.8 KB, 15 views)

titaniumdecoy

You never have to sort the array; instead, assume it is already sorted each time and insert the new score at the appropriate position. This position can be found in O(logn) using a binary search. The resulting algorithm will be O(nlogn), assuming you are using an appropriate data structure to hold the scores.

Sane

The problem with that... is upon worst case, an unbalanced binary tree takes N operations to inject... O(N^2).

So you have to balance it via tree rotations (my solution) O(logn + k) x N = O(nlogn + nk) = O(nlogn). It's not a very quick thing to implement, and the professor said there are better tricks with DP.

Try it.

titaniumdecoy

Interesting problem. I am sure there is an easier way to do it.

Sane

You're right. I was hoping that too. There should be an easier way to do it, but apparently there's not. He told me the whole point of the question is it's deceptively simple. There is no simple way to get something faster than an O(N^2) algorithm, but there is a way that takes a shorter amount of time to code.

titaniumdecoy

I realized the problem with that right after I posted.

What language(s) are you allowed to use? If you can use a language like Java there is the possibility of using one of the built-in data structures which might simplify things.

Klipt

Apart from a balanced binary tree, you could probably use a red-black tree, radix tree or skip list. I think a radix tree might be easiest...

The STL has built in red-black tree implementations for sets and maps, but unfortunately there's no fast function giving the number of elements (<x) in a multiset.

The Java TreeSet class has a tailSet function which would work perfectly, except that there is no time guarantee, and I don't know whether Java supports multisets.

__________________
Get PLT Scheme|SB Common Lisp|Haskell|wxDev-C++|Python

Sane

In the first stage (this question is a first stage problem), you can use any language, except for a symbolic programming language like Maple.

In stage two, you can use C, C++ and Pascal. Java is pending permission for usage, after it's discovered whether or not it will be used in the world-wide competition.

I'm only using a language that can be used in stage two, so that I will be properly practiced. Java may not be allowed for stage 2.

Edit: Seems kind of cheap to me, how us C people get stuck implementing algorithms supported by Java's standard libraries.

Klipt

Most of the functionality is covered by the STL. (I assume by C you mean C/C++ ... using pure C is unnecessarily Spartan.) It's the Pascal people who really get screwed on standard libraries.

__________________
Get PLT Scheme|SB Common Lisp|Haskell|wxDev-C++|Python

Arevos

This challenge is more difficult than it looks, because you need to have an O(N log N) for the worst as well as the average case.

The obvious solution is to use a balancing tree structure to store your data. That'll give you a log N insertion time for N items, which is the solution that Sane has opted for. It was my initial solution, too.

However, I'm wondering if there isn't a more subtle way to solve this problem. You only need the average of the ranks. Is there a way to reason about the average without necessarily storing every ranking?