[CCC 2005] Senior S5: Pinball Ranking
Author 
Message 
zylum

Posted: Fri Mar 04, 2005 5:12 pm Post subject: [CCC 2005] Senior S5: Pinball Ranking 


[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 justended 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
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 





Sponsor Sponsor



zylum

Posted: Fri Mar 04, 2005 7:22 pm Post subject: (No subject) 


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





thegoose





zylum

Posted: Sun Mar 06, 2005 5:57 pm Post subject: (No subject) 


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

Posted: Mon Mar 07, 2005 7:03 am Post subject: (No subject) 


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. 






