PROBLEM LINK:Practice 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. Final Solution:
Note from above that if we separate both directions and then compute , we can save a lot of computations. Alternate Solution :Go from right to left and keep going until you encounter any # AUTHOR'S and TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 Sep '14, 00:14

I am trying the same approach as mentioned in Editorial, why my code is not giving right answer? answered 23 Sep '14, 11:05

My Approach :
For remaining rows :
Code for reading grid :
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 :
If it is true then (i,j) is a valid position otherwise it is invalid position . Here is my code for this :
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

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 ....
answered 02 Mar '15, 16:24

The best way to solve this problem without DP is to keep two arrays, namely row[] and col[] which stores the rightmost and the bottommost 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 bottommost 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 bottommost '#'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 bottommost '#' 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

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=n1;i>=0;i) { for(j=n1;j>=0;j) { if(i!=n1) a[i][j]=(a[i][j] && a[i+1][j]); if(j!=n1) 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

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

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 , the final count will be your answer .. ( my solution ran in 0.41 sec., c++ , using scanf/printf ) answered 26 Jan '16, 13:19

why it is giving run time error .. https://www.codechef.com/viewsolution/10744547 answered 07 Jul '16, 18:20

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, 23:06

Really good question. Was so simple but I made it really complex. :(
Is the TL for Python for practice also 8s? I am getting TLE for the 2nd pseudo code mentioned in the editorial.
@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.