Will TreeMap (BST) be able to solve this question in reasonable time?

You are given a list of up to 10^7 chess players and their ratings r in a competition. However, this competition uses a unique form of rating calculations. The task is to determine the rank of a player after a certain point in the competition.

During the competition, the following can occur:

A player joins the competition late. They are added to the list. If they share the same rating as another player, they are ranked lower as they came later.
Player A and B finish a game of chess. They have arbitrary performance ratings of i and j respectively, with the winner’s performance rating being higher. The winner will gain rating equal to the positive difference of i and j, and similarly the loser will lose rating equal to that amount. Input format: A i B j, 0 <= r, i, j <= 2^31 - 1
If a player’s rating drops to 0 or below, they are disqualified from the competition. (i.e. r - (i - j) || r - (j - i) <= 0)

Example:

input:

begin
CARLSEN 2900
CARUANA 2750
JIMMY 800
CARLSEN 2400 JIMMY 600
RANK CARLSEN
RANK JIMMY
LIAM 400
CARUANA 300 LIAM 3320
RANK CARUANA
RANK LIAM
PETER 4700
RANK PETER
end

output:

CARLSEN; RANK: 1; RATING: 4700
JIMMY; RANK: DISQUALIFIED
CARUANA; RANK: DISQUALIFIED
LIAM; RANK: 2; RATING: 3420
PETER; RANK: 2; RATING: 4700

explanation:

CARLSEN and JIMMY play. CARLSEN’s performance rating 2400 is greater than JIMMY’s performance rating 600, hence CARLSEN is the victor. CARLSEN gains 1800 rating, putting him at 4700 rating at rank 1, and JIMMY loses 1800 rating, putting him at -1200 rating and disqualifying him from the competition.

CARUANA and LIAM play. CARUANA’S performance rating 300 is lower than LIAM’s performance rating 3320, hence LIAM is the victor. CARUANA loses 3020 rating, putting him at -270 rating and disqualifying him from the competition, and LIAM gains 3020 rating, putting him at 3420 rating at rank 2.

PETER joins late with a rating of 4700. He has the same rating as CARLSEN, but he arrived later and is therefore rank 2.

This is practice for coding competitions, but I’m not sure how to go about this.

My current analysis is to use a BST, and every time a player’s ranking changes as a result of either:

a higher rated player entering the competition OR
rating changes after a game is played in the competition

that I rebalance the tree nodes to assign a proper ranking, but I’m not too sure that I can obtain the ranking in reasonable time for larger input sizes.

Furthermore, I need to somehow track the entry time and use it to deal with duplicated ratings, which I’m not sure how to do so.

Am I on the right track thus far at least?

Answer

It is fine for a ranking but every game played alters the comparison key, hence the tree structure would be corrupted, so you need to remove the players from the tree first, update the ratings, and add them back. Or you start with a new empty tree for every round.

Sorting an ArrayList would be the same.

And of course you need to find a played game, the two players.

     a:180
     /  
 b:160  c:200

When b:160 wins for c:200: the original tree would be corrupted.

     a:180
     /  
 b:200  c:160

That is searches, subranges, inserts and removals would go wrong.

Also finding b and c needs an additional mapping (like the player IDs being an index in an ArrayList).

Advertisement

Answer