Sane's Monthly Algorithms Challenge: November 2008
Intelligent Stats (Guru Level)
You are a computer scientist for a popular online game which hosts
one-on-one chess games between players across the world. After each
game, the username of both players is recorded in the website's
database, along with the username of the player who won.
The website has statistics for the Wins and Losses of each player. However, these statistics are poor representations since the most active members can increase their win count by 'picking' on bad players with low win-loss ratios. Some also cheat by playing against their own alternate accounts.
To help reduce this problem, they want to add an intelligent stat to each user, which indicates how many players the user “can” beat, given the playing history of all players and the following logical rule:
Player A can beat Player B if and only if Player A and Player B have different usernames and:
Player A has beat Player B
Player A has beat Player C and Player C can beat Player B.
This statistic will hopefully provide an incentive for users to compete against better players, and to not repeatedly pick on the same person.
Your job is, given the database of playing history, generate the database containing this new statistical attribute for each player.
InputThe first line contains an integer
nlines each contain two alphanumeric names of lengths no longer than 20, separated by a space. This line indicates that the first user “has” beat the second user. Names are case sensitive. A player can never play against himself.
OutputOn the first line, output an integer
k≤ 20,000), representing the number of distinct names mentioned in the input file.
For each of the next
klines to follow, output a name you have not yet mentioned in the output file, followed by the number of users he/she “can” beat (the order of the output file does not matter).
Point Value: 10 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: Jan 15, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3