PROBLEM LINK:
Author: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Vaibhav Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Sorting, Data Structures, Implementation
PROBLEM:
Given N submissions, M test cases, A array representing time taken and B array representing whether particular test case for a submission has passed. You are required to decide test cases and time limit to pass submissions where D=1.
QUICK EXPLANATION:
We firstly remove those test cases for which B=0 for our AC submissions. Then we will store all pairs of test cases which can be chosen and corresponding time limit for our AC submissions to pass in a list in a sorted fashion. Then we will compare time limits with every maximum time taken by our non-AC submissions. When time limit is less than maximum time taken by all non-AC submissions we print all considered cases.
EXPLANATION:
It must be clear that we won’t consider all those test cases for which B=0 and D=1 otherwise it will become a WA submission. It must also be clear that time limit would be maximum of time taken by every AC submission for every test case we are considering.
Now we will make a list of pairs in which we will be storing all test cases possible along with its time limit in sorted fashion(increasing order of time limit). We will calculate time limit for j test case by iterating through time taken by all AC submissions for that case i.e. TL=max(TL,A[i][j]) for D[i]=1.
To make it easier, we will make A=\infty for every corresponding B=0, a set TC which will store test cases for our answer and an array C storing maximum time taken for every non-AC submission till cases in TC.
Now, we will iterate through our list. For every pair occurring, we will check if time limit is less than maximum time taken by every non-AC submission i.e. TL<C[i]. C[i] will be calculated as C[i]=max(C[i],A[i][j]) where j is test case. As soon as TL<C[i] for all non-AC submissions answer will be “YES” and we will print current TL, size of set TC and test cases stored in it.
We know that even if a single test case is WA/TLE, submission will be considered non-AC. Hence, if we get C[i]=\infty it means atleast one case is WA for i non-AC submission and submission will actually become non-AC and if we get TL<C[i] it means atleast one case will give TLE and submission will become non-AC. Hence, for every submission we need to check TL<C[i].
The TL will appear in increasing order. If we do not sort, then we might check the condition for larger TL earlier and it may not lead to “YES”.
TIME COMPLEXITY
Time complexity is O(N*M+NlogN).
AUTHOR’S AND TESTER’S SOLUTIONS:
Editorialist’s solution can be found here.