Task authored, prepared, and written editorial by: Timur Degteari
For tests satisfying n,m <= 50 we can use brute-force: we iterate over all possible values of (those are 1, 2, \dots, m-1, note that for d \geq m Mister IP will never remove any test), and for each pair we iterate over all 1 \leq k \leq m, and explicitly count how many of them satisfy a_{i, k} > a_{i, j}, and mark whether test is "useless" for solution given the value of . After that it's only left to calculate how many tests are being removed to check whether this value of works. By taking the maximum which removes enough tests we find the answer. If no value of works, we output . The time complexity of this solution is O(n m^3).
For tests satisfying n, m <= 400 we can improve the solution above. If for each pair we precalculate how many there exist such that a_{i, k} > a_{i, j}, then for a fixed and a pair we can tell in whether test is "useless" for solution . Precalculating is possible naively — for each we iterate over all 1 \le k \le m. This is done in O(n m^2). Checking each value of takes time, and since there are m-1 values of to check, the time complexity of this is O(n m^2), and hence this whole solution takes O(n m^2) time.
For the full solution, we need to optimize two things — calculating for each how many satisfy a_{i,k} > a_{i,j}, and finding the appropriate value of . For the first part we can, for each , sort the array of pairs \{a[i][j], j\}, after which the number of such 's will be equal to (the position of in the sorted array). For the second part we can observe the following — if for some value of and a solution , test is "useless", then it will be useless for d-1 as well. This, now, means that if for some , test got removed, for d-1 it would be removed too. This allows us to binary search on the value of — by setting binary search bounds to be [0, m-1], if we end up in , the answer is , otherwise we've found it with binary search.