Rectangular queries logic unveiled

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.

8 Likes

You are going well…but remember one thing answer all the questions from yourself…don’t copy or cheat

Nice to see that you were able to get the logic…Now you can further optimize it by doing the same precomputation for columns…and when the #rows<#columns you use the row precomputation… else you use the column precomputation…

2 Likes

yes sure :slight_smile:

I could not solve the problem ! But I wonder that how most of the people solve the question using the same approach as mentioned above ! that is, taking a 3D array !!!

@kaustavary17: its becoz the range of the elements was 1<=A(i,j)<=10, most of them precomputed values for 1 to 10 and obtained answers by the solution by adding only rows between 1 to 10.

for initializing first element of each row you start from i=1…you
have started from i=0…pleased modify it… nice editorial …:slight_smile:

done :slight_smile: thanks for pointing that out :slight_smile:

what is the order of your solution? is it O(Q*N) for Q queries ?