Problem Link - Soccer League
Problem Statement
The new season of the Bytelandian Premier League (BPL) has started!
In the BPL, any two soccer teams play with each other exactly once. In each match, the winner earns 3 points and the loser earns no point. There is no draw (if the match is level after the two halves, two teams will take part in a penalty shootout to decide the winner).
At the end of the league, the winner is the team having the largest number of points. In case there are more than one team which has the largest number of points, these teams will be co-champions of the league.
The league has been running for some time. Now, the following problem has arisen: we would like to know if a specific team still has a chance of winning the league.
Approach
The problem is solved by analyzing the results of matches. The number of wins (wins[i]
) and unplayed matches (unplayed[i]
) for each team is tracked. The highest current score (score
) is determined by iterating over the results of all matches. Then, it is checked whether adding the maximum potential points from unplayed matches allows a team to equal or surpass the current highest score. If a team cannot potentially achieve the highest score, it is marked as having no chance (0). Otherwise, it is marked as having a chance (1).
The logic also considers the scenario where unplayed matches between top teams might increase the score further if they directly impact the current leading teams’ wins. This ensures a thorough assessment of all possibilities for championship contention.
Time Complexity
The time complexity is O(n^2), as the code iterates over all n \times n match results in the league.
Space Complexity
The space complexity is O(n), as arrays wins
and unplayed
are used to store data for n teams.