### PROBLEM LINK:

**Author:** Sergey Nagin

**Tester:** Jingbo Shang

**Editorialist:** Hanlin Ren

### DIFFICULTY:

Challenge

### PREREQUISITES:

Greedy, Heuristics, etc

### PROBLEM:

You are given a matrix A of size n\times n. You need to construct a matrix B of the same size. Initially all element in B is 0. By one operation you can choose 9 parameters a_1,a_2,b_1,b_2,c_1,c_2,d,l,r, and for all l\le i\le r, let

then set B_{i,j}\gets 1. You need to use as few as possible steps to construct such a B, that A and B has at most 100 different cells.

### EXPLANATION:

Iâ€™ll list some common approaches(that are used by more than one contestants) below.

## The most trivial one

Itâ€™s very trivial to generate a valid solution.

Let a_1=b_1=c_1=0,a_2=b_2=c_2=1,d=y,l=r=x, then we can use one such operation to make A[x][y]\gets 1.

Also this approach doesnâ€™t exceed the N^2 operations limit. It can get **3.21 pts**. A solution.

If you choose to ignore the last 100 1's, you can get **3.261 pts**, which is a little bit higher. A solution.

## Other approaches

Letâ€™s find consecutive 1's in a column. For any maximal(non-extendable) consecutive segment of 1's, we only need one operation to deal with. This approach gives you **36.365 pts**. A solution.

We can, of course, stop the algorithm when thereâ€™s at most 100 1's. However this only improves slightly to **37.512 pts**. A solution.

A smarter approach is to sort all non-extendable consecutive segments of 1's, and ignore the shortest ones of them until you ignored 100 cells. This gives a bigger improvement to **43.704 pts**. A solution.

Another approach: when we meet a_{i,j}=0 with a_{i-1,j}=1 and a_{i+1,j}=1, we modify a_{i,j} to be 1. Of course such modification canâ€™t be done more than 100 times, and some contestants choose to have at most one modification per column. If we didnâ€™t run out of the limit of 100 different cells, we use the sorting approach above. This gives you **43.915 pts**. A solution.

### ALTERNATIVE SOLUTION:

Please, feel free to discuss your approaches. As this is a challenge problem, there must be a bunch of different approaches!