Problem Link - Rank Fraud
problem statement -
Our friend the king decided to rank his ministers based on their ability to play table-tennis. He did not want to rely on chance upsets, so he asked his prime minister to organize a competition in which every minister played every other minister.
Needless to say, at the end of the competition, each minister had won a few matches and lost a few matches, so there was no conclusive overall winner. Time was running out to deliver the results to the king and there was no time to organize a tie breaker. In a fit of inspiration, it occurred to the prime minister that if he could present the king with a list of names in which every minister had beaten the next minister in the list, the king would be satisfied that he had ranked the ministers in order of their abilities at table tennis.
For instance, suppose that the ministers were numbered 1,2,3,4 and 5 and the results of the competition were as follows:
- Minister 1 beat ministers 2 and 4.
- Minister 2 beat minister 5.
- Minister 3 beat ministers 1 and 2.
- Minister 4 beat ministers 2,3 and 5.
- Minister 5 beat ministers 1 and 3.
Then, the prime minister could present the following list to the king,
~~~~ 4~~~~~~~~~3~~~~~~~~~1~~~~~~~~~2~~~~~~~~~5~,
because Minister 4 beat minister 3, who beat minister 1, who beat minister 2, who beat minister 5.
The problem to be solved is the following: Given the results of the competition, identify a winning sequence as described above, if such a sequence exists. There may be more than one such sequence. It is sufficient to find any one. If no such sequence exists, you should say that there is no solution.
Approach
The goal is to sort the ministers such that every minister in the sequence has defeated the next minister in the sequence. We use a comparison-based approach to determine the order. First, we store the results of the matches in a 2D matrix where is[i][j] is 1 if minister i beat minister j. Then, we create a list of ministers and use a custom sorting function. The custom sorting function ensures that a minister a comes before b in the sequence only if a has defeated b according to the matrix. After sorting, the sequence is checked implicitly because the sorting logic guarantees correctness if a valid sequence exists. If sorting completes, we print the sequence. If sorting fails or no valid sequence can be formed, the program would need additional checks, but this code assumes the input allows a valid solution.
Time Complexity
The time complexity is O(n^2logn), where n is the number of ministers.
Space Complexity
The space complexity is O(n^2) due to the 2D matrix used to store match results.