Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[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 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

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

Posted: Sat Mar 05, 2005 8:52 am   Post subject: (No subject)

See this problem:
And the solution:
The idea behind the solution of this problem is quite similar.
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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 5 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: