PROBLEM LINK:Author: Gerald Agapov 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 Case 2 : A more generic case with any N,M and K. 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 submatrices. If we get close to K , we accept those changes otherwise we reject it. 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 :) . AUTHOR'S and TESTER'S SOLUTIONS:Author's solution to be uploaded soon.
This question is marked "community wiki".
asked 14 Jul '14, 15:01

Here is my editorial for that problem with a lot of details, it gave me 19th place overall: answered 18 Jul '14, 03:14

Sir what would be the best way to find the number of sub matrices? I used PnC, but things get complicated as the types of letters increase. answered 14 Jul '14, 22:03
1
What's PnC?
(14 Jul '14, 22:25)
(14 Jul '14, 23:43)
I have no idea at all how finding the number of distinct submatrices could ever involve permutations. I just tried hashing all submatrices (there are just O(N^2M^2) of them) and storing their hashes in an STL set<>.
(14 Jul '14, 23:48)
size of submatrix vary from [1..n]x[1..m] makes the number of submatrices n^2.m^2!!
(15 Jul '14, 17:57)
@xellos0 I used hashing too. I just used unordered_set instead.
(18 Jul '14, 03:50)

The author's solution is not uploaded even now (after 3 years)! answered 07 Jul, 07:38
