×

GRID - editorial

Practice
Contest
Author: Lalit Kundu
Tester: Tasnim Imran Sunny
Editorialist: Devendra Agarwal

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:

This question is marked "community wiki".

46273842
accept rate: 0%

19.0k348495531

Really good question. Was so simple but I made it really complex. :(

(22 Sep '14, 00:55)

Is the TL for Python for practice also 8s? I am getting TLE for the 2nd pseudo code mentioned in the editorial.

(22 Sep '14, 01:19)

@nisargshah95: For this problem we tested in python and it was working fine. Though sometimes it happens that things don't work quite well with python. So either please optimize your solution or please try in other language like C++ or Java.

(22 Sep '14, 01:25)

 3 I did something like this.. Let set the visibility of ith row and jth column of grid to true.Now starting from bottom right position, if '.' is present there and its row and column visibility values are true,then increment the count by 1 else if a '#' is present then set the visibility of that row and column to false. pseudocode is : initial visibility of all rows and column is set to true traverse each value if value[i][j] == '.' and row[i] == 'true' and column[j] == 'true'  count++;  if value[i][j] == '#'  set row[i] to 'false' set column[j] to 'false'  answered 22 Sep '14, 00:38 40●1●3 accept rate: 0% exactly same approach :) and the best approach.... even variable names are also same :) :) (22 Sep '14, 01:13) Ya.. DP was not needed... space efficient as well ..:) (23 Sep '14, 15:35) krooonal4★ How about array[1][2] element below ?? For that row[1] = false , col[2]= false but it is valid point.  #.# #.. #..  (25 May '15, 13:43)
 1 Great explanation answered 16 Dec '15, 21:38 31●2 accept rate: 0%
 0 Was the time limit for Ruby increased like Python ? I got TLE using DP approach answered 22 Sep '14, 00:21 2★naren65 1 accept rate: 0% No, it was not increased for Ruby. We did not test it for Ruby. So it was not increased. (22 Sep '14, 00:24) 1 Its a known fact that both Python and Ruby are similar in performance. In fact Ruby is a little slower. I feel the time limit should have been increased for Ruby too. (22 Sep '14, 00:27) naren652★
 0 I am trying the same approach as mentioned in Editorial, why my code is not giving right answer? http://ideone.com/2ezrLv answered 23 Sep '14, 11:05 2★rach8 1●3 accept rate: 0%
 0 My Approach : step 1 -> Read the first row as a string and replace all the occurrences of '#' with '0' in that row. (tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = '1');  For remaining rows : step 2 -> Read the next row and replace all the occurrences of '#' with '0' and for the '.' : Read the number in above cell (that is in the above row and same column) and increase this number by 1 and put the incremented value in the current cell .  (tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = grid[i-1][j] + 1);  Code for reading grid :  cin >> tmp; for(j=0 ; j> tmp; for(j=0 ; j
 0 Can you Find Where am i Going Wrong , I have Used The Same Logic As Editorial Only i Checked From Bottom Left to Up right and Top Left to Bottom Right ....  include include include define l(x) scanf("%lld",&x); typedef long long int ll; using namespace std; int main() { // your code goes here ll t; ios_base::sync_with_stdio(0); l(t); getchar(); while(t--) { ll n; l(n); getchar(); char a[1000][1000]; for(ll i=0;i=0;j--){ if(a[i][j]=='.')hoz++; else break; } for(ll j=n-1;j>=0;j--) for(ll i=n-1;i>=0;i--){ if(a[i][j]=='.')ver++; else break; } printf("%lld\n",min(hoz,ver)); } return 0; }  answered 02 Mar '15, 16:24 79●2●7 accept rate: 4%
 0 The best way to solve this problem without DP is to keep two arrays, namely row[] and col[] which stores the rightmost and the bottom-most encounter of '#'for each row and column respectively for the whole grid. It is obvious that any ray entering from below cannot pass the barrier '#' than the bottom-most encounter for each column. Similarly, a ray cannot pass the '#' barrier if it comes from the left of the rightmost '#' occurrence. Hence, each of the '.' in a column above bottom-most '#'and each of the '.' in a row on left of the rightmost '#' will not be suitable place to keep a mirror. So, a suitable place will be the one where a '.' is below the bottom-most '#' for that column and on right of the righmost '#' for that row. Count all such dots. See my solution here. link This answer is marked "community wiki". answered 22 Jun '15, 00:07 1 accept rate: 0%
 0 why i am getting wrong answer....pls help boolean a[][]=new boolean[n][n]; int count =0; for(i=0;i=0;i--) { for(j=n-1;j>=0;j--) { if(i!=n-1) a[i][j]=(a[i][j] && a[i+1][j]); if(j!=n-1) a[i][j]=(a[i][j] && a[i][j+1]); if(a[i][j]==true) count++; } } ob.println(count); } }} answered 16 Dec '15, 20:27 5★ankesh18 628●1●10 accept rate: 7%
 0 Another approach for the solution, could be using binary search. Store the positions of the rocks ("#") in a vector in a sorted manner and then find if there is a number greater then j in rows[i] and a number greater then i in cols[j], using binary search (when checking if cell (i,j) is possible or not). row[i] is a vector which stores the positions of rocks in ith row in sorted manner and similarly for col[j]. The overall complexity of the solution would be N^2log(N), which is sufficient in this case. Link to the solution :- https://www.codechef.com/viewsolution/8970115 answered 17 Dec '15, 14:56 4★ps06756 18●1●2 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,366
×1,754
×995
×119

question asked: 22 Sep '14, 00:14

question was seen: 7,777 times

last updated: 04 Mar, 23:02