I am a newbie on codechef and this problem(http://www.codechef.com/problems/RECTQUER)from Dec Challenge 2013 consumed my 4 days(solved it yesterday).So i thought it was worth to unveil the logic of this problem.
Aim: To find number of distinct elements in a submatrix.
Input:Enter the n and the order of the square matrix will be n*n.
Enter n*n matrix.
Enter number of queries.(q)
Enter query in the form (x1 y1 x2 y2).x1 y1 denotes the x1 row and y1 column of the
upper left corner of the submatrix. x2 y2 denotes the x2 row and y2 column of the
lower right corner of the submatrix.
The rows are indexed from top to bottom that is top row has index 1, and columns are indexed from left to right that is left column has index 1.
The nos in the matrix can take values form 1-10.
Worth noting is max value of n can be 300.
Brute force approach:
You can traverse all the numbers in the query.You can keep an array(count[10]).Initialize each element in count as 0.For each number visited you can update respective location for that number in count.
So after all numbers included in the query have been traversed the count[] has the number of occurences of each number.Now just traverse the count[] and where occurence is not 0 just increment dist_val and after the count[] has been traversed you will get the number of distinct elements in dist_val.
But it is worth noting that this approach gives an TLE(time limit exceeded error)
Required approach:I would like to explain this with an example.
3
1 2 3
3 2 1
5 6 3
1
1 2 3 3
o/p=4
Declare an 3-D array(a[301][301][10]) for storing the matrix and cumulative frequency of each number in a particular row.
Initialise the first element of each row as 0000000000.This can be done using
for(i=1;i<=n;i++)
for(k=0;k<10;k++)
a[i][0][k]=0;
Now consider this code fragment:
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&no);
for(k=0;k<10;k++)
a[i][j][k]=a[i][j-1][k];
a[i][j][--no]++;
}
if you trace it for the above example you will get
1st 2d array 2nd 2d array 3rd 2d array
0000000000 0000000000 0000000000
1000000000 0010000000 0000100000
1100000000 0110000000 0000110000
1110000000 1110000000 0010110000
Now while you were inputting the numbers you computed this.Our query for the above example is
1 2 3 3
x1 y1 x2 y2
for the 1st 2d array.(get elements in the first row of the queried submatrix)
1110000000 - 1000000000 = 0110000000
a[0][y2][0 to 9] - a[0][y1-1][0 to 9]
we just got what are the elements in the first row of the queried submatrix .The elements are 2 and 3.
for the 2nd 2d array.
1110000000 - 0010000000 = 1100000000
a[1][y2][0 to 9] - a[1][y1-1][0 to 9]
we just got what are the elements in the second row of the queried submatrix.The elements are 1 and 2.
for the 3rd 2d array.
0010110000 - 0000100000 = 0010010000
a[2][y2][0 to 9] - a[2][y1-1][0 to 9]
we just got what are the elements in the 3rd row of the queried submatrix.The elements are 3 and 6.
So you can run a loop just to iterate the rows and check for the occurrences of each number by subtracting cumulative frequencies(arr[i][y2][k]-arr[i][y1-1][k]).
So for each row in the query you get what are elements present in that row by the above formula.
this can be done using the below code fragment
Initialize count[0 to 9] to 0.
for(i=x1;i<=x2;i++) //for each row of query
{
for(k=0;k<10;k++)
{
val=a[i][y2][k]-a[i][y1-1][k]; //check what nos occur
if(val)
count[k]=1;
}
}
count[] will record the distinct elements that occur in the queried submatrix.
Now just traverse the count[] and where occurence is not 0 just increment dist_val and after the count[] has been traversed you will get the number of distinct elements in dist_val.
So instead of traversing each and every element in the queried submatrix you just traversed rows in the queried submatrix and you got number of distinct elements in that submatrix.
My vote of thanks to @atulsehgal and others whose solutions and comments helped to unveil the logic of this problem and march a step further.
