BJUDGE - EDITORIAL

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

Till above links are not available, refer setter’s solution here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like

I am having a little doubt if a subset of size K is selected and a time limit can be set for this to get the desired result. Then can’t we have any subset of size <= K to get the desired result?

Can’t be

YES

8 1

2

NO

a correct solution for the sample testcase?

Time complexity can be reduced to O(m*n) by pre-processing.

For each submission, precompute whether the problem has WA for atleast one of the first j chosen tests ( in sorted order) and the maximum time the submission has taken in the first j tests.

Recurrence:

deleted[i][j]=(1-b[i][j]) | deleted[i][j-1] (where deleted[i][j]=1 if the ith submission has WA in atleast one of the first j tests.)

time[i][j]=max(a[i][j], time[i][j-1])

2 Likes

If a bad submission is getting AC for all tests then why don’t we set the new time limit as maximum of time take for all tests for this bad submission - 1, and then check in good submissions if there is some tests which is getting TLE if there is such test we simply delete that test. This approach seems better still i am getting WA for 1st and 2nd test files.
My code:
LINK any help will be appreciated.

There may exist multiple correct solution, in which case, you can print any of them.

All subsets of size <= K may not be valid. One of the test case might be stopping some bad submission by WA. Though some subsets are valid, depending upon that very test case.

For the sample test case, Yes, that too will pass.

I think in this editorial , you don’t have the proof of your solution , why do we only remove columns in matrix based on maximum Time by a good file ? What is the proof that this is the best way to go to ensure a solution ?

Thanks.