GRID - editorial

editorial
, , ,
1

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]: http://www.codechef.com/problems/GRID
[2]: http://www.codechef.com/COOK50/problems/GRID
[3]: http://www.codechef.com/users/darkshadows
[4]: http://www.codechef.com/users/rustinpiece
[5]: http://www.codechef.com/users/devuy11
[6]: http://www.codechef.com/download/Solutions/COOK50/Setter/GRID.cpp
[7]: http://www.codechef.com/download/Solutions/COOK50/Tester/GRID.cpp

8 Likes
2

Was the time limit for Ruby increased like Python ? I got TLE using DP approach

3

No, it was not increased for Ruby. We did not test it for Ruby. So it was not increased.

4

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.

1 Like
5

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'
3 Likes
6

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

7

exactly same approach :slight_smile: and the best approach…
even variable names are also same :slight_smile: :slight_smile:

8

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

9

@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.

10

I am trying the same approach as mentioned in Editorial, why my code is not giving right answer?

11

Ya… DP was not needed… space efficient as well …:slight_smile:

12

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<n ;j++)
		{
			
			(tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = '1');
		}
		
		grid.push_back(tmp);
		
		for(i=1;i<n;i++)
		{	
			cin >> tmp;
			
			for(j=0 ; j<n ;j++)
			{	
				(tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = grid[i-1][j] + 1);
			}
			
			grid.push_back(tmp);
		}

Now i will start traversing the grid from first row and i will find the last occurence of ‘0’ in that row. Lets suppose that the last occurrence of ‘0’ is ‘index’ . Now i will start from index+1 and check each column upto column <= n .For each column i will calculate :

grid[n-1][j]-grid[i][j] == n-1-i

If it is true then (i,j) is a valid position otherwise it is invalid position .
Here is my code for this :

    for(i=0 ; i<n ; i++)
	{
		index = grid[i].find_last_of('0');

		for(j = index+1 ; j<n ; j++)
		{
			if(n-1-i == grid[n-1][j]-grid[i][j])
			{
				count++;
			}
					
		}
	}

But i am getting wrong answer . If anyone one can find where i am doing wrong then please let me know ?

13

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 <iostream>
#include <cstdio>
#include <algorithm>
#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<n;i++){
	        for(ll j=0;j<n;j++)a[i][j]=getchar_unlocked();
	        getchar_unlocked();
	    }
	    
	    ll hoz=0,ver=0;
	    for(ll i=0;i<n;i++)
	        for(ll j=n-1;j>=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;
}
14

How about array[1][2] element below ?? For that row[1] = false , col[2]= false but it is valid point.

 #.#
 #..  
 #..
15

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.

16

why i am getting wrong answer…pls help

boolean a[][]=new boolean[n][n];
int count =0;
for(i=0;i<n;i++)
{
String b=in.readLine();
for(j=0;j<n;j++)
if(b.charAt(j)==’.’)
a[i][j]=true;
}

for(i=n-1;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);
}

}}

17

Great explanation

1 Like
18

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

19

time complexity:O(n^2)

1.from SOUTH - from every column keep marking dots ‘.’ with a different char until you encounter a hash ‘#’ , if you encounter a hash stop moving in that column and do the same in the remaining columns (starting from south) . this can be done in O(n^2) time .
now ,
2.from EAST- keep on moving in a given row until you encounter a hash ‘#’ , and increment your count whenever you encounter that different char (that you set while moving from south ) . do the same in remaining rows . this will take O(n^2) time

the final count will be your answer … ( my solution ran in 0.41 sec., c++ , using scanf/printf )

20

why it is giving run time error …
https://www.codechef.com/viewsolution/10744547