×

# CLORGIRD - EDITORIAL

Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

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:

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

This question is marked "community wiki".

3.9k2895
accept rate: 22%

19.8k350498541

HERE is my solution.. again matches with setter XDDD

(28 Oct '18, 00:13)

plagiarism with all setter's XD

(28 Oct '18, 00:14)

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

View Content

202
accept rate: 0%

 1 Another very similar problem- https://codeforces.com/problemset/problem/1059/B :) 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. answered 27 Oct '18, 22:57 15.4k●1●20●66 accept rate: 18%
 0 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). answered 27 Oct '18, 23:50 5★joffan 948●8 accept rate: 13% 1 Oh. It was just a simple implementation. (27 Oct '18, 23:58) 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. (28 Oct '18, 00:10) joffan5★
 0 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 answered 28 Oct '18, 00:14 1 accept rate: 0%
 0 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 answered 28 Oct '18, 00:55 3●1 accept rate: 0%
 0 Could someone point out the flaw here?Worked for 2 out of 3 subtasks. https://www.codechef.com/viewsolution/21245677 answered 28 Oct '18, 13:05 1 accept rate: 0%
 0 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 answered 28 Oct '18, 17:36 1 accept rate: 0% Try corrected test case $# . .$ $. . #$ (29 Oct '18, 22:42)
 0 it's always good to see @Taranpreet Singh's editorial :) answered 29 Oct '18, 00:14 96●3 accept rate: 16% 1 Glad you liked :) (29 Oct '18, 00:56)
 0 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? answered 29 Oct '18, 19:47 1●1 accept rate: 0%
 0 @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 answered 29 Oct '18, 22:44 96●3 accept rate: 16%
 0 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 answered 01 Nov '18, 07:57 3★gitinit 1 accept rate: 0% Have you considered variations on this case: ........ ........ ...#.... .....#.. ....#... ........ ........  (02 Nov '18, 05:51) joffan5★
 0 Why is this solution giving a TLE ? https://www.codechef.com/viewsolution/21622000 answered 14 Nov '18, 12:53 1 accept rate: 0%
 0 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 answered 25 Dec '18, 13:06 2★sabios 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,173
×832
×649
×71
×40
×8

question asked: 26 Oct '18, 13:55

question was seen: 2,032 times

last updated: 25 Dec '18, 13:06