What’s wrong in going with approach with checking where ‘#’ is there and from there just check if all other possible cells i.e. (i+1,j), (i+2,j),(i,j+1),(i,j+2) are possible to fill or not, if it’s possible to fill then there is no problem with this ‘#’ move to next.
Please point out my mistake
The question is easy still ,I am stuck . Can someone please point out what’s wrong with my code ?
link : CodeChef: Practical coding for everyone
Can someone please help me point out where am I wrong?
Could someone point out the flaw here?Worked for 2 out of 3 subtasks.
Want to share some learning after this problem.
Approach :
Brute force approach works well for this problem.
Just check all possible 2 X 2 subarrays and if it is safe ( no #) in them, just fill color ( can be done by taking another array bool coloured[n][m] and mark it true).
Then check if all empty cells of given array (a[i][j] = ‘.’) are coloured or not.
Difference between TLE and AC.
Tried first time using map of pair of i,j to coloured ( map < pair <int,int> , int >) and got TLE (now I think why I took map in first place)
Just switched to an array to store coloured status (bool coloured [n][m]) and got AC.
Learning
Keep it simple (stick to basics: access time of arrays ( O(1) ) is faster than map (logarithmic) )
Here is the code for one test case
Click to view
void solve()
{
int n,m;
cin>>n>>m;
char a[n][m];
bool coloured[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>a[i][j];
coloured[i][j] = false;
}
}
for(int i=0;i<n-1;i++)
{
for(int j=0;j<m-1;j++)
{
if(a[i][j] != '#' && a[i][j+1] != '#' && a[i+1][j] != '#' && a[i+1][j+1] != '#' )
{
coloured[i][j] = true;
coloured[i][j+1] = true;
coloured[i+1][j] = true;
coloured[i+1][j+1] = true;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i][j]=='.' && coloured[i][j]==false)
{
cout<<"NO"<<endl;
return;
}
}
}
cout<<"YES";
cout<<endl; }
Please tell the problem with this code, concept used:- not possible iff there is a single ‘.’ in any row or column(like .# at start, #. at end or #.# in between)
it’s always good to see @Taranpreet Singh’s editorial
i tried checking if i can find a ‘.’ in between 2 ‘#’
for this i just added ‘#’ all around my grid so if anywhere in my initial grid i find ‘#’ i will search if i m having a ‘.’ adjacent to it in all the directions and a ‘#’ at position adjacent to the ‘.’ if i find any such case i will return NO.
and if i dont find any such case its YES.
its almost same as sachit777’s soution which you have replied but i am checking the top and bottom as well and the case which you give him is working with my algo but last case is giving WA while submitting. what could be the issue?
@white_shadow_ i also implemented same logic during contest but got WA on subtask 2 .
i also wonder what could be the the case here is my sol.CodeChef: Practical coding for everyone
I’m checking following conditions:
- Empty cell sandwich-ed between obstacle and boundary of grid
- Empty cell sandwich-ed between two obstacles
I’m getting WA on sub-task 2 (similar to @white_shadow and @knakul853). Can anyone help with the case I’m not considering in my solution? https://www.codechef.com/viewsolution/21353530
Being new to competitive programming my bigggest hint was that bruteforce is acceptable…
i just checked all possible 2x2 grids…instead of using another array for storing result i just replaced every ‘.’ in favourable grid with a ‘1’…then at last again i traversed the full grid to find if i encounter any ‘.’ if i do then “NO” else “YES”…
have a look…its very simple…
=============MY CODE======================
https://www.codechef.com/viewsolution/22081531
Oh. It was just a simple implementation.
Yes - my geometry-analysis evaluation was more complicated, taking a lot of thinking time, and the reason it didn’t work was because I somehow had got the idea that the obstacles were sparse, which of course is not necessarily the case.
plagiarism with all setter’s XD
Glad you liked
Try corrected test case
# . .
. . #
Have you considered variations on this case:
........
........
...#....
.....#..
....#...
........
........
I am getting TLE , but my solution is O(n*m) . Please suggest.
https://www.codechef.com/viewsolution/40482358