PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Implementation, Data Structures and a lot of patience ;).
PROBLEM:
Given N submissions and M tests for a problem. Judge wants only a specified subset of submissions to get AC. Submissions may fail due to TLE or WA. Judge can still decide time limit of problem, as well as test which will be used for determining verdict. It is also given which submission give correct answer on which test.
Is it possible to ensure that exactly those specified submissions pass? If Yes, print the Time Limit chosen and subset of tests chosen.
Let’s say, Good submission is the submission judge wants to pass and Judge wants to fail bad submission.
SUPER QUICK EXPLANATION
-
Just handle impossible conditions, then, on the test files which doesn't get WA on good people files, delete one by one in decreasing order of max time taken by good submissions. After deleting each test, check whether all Bad submissions fail. If yes, we have found the solution.
EXPLANATION
Warning, Implementation-intensive stuff ahead. (Kidding as usual :P)
This problem we are gonna solve sub-task wise, after few observations, which are in bold.
If a good submission fail on any test, that test can never be included in answer. Because, including this test case would fail one good submission at least, thus, not the ideal scenario for our judge.
I will refer the set of remaining tests as set of tests, or Tests in set.
After removing those tests which give WA on good submissions, we need to fail bad submissions. If all bad submissions are already failing, We have found the answer.
At present, Time limit used is the minimum such that all good submissions are passing all tests.
If at least one bad submission is passing, we need to see how to fail that very submission.
Since a bad submission is passing, it cannot have WA for any test for all tests in set, so the only way we can fail this is by getting TLE.
But since Time limit is already the lowest we can so as not to fail a good submission due to TLE, we need to delete the test, which take maximum time from all good submissions. This way, the Time limit can be further reduced, to the minimum such that all good submissions are passing on remaining set of tests.
But, one more problem is to handle the case, where, due to deleting a test file, a bad submission, may also start getting AC, since the test file, which was causing WA, was gone. So, we need to check those submissions too, which were earlier getting WA.
If you have understood the above, you deserve a try at practice section without reading further.
For first sub-task, we can do all this naively, since constraints are so small. Naive solution, which first remove tests giving WA on good submissions, then removing test files in order of decreasing max time taken by a good file, see if after deleting this test, and setting TL minimum to pass good submissions, is there any bad submission passing. If No, we have found our solution.
But for final sub-task, we need to speed things up.
We delete one file per step (step means checking, if set of tests is required answer). Every step is dominated by 2 things, finding the test to delete, and checking if a wrong submission passes. Both this things, we take O(N*M) steps naively. If we can do these steps in order of linear time, we solve the problem, since this step can be performed at most M times.
Let us discuss both of them separately.
Checking if a wrong submission passes
Let’s have an ordered multi-set for each problems, which have the times, this problem takes on every test file in currently in set. Since query time for multi-set largest element is O(logM), we can find the largest time this problem takes on any test file which is present in test. Whenever we remove a file from current set, we will remove from each multi-set, the time current problem takes on removed sub-task.
Hence, we can find the largest time each problem takes on any sub-task in set, in O(logM) time. So, we can iterate on problems, and see if it doesn’t get TLE, in O(N*logM) time.
Finding test file to delete
I will give you all an ancient trick where we will solve this problem, sort values of first array A on basis of second array B, bot of length M and 0 \leq A[i] < MX. Let us make a hash value A[i]+MX*B[i]. Here, if we sort these hash values, first value X will have lowest value B[i], second value will have 2nd smallest B[i] and so on. You can prove it easily. (If help needed, let me know)
Let us use above trick in this problem.
Create an array MX of length M, which have MX[i] maximum of time taken by any good submission on ith sub-task. We can use this array as basis of deleting indices. Get the index i which have maximum MX[i] and delete that test file. (Hint: MX array is array B, hint 2: ordered set can also be used for simpler implementation.)
In case we end up deleting all files, there do not exist any solution and we can simply print NO.
Otherwise, we can print the minimum time, within which all good files run in time but bad files either get WA or TLE.
This way, we have performed every step in O(N*logM) and there can be at most M steps, the overall Time complexity becomes O(N*M*logM) which is fast enough to pass second sub-task.
I know problem involves a lot of implementation, so you can refer solutions below for details. (Though i tried to clarify everything as much as possible.)
Time Complexity
Time complexity is O(N*M*logN) as has been discussed in editorial itself.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 