PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Greedy
PROBLEM:
Find the maximum number of times a participant’s score can overtake another participant in a contest.
EXPLANATION:
The idea of this problem is to use a greedy algorithm. The idea is you should always make the person with the least score currently submit. It can be proven that this gives the optimal result. Now, for the first subtask, we can simulate this process naively. For subtask 2, we can use a priority queue to keep track of the scores of each person and sort them in increasing order at all times.
Time Complexity : O(nk log(nk))
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.