CLORGIRD - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Basic Implementation.

PROBLEM:

Given a N*M grid containing some obstacles represented by ‘#’ and remaining empty cells represented by ‘.’, Determine if it is possible to color only the empty cells if we can color a 2*2 sub-rectangle in one move if it doesn’t contain any obstacles. Note that we don’t need to count the number of moves, just tell whether it is possible to color or not.

SUPER QUICK EXPLANATION

  • Just find all the positions where we can make a move, and store the result of moves in another array.
  • If there’s an empty cell in the grid, which cannot be colored by any operation, It is impossible to color that cell, hence the answer is impossible.

EXPLANATION

Let’s define a position (i,j) valid, if all four positions (i,j),(i,j+1),(i+1,j) and (i+1,j+1) are empty positions, because we can apply the move here without coloring any obstacles.

First of all, we find all the valid positions in the grid and store the result of applying move at that position.

For this purpose, we can make an auxiliary grid, where we mark the positions which can be colored using operations at any valid position.

Now, We know where the moves can be applied, so make another grid, and find out the final grid after applying all operations.

Now, If all the empty cells from given grid are marked colored, then it is possible to color all empty cells without coloring any obstacles, so print Yes. Otherwise, print No.

Related Problems

There are a lot of problems which involve grids which occurred recently, like AVGMAT, GRIDGM

Also, Prefix/Suffix sums combined with grid or even 3-dimensional arrays form interesting problems, and thus, are a nice topic for practice.

Another Interesting grid problem involves dynamic-programming on grids depending upon some conditions, which you may find here.

Time Complexity

Time complexity is O(N*M) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

2 Likes
2

Another very similar problem- https://codeforces.com/problemset/problem/1059/B :slight_smile:

The basic way to solve is same- for all possible cells, what cells you can visit without visiting any unwanted cell and in the end verify that all required cells are visited at least once.

1 Like
3

I was annoyed with myself for trying to do evaluation of different geometry of obstacles (which failed) instead of just colouring the grid, which works fine (but which I implemented just too late, having started late on the contest).

4

Oh. It was just a simple implementation.

1 Like
5

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.

6

HERE is my solution… again matches with setter XDDD

7

plagiarism with all setter’s XD

8

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

9

The question is easy still ,I am stuck . Can someone please point out what’s wrong with my code ?
link : https://www.codechef.com/viewsolution/21248302

10

Can someone please help me point out where am I wrong?

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

11

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

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

12

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; }
2 Likes
13

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

14

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

15

Glad you liked :slight_smile:

1 Like
16

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?

17

Try corrected test case

# . .
. . #

18

@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.https://www.codechef.com/viewsolution/21245085

19

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

20

Have you considered variations on this case:

........
........
...#....
.....#..
....#...
........
........