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

×

GRID - editorial

PROBLEM LINK:

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

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

This question is marked "community wiki".

asked 22 Sep '14, 00:14

devuy11's gravatar image

4★devuy11 ♦♦
46273842
accept rate: 0%

edited 22 Sep '14, 01:49

admin's gravatar image

0★admin ♦♦
17.4k347486515

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'

 count++;

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

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

answered 22 Sep '14, 00:38

weirdhackerzz's gravatar image

2★weirdhackerzz
3013
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

link

answered 16 Dec '15, 21:38

testerprac's gravatar image

1★testerprac
312
accept rate: 0%

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

link

answered 22 Sep '14, 00:21

naren65's gravatar image

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

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

http://ideone.com/2ezrLv

link

answered 23 Sep '14, 11:05

rach8's gravatar image

2★rach8
13
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');
        }

        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 ?

link

answered 04 Oct '14, 15:20

sdream's gravatar image

2★sdream
-124
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--){
            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;

}

link

answered 02 Mar '15, 16:24

siddharths067's gravatar image

1★siddharths067
7916
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.

link
This answer is marked "community wiki".

answered 22 Jun '15, 00:07

aakashrana1995's gravatar image

5★aakashrana1995
1
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); }

}}

link

answered 16 Dec '15, 20:27

ankesh18's gravatar image

6★ankesh18
62619
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 :- https://www.codechef.com/viewsolution/8970115

link

answered 17 Dec '15, 14:56

ps06756's gravatar image

4★ps06756
1812
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 )

link

answered 26 Jan '16, 13:19

poorcoder's gravatar image

1★poorcoder
1
accept rate: 0%

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

link

answered 07 Jul '16, 18:20

rakshi28's gravatar image

3★rakshi28
1
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. :)

link

answered 01 Jul, 23:06

sharangone's gravatar image

2★sharangone
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×12,235
×1,320
×801
×118

question asked: 22 Sep '14, 00:14

question was seen: 7,061 times

last updated: 01 Jul, 23:06