### PROBLEM LINK:

**Author:** Ivan Zdomsky

**Tester:** Hiroto Sekido, Gerald Agapov

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Challenge

### PREREQUISITES:

### 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.