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.


The first line contains an integer n (1 ≤ n ≤ 10,000).

The next n lines 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.


On the first line, output an integer k (2 ≤ k ≤ 20,000), representing the number of distinct names mentioned in the input file.

For each of the next k lines 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).

Sample Input

Jim Denise
Noobie111 AwesumChessPlyr1337
Gerald AwesumChessPlyr1337
AwesumChessPlyr1337 Denise
Denise 2GudAtChessLOL
2GudAtChessLOL AwesumChessPlyr1337
Jim Gerald

Sample Output

Jim 4
Gerald 3
Noobie111 3
Denise 2
2GudAtChessLOL 2
AwesumChessPlyr1337 2


All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: Jan 15, 2009
Author: DrSane

Languages Allowed:

Comments (Search)

Case 10 and 12 keep giving me WA...are there any special things in the problem statement I'm not noticing?

As far as I can tell from the program that generated them, there's nothing special about those two test cases that would make you fail them individually. Make sure your data structure(s) aren't running out of room or anything along those lines.

Edit: Nevermind. I see you passed. Congrats. :)

Thanks for the quick reply, I realized what was special about them (though they may seem not special at all). You were right, room was the thing that I was lacking. Accidentally looping through N as the number of vertices rather than the actual number, thus getting WA. :)

Great problems! Do you think of an algorithm first and then make up a problem?

Sometimes. I usually try to think of a real life problem and a list of possible variations, then think of several algorithmic solutions, and tweak the problem to make it require the more interesting solution. Working backwards from a solution usually makes for somewhat boring problems (like this one). I have a whole stack of newer and better problems, but am waiting to post them until after I get the opportunity to train the IOI 'fellas in Waterloo.

Hehe, I'll see you there then. They still have not told us about anything regarding any training... Do you know any specific dates?

Congrats on your achievement. You should get an e-mail or letter from Troy soon. I haven't actually spoken to him since Stage 2 so I do not know what's happening with your training. All I know is that I have some problems and I'll be in UW at that time, but I work full days so I can't be there in person.