PROBLEMS - Editorial

Problem Link

Practice

Contest

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.

Some solutions using Quick Sort didn’t pass the time limit…If you check my solution for this question , i got a TLE while using QuickSort…But after changing the same code with Counting Sort got AC…Whereas some people did get AC even with QuickSort…Can someone explain the anomaly here??

You can also do it without using pairs.After calculating the difficulty of a problem by counting the number of Indices such that NSk>NSk+1 multiply it with 10^5+1 (Any other bigger number will work, we need a number with which a problem with lower difficulty level and very high index does not come up than a problem with high difficulty but less index) and adding it with it’s index i and now sort it.Now two problem with same difficulty will be ordered according to their indices.

here is my solution:

https://www.codechef.com/viewsolution/19438422

Can anyone provide some testcases ? @likecs

Can anyone tell me why me code not passing any testcase??

The code link is given below:-

Thanks in advance!!

I am getting TLE for subtask#2. can anyone help me out with my mistake. My solution is in java here
https://www.codechef.com/viewsolution/20223716

quick sort is O(n^2) in worst case…there will surely be a difference between there’s and your’s quicksort

Can somebody suggest the approach in C?