LMATRIX2-Editorial

[djdolls]

PROBLEM LINK:

Practice
Contest

Author: Ivan Zdomsky
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

DIFFICULTY:

Challenge

PREREQUISITES:

Chinese Remainder Theorem

PROBLEM:

We are given a rectangle A, where each element has an initial value and an associated bound. The task is convert all the elements of the rectangle to zero by using minimum number of operations, where in a single operation a subrectangle is picked and a constant k is added to all elements in the subrectangle modulo its bound.

QUICK EXPLANATION:

Use Chinese Remainder Theorem to find which subrectangles can be made zero in a single move, and then use any rectangle cover heuristic to cover the whole rectangle using minimum number of subrectangles.

EXPLANATION:

First, we discuss which subrectangles can be made zero in a single move. If the initial value of an element is x, and its corresponding bound is P, then any k that can be added to this element to make it zero must satisfy the following:

(x + k) = 0 mod P
k = (P - x) mod P

Hence, if we want to make a subrectangle B zero by picking a single k, the chosen k must satisfy the following constraints:

k = (P_ij - B_ij) mod P_ij

Such k can be found using Chinese Remainder Theorem (if exists). Note that, here P_ij’s are not co-prime to each other. Hence, it is possible that the above equation may not have a solution. Let us see an example: suppose after considering a subrectangle, we got the following equations:

k = 5 mod 6
k = 2 mod 4
k = 6 mod 10

First, let us split the above equlities, so that each modulo correspond to a prime power. In the first equality modulo is 6, which consists of two primes 2 and 3, hence we can split this equality into two equalities:

k = (5 mod 2) mod 2
k = (5 mod 3) mod 3

i.e.,
k = 1 mod 2
k = 2 mod 3

In a similar way, other equalities can be split:
k = 1 mod 2
k = 2 mod 3
k = 2 mod 4
k = 0 mod 2
k = 1 mod 5

Now combine the equalities for the powers of a single prime together and see if they are consistent. In the above example k = 1 mod 2, k = 0 mod 2, and k = 2 mod 4 are not consistent, and hence, the equation has no solution. On the other hand, if we replace the equality k = 5 mod 6, by k = 2 mod 6, then the resulting equalities will be:

k = 0 mod 2
k = 2 mod 3
k = 2 mod 4
k = 0 mod 2
k = 1 mod 5

After reduction, we get the following equalities:
k = 2 mod 3
k = 2 mod 4
k = 1 mod 5

Here, all modulo’s are co-prime to one another, and hence there must exist a solution which can be computed using Chinese remainder theorem (k = 26 mod 60).

Since the all modulo’s in this question are smaller than 11, one could even preprocess all set of possible modulo equations and compute their solutions. There are (8 * 9 * 5 * 7 = 2520) such equations which have valid solutions.

Now that we know which subrectangles can be made zero in a single step, the problem is similar to dynamic set cover problem, where we want to cover all elements in the rectangle using subrectangles. One possibility could be to use a greedy heuristic, i.e., as long as the rectangle has at least one non-zero entry, pick the largest subrectangle that can be made zero, convert it to zero, and continue. We do not necessarily need to pick the largest subrectangle at each step as that would be computationally prohibitive, but any subrectangle which is large enough can be chosen. Instead of iterating through all subrectangles, one could iterate through a sample of them and pick the best among these.

Since the order of operations does not matter, we can also use Simulated Annealing like iterative method to optimize the already found cover by above greedy heuristic: In each iteration, we can split a chosen subrectangle into two, and merge two subrectangles together, if possible. Keep doing so as long as the time permits, and maintain the best solution found.

|---------| |---------------|             |-----------------------|
|         | |               |             |                       |
|         | |---------------|     ==>     |-----------------------|
|         | |-----|                       |-------------|
|---------| |-----|                       |-------------|

In the above example, we can split the leftmost rectangle, and then it could possibly be merged with the other two rectangles, to reduce the number of suberctangles by one.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

[mugurelionut]

In my solution I also used rectangles which do not make all the elements inside of them zero. This was better for my approach, but it also added extra complexity, meaning that the algorithm was overall slower (so I couldn’t run multiple iterations). My approach was to “compress” the part of the matrix containing non-zero elements as much as possible. Let’s assume that the matrix contains non-zero elements only between the rows rmin and rmax. Then I associated a weight to each cell of the matrix - larger weights for cells on the rows rmin and rmax and lower weights for the other cells, depending on the distance to rmin and rmax. Then I tried to find a rectangle having the largest total weight and having one of its sides on rmin or rmax (or even both). The weight of a rectangle is the sum of the weights of the non-zero elements becoming zero minus the sum of the weights of the zero elements becoming non-zero. That means that for a given rectangle we do not know immediately which value of k to use (the one maximizing its weight). So I used a kind of pruned backtracking in order to find the best value of k for each candidate rectangle (this is the part which took most of the time and which only allowed me to run one iteration of this algorithm). Of course, I also bounded the size of candidate rectangles in order for this approach to work in time and I also used some caching in order to not recompute the weight of each candidate rectangle at each step (instead, it would be recomputed only when necessary). The average absolute score of this approach was around 22.8, which was about 90% of the score of the winner (@ACRush).