Computer Science Canada

[CCC 2005] Senior S5: Pinball Ranking
Author:  zylum [ 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 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
Author:  zylum [ Fri Mar 04, 2005 7:22 pm ]
Post subject: 
anybody wanna post a solution? mine probably times out for larger cases so im not going to post mine..
Author:  thegoose [ Sat Mar 05, 2005 8:52 am ]
Post subject: 
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.
Author:  zylum [ Sun Mar 06, 2005 5:57 pm ]
Post 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?
Author:  thegoose [ Mon Mar 07, 2005 7:03 am ]
Post 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.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy