### PROBLEM LINK:

**Author:** Gerald Agapov

**Tester:** Shang Jingbo and Gerald Agapov

**Editorialist:** Devendra Agarwal

### DIFFICULTY:

Challenge

### PREREQUISITES:

Greedy.

### PROBLEM:

Given an empty matrix of NxM , fill the matrix with G,C,A and T.

The matrix will be stable if it contains K different submatrices. Your aim is to fill the matrix with A,C,G and T such that the difference between the number of different submatrices in matrix and number K should be as small as possible.

### Explanation:

This problem is a challenge problem. For challenge problem , you should aim at finding some approximate/partial solution using algorithms like greedy , dp , etc…

For this problem , let us break the problem in cases :

**Case 1 :** For small n and m where n * m<=10

This case can be solved using brute force. Try all possible matrices and then find the matrix which gives the best possible estimate. All possible matrix are 4^{n*m} , and each matrix can be checked for different submatrices in O(n^{2}*m ^{2}) time . You need to be little careful in this method because test cases may go to 100 , so use this approach only if 4^{n}*m*n

^{2}*m

^{2}<= (4 * 10

^{8}) / Total_Tests

**Case 2 :** A more generic case with any N,M and K.

First start with all ‘A’ in the matrix , then try to change each element of the matrix randomly and check if it gave a better estimate or not. But checking after changing each element may lead to TLE because time complexity for that will be T* n^{3}*m ^{3} where T is the Total_Tests.
So, instead of checking after changing at each box , we can use any strategy to reduce number of checks. One simple idea is to check only log(N*M) times. Start with changing first (N * M)/2 elements and then keep on decreasing the number by 1/2 . So time required is T * n

^{2}*m

^{2}

*log(n*m) <= 100 * 15

^{4}* 10 < 10

^{8}

We will use greedy approach in our selection , we will pick up only those changes which will take us close to K.

Now you can still make some random iterations in which you pick any two elements of the matrix and swap them and then check for number of different sub-matrices. If we get close to K , we accept those changes otherwise we reject it.

You can try some more random strategies here : by fixing an element of the matrix and choosing the other element for swapping.

Be careful on the number of random iterations, so,let Iterations be the number of Iterations you will run your program, then Iterations * n^{2}*m^{2} <= 100000000/Total_Tests must be satisfied to avoid TLE . Actually you can try by changing the constant and submitting the solution to get a better bound on number of Iterations.

I would like to thank Ju Ruo , i got this insight after reading his code .

I would invite all the participants of this problem to share their awesome ideas with us :).

### AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution to be uploaded soon.

Tester’s solution