PROBLEM LINK:
[Practice][1]
[Contest][2]
Author: [Lalit Kundu][3]
Tester: [Tasnim Imran Sunny][4]
Editorialist: [Devendra Agarwal][5]
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming
PROBLEM:
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.
Solution:
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).
Final Solution:
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:
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:
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:
[Authorβs solution][6]
[Testerβs solution][7]
[1]: GRID Problem - CodeChef
[2]: CodeChef: Practical coding for everyone
[3]: darkshadows | CodeChef User Profile for Lalit Kundu | CodeChef
[4]: rustinpiece | CodeChef User Profile for Tasnim Imran Sunny | CodeChef
[5]: devuy11 | CodeChef User Profile for Devendra Agarwal | CodeChef
[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/GRID.cpp
[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/GRID.cpp