PROBLEMS - Editorial

editorial
, , , , ,
1

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.

2

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??

3

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

4

Can anyone provide some testcases ? @likecs

5

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

The code link is given below:-

Thanks in advance!!

6

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

7

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

8

Can somebody suggest the approach in C?

9

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

10

why its not working with same logic everything is same just the difference is that instead of map i used vector :C

11

My code for Problem Sort is mentioned below:

I did the following:

Input subtasks SC1,SC2…SCs and contestants NS1,NS2,…NSs

Sort subtasks(in increasing order of difficulty)

Created structure objects each having two int members(variables) storing ‘problem index’ and the variable ‘n’ as mentioned in the problem

Calculated ‘n’ for each structure object(one structure object=one problem).

Used qsort to sort the structure objects based on the value ‘n’.

Assigned indices to problems based on difficulty. Output indices of problems based on the difficulty.

I have randomly run a few test cases and all are coming out to be correct, however I am getting WA for all Test cases when I am submitting the code.

What is wrong in this code?

12

Why do we have to sort the submission count array? clearly the question says that the array will be given in increasing order. In this code, if I remove the sorting function for each problem, then the solution is not accepted, which is not making sense to me.

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define endl ‘\n’
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int p,s,hold;

vector<pair<int,int>> vec;

cin>>p>>s;
for(int i=0;i<p;i++){
    vec.push_back(make_pair(0,i+1));
     vector<pair<int,int>>arr(s);
    
    for(int i=0;i<s;i++) cin>>arr[i].first;
    for(int i=0;i<s;i++) cin>>arr[i].second;

    sort(arr.begin(),arr.end()); //Why Is This Line Required? The question says it's already sorted
    
    for(int j=1;j<s;j++){
        if(arr[j-1].second>arr[j].second) vec[i].first++;
    }
}
sort(vec.begin(), vec.end());
for(int i=0;i<p;i++){
    cout<<vec[i].second<<endl;
}
return 0;

}

13

understanding the Question turned out a bit difficult for me so I turned to the solution, so here’s the code—

#include

#include

#include

#include

using namespace std;

#define ll long long int

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);      //this is fast I/O (inputput output) use header file <cstdio>

ll p, s; cin>>p>>s;

vector<pair<ll,ll>>pb;

ll c = 1;

while(p--){

    ll n=0;

    vector<pair<ll,ll>>v(s);

    for(ll i=0; i<s; i++)

        cin>>v[i].first;

    for(ll i=0; i<s; i++)

        cin>>v[i].second;

   

    sort(v.begin(), v.end());

    for(ll i=0; i<s-1; i++){

        if(v[i].second>v[i+1].second)

            n++;

    }

    pb.push_back(make_pair(n,c));

    c++;

}

sort(pb.begin(), pb.end());

for(auto x:pb)

    cout<<x.first<<" "<<x.second<<endl;

return 0;

}

for the 1st tc –
3 3
16 24 60
498 861 589
14 24 62
72 557 819
16 15 69
435 779 232
the answers came out to be –
0 2
1 1
2 3
(i change the code a bit to see the dry run) but should it be 1 1, 1 2, 2 3 ?? how 0 2 can someone explain??

14

“You should sort the problems in the increasing order of difficulty levels.”