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[i][j] is 1 if a ray from (i,j) parallel to X axis reaches the end otherwise 0. RayY[i][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[i][j] , then can we find the solution to RayX[i][j-1] ?
Yes , we can do so.
Case 1: If RayX[i][j] is 0 , then there must be a blockade from (i,j-1) also , thus RayX[i][j-1] is 0 in this case.
Case 2: If RayX[i][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[i][j-1] is 1 otherwise 0.
In short RayX[i][j-1] is RayX[i][j] if we can send the ray from (i,j-1).
What is the Base Case ? i.e. What is the answer to RayX[i][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[i][j] is 1 and RayY[i][j] is 1.
If you are unable to get the idea , have a look at the pseudo code:
for(int i=1;i<=n;i++) for(int j=n;j>=1;j--) //starting from backwards //For RayX[i][j] if( inp[i][j] =='.') RayX[i][j] = (j!=n)?RayX[i][j+1]:1 else RayX[i][j] = 0 //If you cannot start the ray from here then 0 //For RayY[i][j] if ( inp[j][i] == '.' ) RayY[j][i] = (j!=n)RayY[j+1][i]:1 else RayY[j][i] = 0 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if ( RayX[i][j] == 1 && RayY[i][j] == 1) sum++ return 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 for(int i=n-1;i>=0;i--) if(inp[i][j]=='#') ok=0 //encountered the first '#' , set the ok variable to false RayY[i][j]=ok for(int i = 0;i< n;i++) int ok=1; for(int j=n-1;j>=0;j--) if(inp[i][j]=='#') ok=0; RayX[i][j]=ok; int ans=0; for(int i=0;i< n;i++) for(int j=1;j< n;j++) if(RayX[i][j] && RayY[i][j]) ans++; return ans
AUTHOR’S and TESTER’S SOLUTIONS: