Problem Link
Author: Ashesh Vidyut
Tester: Mark Mikhno
Editorialist: Bhuvnesh Jain
Difficulty
EASY
Prerequisites
Sorting
Problem
Given P problems, each having S subtasks. Each subtask has a score and the number of users successfully solving it. First, sort the subtasks for each problem in increasing order of subtask score. Now, calculate the number of valid indices such that the number of users solving that subtask is greater than the next higher subtask. This number, n is the difficulty of the task.
Sort, the task in increasing order of difficulty.
Explanation
You are required to do whatever is just stated in the problem statement. In most languages, there is a support for “pairs” which is sorted internally in exactly the manner stated in the problem. Pair (x, y) is smaller than (u, v) is x < u or ((x == u) and y < v).
Further reading material for custom pair sorting comparators in C++ can be found here. For Java, you can read it here. In Python, pairs are represented as tuples. You can read more about it here.
The time complexity of the above approach will be O(P * S * \log{S} + P * \log{P}). The first term is for sorting the subtask list of each of the P problem. The second term is for the sorting the final list of problems based on difficulty.
The space complexity will be O(P + S). Note that it is not important to store all the subtasks for every problem which would lead to memory usage of O(P * S).
Once, you are clear with the above idea, you can see the tester implementation below for help.
Feel free to share your approach, if it was somewhat different.
Time Complexity
O(P * S * \log{S} + P * \log{P})
Space Complexity
O(P + S)
SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.