I am not able to reduce the time complexity to get a valid answer. at best i have been able to reduce the time complexity from the common O((mn)^2) to O(km*n).
The basic solution would be to check all the smaller squares inside the matrix.
i want to know the fastest way to solve the problem. Best time complexity .
the answer that you shared is of 0.98 sec and the time limit of the question is 1 sec that is it just somehow got saved. People have solved it in much lesser time than that. I am not able to understand how?
http://www.codechef.com/viewsolution/5607150
^that’s my solution
You can certainly do away with the factor k. Think in terms of having extra space to save your computation results for the next step. Also a major hint is the use of a queue.