CLORGIRD - EDITORIAL

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

My Solution

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?

https://www.codechef.com/viewsolution/21234006

Could someone point out the flaw here?Worked for 2 out of 3 subtasks.

CodeChef: Practical coding for everyone

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; }
4 Likes

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)

https://www.codechef.com/viewsolution/21240618

it’s always good to see @Taranpreet Singh’s editorial :slight_smile:

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

Why is this solution giving a TLE ?
https://www.codechef.com/viewsolution/21622000

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.

1 Like

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.

HERE is my solution… again matches with setter XDDD

plagiarism with all setter’s XD

Glad you liked :slight_smile:

1 Like

Try corrected test case

# . .
. . #

Have you considered variations on this case:

........
........
...#....
.....#..
....#...
........
........
2 Likes

I am getting TLE , but my solution is O(n*m) . Please suggest.
https://www.codechef.com/viewsolution/40482358