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 .
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 :
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;
}
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.
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.
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 )
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.
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.
@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.
