FEB16 Long : SEATL

long-contest

#1

Complexity : O(Number of Distinct elements in matrix * N)

Concepts : Maps , sets .

While a lot of people might have used O(NM*(N+M)) approach and recieved TLE even for subtask 1.
The number of test cases are not specified for each subtask.

Now instead of generating the count matrix , that is the maximum count of each element in that row+coloumn,
we would rather do it number by number.Its given that the numbers are between 1 to 10^6 or we can say the maximum number of distinct elements in the matrix can be atmost N*M ,

We will have map data structure to store the coordinates of each element in the matrix.
And from this we can find the length of the largest cross,and then print maximum length of cross of all elements.

Here is my working code in python : Solution