Hello Guys,
I submitted Solution to Devu and Churu problem but it was giving me TLE since i used a normal approach.I want to know How to approach this problem.some people have used Binary search approach like this one http://www.codechef.com/viewsolution/5957224.TIA 
Small hint:
Fix a height, then try for each 1 <= i <= j <= n such that you are currently looking at row = height and columns from i to j(inclusive). Now for this fixed i, j, you can note that if we iterate over k >= height such that we are currently looking at rectangle (height, i) and (k, j). Then in this rectangle, if we increase k, then number of distinct elements also increase. So you can apply two binary searches over k to solve problem for fixed, height, i and j. So overall complexity will be O(n * n * n * n * log n).
Sample Solution
You can check my code which uses exactly same variables here.
More optimization
By using the idea, that k will always increase, you can solve it in O(n^4). You can also use a solution called monotone queue too.
Another solution
It uses trick that K is not that large, K <= 26. So you can use bitmask idea to solve the problem too.
1 Like
I used two pointers, I solved it in O((n^3)*26), if u don’t understand my solution u can think about how to solve that problem for this kind of matrix A(nx1).
1 Like