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