Problem Link - Draw Fixing
Problem Statement
Siruseri happens to have some of the best chess players in India and one of the most important events in the Siruseri sports calendar is the Annual Chess Challenge where teams from Siruseri and Navalur compete.
The event is held alternately at Siruseri and Navalur. This year the tournament is to be held at Sirseri and the Secretary of the Siruseri, who is up for re-election this year, would like to ensure a win for Siruseri. Since starting a war or accusing Navalur of possessing weapons of mass destruction is beyond his scope (and he also has a few more brain cells than the average leader of the free world) he decided to do something clever. Draw Fixing!!
To understand what he intended to do, we need to know how the Chess Challege match is organised. Both Siruseri and Navalur are required to send N players. Every player from both teams participates in exactly one game (and so exactly N games are played). The host is expected to draw lots to determine who plays who. Our secretary plans to fix this draw so that the pairings are exactly as he wants them to be.
Each chess player has a ELO rating indicating how good he is. The higher the rating the better the player. The secretary knows the rating of each of the players in the Siruseri and Navalur teams and he would like to pair them up so that the number of pairs in which the Siruseri player has a higher ELO rating is maximised.
Approach
To solve the problem, first, we sort both teams by their ELO ratings in ascending order
. This helps us pair players strategically. Starting with the weakest player in Navalur, we check if Siruseri’s weakest unpaired player has a higher rating. If so, we pair them together, as this guarantees a win for Siruseri in that match. If not, we pair Siruseri’s weakest unpaired player with Navalur’s strongest unpaired player. This ensures that we minimize the loss for Siruseri by not wasting stronger players on unwinnable matches. This process continues until all players are paired. The result is the maximum number of matches that Siruseri can win, and the pairing order for all matches is determined accordingly.
Time Complexity
The sorting step dominates the complexity, making it O(N \log N).
Space Complexity
The space complexity is O(N), primarily due to the storage of the player pairs and results
.