PROBLEM LINK:
Author: Nikhil Garg
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
CHALLENGE
PREREQUISITES:
None
PROBLEM:
You are given a matrix M of the size H × W with integer elements. You need to find some its submatrix with large sum. You score depends on the sum you find. In order to get AC your sum should be positive. It is guaranteed that such submatrix exists. By submatrix we mean some matrix that can be obtained from the given one by removing some of its rows (maybe none, but no all) and removing some of its columns (again maybe none, but not all).
EXPLANATION:
Since submatrix with positive sum exists then there exists at least one positive element in the matrix. Hence in order to get AC you just need to find r and c such that M[r][c] > 0 and print
1 1
r c
Since we have some tests with very low number of positive elements we suggest to start any arbitrary smart solution with initializing the answer by this simplest correct submatrix.
The good idea how some smart solution can be started is the following. Assume that the set of rows of the submatrix is fixed. Than the optimal set of columns will be exactly those columns for which the sum of elements in this column in the selected rows is positive. The same can be applied when the set of columns is fixed.
Now several strategies can be used using this idea:

Choose a random subset of rows (or columns) and find the optimal subset of columns (or rows). Do this multiple times and choose the best. See author’s solution as a reference.

Choose a random subset of rows and find the optimal subset of columns for it. Then find the optimal rows for these columns. Then find the optimal columns for these rows and so on till we stop making the progress. See tester’s solution as a reference.
Also different types of hill climbing are possible. Start with choosing a set of rows and a set of columns. Then at any stage either add new row, delete a row, add new column or delete column so that the sum increases. Keep doing this till time permits. Simulated Annealing or beam search could also be done using this neighborhood criterion.
As usually all contestants are welcome to describe their strategies.
The natural question arises. Why we can’t find optimal answer in reasonable time?
The reason is that this problem is equivalent to Maximum Edge Weight BiClique Problem (MEWBCP), which is known to be NPcomplete. What does it mean? Consider a complete bipartite graph G having W vertexes in the first part and H vertexes in the second part. Let edge between rth vertex from the first part and cth vertex from the second part has the weight M[r][c]. Then it is clear that any submatrix of M corresponds to some biclique (complete bipartite subgraph) of G and the sum of this submatrix is the sum of edges in this biclique.
The problem is NPcomplete since we can reduce the classical NPcomplete maximum clique problem to it. The reduction is quite simple and can be found here.
Finally, we mention that tabu search can be applied in this problem. You can read about it in this paper. Here authors consider MEWCP (Maximum Edge Weight Clique Problem). But it is clear that MEWBCP is partial case of MEWCP when weights of edges inside each part of the graph are zero. The authors formulate MEWCP as unconstrained binary quadratic program (UQP). In our case it takes the form.
maximize sum(M[r][c] * x[r] * y[c] : 0 ≤ r < W, 0 ≤ y < H)
subject to x[0], x[1], …, x[W − 1], y[0], y[1], …, y[H − 1] are in {0, 1}
Note that the variables here have very simple meaning:
x[r] = 1 if and only if the rth row is chosen;
y[c] = 1 if and only if the cth column is chosen.
The authors of the paper wrote that they can solve optimally the instances of MEWCP for graphs with thousands vertices using tabu search for this UQP. This approach described in detail in this paper. You can learn more about tabu search here (homepage of its creator).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
But it currently gets WA since the init by 1 × 1 submatrix with positive element is not made.
Tester’s solution can be found here.
It gets the score 3084.54887261952. Note, that the winner’s score is 3096.0084244532. So, even such relatively simple solution gets the high score. That is why we have such close scores among the top contestants.