Author: [Lalit Kundu]
Tester: [Tasnim Imran Sunny]
Editorialist: [Devendra Agarwal]
There is NxN grid, you need to find number of grid positions which follow the following rule. Emanate a light ray from the point (i,j) parallel to grid axis (i.e. one ray visits (i,x) : x >=j , and the other one visits (y,j) : y>=i ) , if both the rays reach the end i.e. (i,n) and (n,j) , then we count (i,j). ‘#’ absorbs any light ray incident to it.
Let’s first come up with a solution and then we will improve it’s complexity.
For every position (i,j) we iterate in X as well as in Y axis from (i,j) and see if it is a valid position, if it is a valid position then we increment our answer.
You will quickly realise that this solution will time out. Reason : It requires time complexity O(T * (n * n) * (n)) = O(T * n3) [At each iteration we do atmost O(n) traversal and we do atmost O(n*n) iterations]. Worst Case for this solution will be all characters with ‘.’ . T is the number of test cases.
Let’s improve our approach a little.
Suppose that grid point (i,j) is a valid point then you will realise that there is no need to check the x-axis ray for (i,j+1) and similarly there is no need to check y-axis ray for (i+1,j). But does that make significant change in our complexity ? The answer to this is No. Reason : Worst case is keep ‘#’ at the boundary. But if (i,j) is not valid , we cannot comment anything on the x-ray for (i,j+1) and similarly the y-ray for (i+1,j).
Note from above that if we separate both directions and then compute , we can save a lot of computations.
So, We make 2 arrays RayX and RayY , RayX*[j] is 1 if a ray from (i,j) parallel to X axis reaches the end otherwise 0. RayY*[j] is 1 if a ray from (i,j) parallel to Y axis reaches the end otherwise 0.
So , we need to find O(N2) entries. Can we compute each entry in O(1) time ?
Yes , we can do so.
If we know the Solution to RayX*[j] , then can we find the solution to RayX*[j-1] ?
Yes , we can do so.
Case 1: If RayX[j] is 0* , then there must be a blockade from (i,j-1) also , thus RayX*[j-1] is 0 in this case.
Case 2: If RayX[j] is 1* , then there is no blocade from (i,j) then we check that if we can send the light ray from (i,j-1) i.e. grid does not have ‘#’ at (i,j-1) then we say RayX*[j-1] is 1 otherwise 0.
In short RayX*[j-1] is RayX*[j] if we can send the ray from (i,j-1).
What is the Base Case ? i.e. What is the answer to RayX*[n] ?
It is 0 or 1 depending on whether grid has ‘.’ or ‘#’ at that position.
Leaving the Y-axis analysis as a simple exercise for the readers.
Finally for checking if a grid point is valid you only need to check if RayX*[j] is 1 and RayY*[j] is 1.
If you are unable to get the idea , have a look at the pseudo code:
for(int j=n;j>=1;j–) //starting from backwards
if( inp*[j] ==’.’) RayX*[j] = (j!=n)?RayX*[j+1]:1
else RayX*[j] = 0 //If you cannot start the ray from here then 0
if ( inp[j]* == ‘.’ ) RayY[j]* = (j!=n)RayY[j+1]:1
else RayY[j] = 0
if ( RayX*[j] == 1 && RayY*[j] == 1) sum++
Alternate Solution :
Go from right to left and keep going until you encounter any #
Similarly go from bottom to up until you encounter any #.
Have a look at the easy pseudo code:
for(int j=0;j< n;j++)
int ok=1 //flag which will be zero once you get an ‘#’ and it will be 1 otherwise
if(inp*[j]==’#’) ok=0 //encountered the first ‘#’ , set the ok variable to false
for(int i = 0;i< n;i++)
for(int i=0;i< n;i++)
for(int j=1;j< n;j++)
if(RayX*[j] && RayY*[j]) ans++;
AUTHOR’S and TESTER’S SOLUTIONS: