[CCC 2005] Senior S5: Pinball Ranking

[zylum]

[CCC 2005] Senior S5: Pinball Ranking

Pinball is an arcade game in which an individual player contrils a silver ball by means of flippers, with the objective of accumilating as many points as possible. At the end of each game, the player's score and rank are displayed. The score, an integer betwee 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.

Your 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. Input contained in the file s5.in.

Your 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

code:

5 100 200 150 170 50

Output for Sample Input

code:

2.20

Explanation for Sample Output
the pinball screen would display (in turn):

code:

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

[zylum]

anybody wanna post a solution? mine probably times out for larger cases so im not going to post mine..

[thegoose]

See this problem:
http://www.boi2004-plovdiv.org/tasks/team.pdf
And the solution:
http://www.boi2004-plovdiv.org/tasks/solutions/1.2.team.rtf
The idea behind the solution of this problem is quite similar.

[zylum]

here's a solution i came up with which employs a binary tree. it solves a random case with t = 100000 in under 35 seconds... the worst case will probably be much more since i didnt bother balancing the tree. in my solution the worst case would be when the scores are either ascending or descending (both) in which case my algorigthm will run in O(N^2).

code:

var tree : collection of     record         score, bigger : int         l, r : boolean         left, right :  ^tree     end record proc newNode (var node : ^tree, val : int)     new tree, node     node -> score := val     node -> bigger := 0     node -> l := false     node -> r := false end newNode proc addNode (node : ^tree, val : int)     if val <= node -> score then         if node -> l then             addNode (node -> left, val)         else             newNode (node -> left, val)             node -> l := true         end if     else         node -> bigger += 1         if node -> r then             addNode (node -> right, val)         else             newNode (node -> right, val)             node -> r := true         end if     end if end addNode fcn traverseTree (node : ^tree, val : int) : int     if ~node -> l and ~node -> r then         if node -> score <= val then             result 0         else             result 1         end if     end if     if node -> score <= val then         if node -> r then             result traverseTree (node -> right, val)         else             result 0         end if     else         if ~node -> r then             if node -> l then                 result traverseTree (node -> left, val) + 1             else                 result 1             end if         else             if node -> l then                 result traverseTree (node -> left, val) + node -> bigger + 1             else                 result node -> bigger + 1             end if         end if     end if end traverseTree var FI : int open : FI, "s5.in", get var T : nat := 0 var N : int var temp : int get : FI, N get : FI, temp var root : ^tree newNode (root, temp) T += traverseTree (root, temp) + 1 for : 2 .. N     get : FI, temp     addNode (root, temp)     T += traverseTree (root, temp) + 1 end for put T / N : 0 : 2 put "\ndebugging:" put "run time: ", Time.Elapsed / 1000, " seconds" put "sum of rankings: ", T

here's the code i used to generate random test cases:

code:

var f : int open : f, "s5.in", put const N := 1000 put : f, N for i : 1 .. N     put : f, Rand.Int (0, 1000000000) end for

if anyone has the actual test cases can you please test this solution?

[thegoose]

zylum wrote:

here's a solution i came up with which employs a binary tree. it solves a random case with t = 100000 in under 35 seconds... the worst case will probably be much more since i didnt bother balancing the tree. in my solution the worst case would be when the scores are either ascending or descending (both) in which case my algorigthm will run in O(N^2).

Hint: discretize the data so you know what to expect, then CREATE THE TREE IN ADVANCE.