2005 Canadian Computing Competition, Stage 1

Problem S5: Pinball Ranking

Pinball is an arcade game in which an individual player controls a silver ball by means of flippers, with the objective of accumulating as many points as possible. At the end of each game, the player's score and rank are displayed. The score, an integer between 0 and 1 000 000 000, is that achieved by the player in the game just ended. The rank is displayed as "r of n". n is the total number of games ever played on the machine, and r is the position of the score for the just-ended game within this set.

More precisely, r is one greater than the number of games whose score exceeds that of the game just ended.

Input

You are to implement the pinball machine's ranking algorithm. The first line of input contains a positive integer, t, the total number of games played in the lifetime of the machine. t lines follow, given the scores of these games, in chronological order.

Output

You are to output the average of the ranks (rounded to two digits after the decimal) that would be displayed on the board.
At least one test case will have t ≤ 100. All test cases will have t ≤ 100 000.

Sample Input

5
100
200
150
170
50

Sample Output

2.20

Explanation

The pinball screen would display (in turn):

1 of 1
1 of 2
2 of 3
2 of 4
5 of 5

The average rank is (1+1+2+2+5)/5 = 2.20.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 128M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

is there any other way to speed up my binary search tree?

Nice that you learned how to code a binary search tree. So, Jacob tried the same, and he also got only 90/100. The last test case is specially designed to be worst-case in terms of runtime, so you probably can't pass it using a binary search tree. Try a different approach.

Must you use a balanced binary search tree for full marks?

nope! ((i recommend a binary indexed tree))
[url]http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees[/url]

Was the time limit lowered?

Since the recent grading system change, execution times are now recorded more accurately. We noticed that certain O(N^2) algorithms were previously able to pass, so the time limit has been adjusted accordingly.

Just a question -- Isn't my 80/100 solution a O(n log n) solution?

Edit: I guess I'll just use a BIT. Thanks Brian!

What do you think is the time complexity of inserting an element into an arbitrary position in an ArrayList?

An issue has recently come up with Java rounding a real number differently than C++:

One of the cases has an answer which evaluates to *exactly* ?.?45. This should be rounded DOWN to ?.?4, not up to ?.?5.

It turns out that the result ?.?5 is produced when C++ long doubles are used (or similar higher-precision real variables in other languages), instead of just doubles. This absolutely seems like it should be correct. However, for convenience, we'll continue to go with the answer ?.?4.

glibc uses the [url=http://en.wikipedia.org/wiki/Rounding#Round_half_to_even]round half to even[/url] convention. This is now [url=http://wcipeg.com/wiki/Judge:Writing#Output]officially endorsed[/url].

Based on the definition of r, am I right in saying that if the scores are 100, 100 and 100, all scores are of rank 1?  Or are tied scores ranked based on date added?

[quote]More precisely, r is one greater than the number of games whose score exceeds that of the game just ended.[/quote]The problem statement tells you exactly how the rank is defined. Determining from the problem statement whether this means there are ties, or however you want to put it, is part of the contest coder's skill set (and also serves the programmer well in real life, in which project specifications are often written by incompetent managers).

Would an insertion sort run in time for all test cases or is a binary search the only one that will

You have to be a bit creative with the insertion.

Just a question of curiosity - did u use insertion sort? (yes, no, maybe so ...)

All the < 0.2s solutions use a binary indexed tree. (not the same as a binary search tree!)
However, all the other solutions use some sort of insertion sort.

Actually there is one solution that uses mergesort.
However, you have to be extremely clever with mergesort - this solution only sorts once (instead of [i]t[/i] times), the entire list of scores. If you sort [i]t[/i] times, as you normally would, you'll still TLE.

Who used mergesort? From what I can see everyone who solved it used insertion or BIT no?

I used mergesort (it was not an original thought however, credit must go to Sean Henderson, former PEG leader.) However, that code was inadvertently deleted, so you can't see it anymore.

WHen i changed the variables to real (etc.), my program worked for most of the testcases faster - but more of the testcases overall became TLE. Why?

What does that error mean o_O? 
Test Case #10: Hardware failure [1.468s, 600K] (0/10)

This means you went wayyy out of bounds.