You are not logged in. Please login at to post your questions!


GRID - editorial


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




Dynamic Programming


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

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 solution
Tester's solution

This question is marked "community wiki".

asked 22 Sep '14, 00:14

devuy11's gravatar image

4★devuy11 ♦♦
accept rate: 0%

edited 22 Sep '14, 01:49

admin's gravatar image

0★admin ♦♦

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

(22 Sep '14, 00:55) nisargshah953★

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) nisargshah953★

@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) dpraveen ♦♦4★

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'


if value[i][j] == '#'

 set row[i] to 'false'
 set column[j] to 'false'

answered 22 Sep '14, 00:38

weirdhackerzz's gravatar image

accept rate: 0%

exactly same approach :) and the best approach.... even variable names are also same :) :)

(22 Sep '14, 01:13) rudra_sarraf3★

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) empty_life2★

Great explanation


answered 16 Dec '15, 21:38

testerprac's gravatar image

accept rate: 0%

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


answered 22 Sep '14, 00:21

naren65's gravatar image

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) dpraveen ♦♦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.

(22 Sep '14, 00:27) naren652★

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


answered 23 Sep '14, 11:05

rach8's gravatar image

accept rate: 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<n ;j++)

            (tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = '1');


            cin >> tmp;

            for(j=0 ; j<n ;j++)
                (tmp[j] == '#') ? (tmp[j] = '0') : (tmp[j] = grid[i-1][j] + 1);


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])


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


answered 04 Oct '14, 15:20

sdream's gravatar image

accept rate: 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 <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--){
            else break;
            for(ll j=n-1;j>=0;j--)
                for(ll i=n-1;i>=0;i--){
                    else break;



return 0;



answered 02 Mar '15, 16:24

siddharths067's gravatar image

accept rate: 4%

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.

This answer is marked "community wiki".

answered 22 Jun '15, 00:07

aakashrana1995's gravatar image

accept rate: 0%

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); }



answered 16 Dec '15, 20:27

ankesh18's gravatar image

accept rate: 7%

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 :-


answered 17 Dec '15, 14:56

ps06756's gravatar image

accept rate: 9%

edited 17 Dec '15, 14:57

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 )


answered 26 Jan '16, 13:19

poorcoder's gravatar image

accept rate: 0%

why it is giving run time error ..


answered 07 Jul '16, 18:20

rakshi28's gravatar image

accept rate: 0%

No need for dynamic programming in this question. Just throw light from east and then from south. Indexes which recieved light from both east and south will have count 2. Rest will have count 0(initial) or 1(just from 1 side). Blocks are numbered 99.

While throwing light if you occur a 99/block stop the light else continue in that row or column.

At end count all blocks with count==2 and that is the answer. :)


answered 01 Jul '17, 23:06

sharangone's gravatar image

accept rate: 0%

here is my solution for the above problem in cpp


answered 04 Mar, 23:02

anjn98's gravatar image

accept rate: 0%

My approach was:

  1. Make two NxN arrays
    1. Vertical array (to trace visibility from east)
    2. Horizontal array (to trace visibility from south)
  2. iterate each row from right to left in horizontal array. Mark items which are not visible.
  3. iterate each row from bottom to top in horizontal array and element is called v[i][j]. If v[i][j]=='.' and h[i][j]=='.' then Its a match :)
Example: Same example which is given in figure of problem description

Step 1: Horizontal array initially be like

Vertical array initially be like

Step 2: Horizontal array be like ###..
As I cannot see beyond a stone from east

Vertical array be like

Step 3: Horizontal array be like

Vertical array be like
As I cannot see beyond a stone from south

Step 4: Answer will be the count of points which are common in both as '.' Hence answer is 2

My JAVA solution is can be found HERE


answered 05 Jul, 00:39

sgrpwr's gravatar image

accept rate: 0%

edited 05 Jul, 00:48

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 22 Sep '14, 00:14

question was seen: 8,159 times

last updated: 05 Jul, 00:48