You are not logged in. Please login at www.codechef.com to post your questions!

×

CLORGIRD - EDITORIAL

2
2

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. :)

This question is marked "community wiki".

asked 26 Oct '18, 13:55

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

edited 27 Oct '18, 22:51

admin's gravatar image

0★admin ♦♦
19.8k350498541

HERE is my solution.. again matches with setter XDDD

(28 Oct '18, 00:13) l_returns5★

plagiarism with all setter's XD

(28 Oct '18, 00:14) l_returns5★

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
link

answered 28 Oct '18, 13:19

umangahuja1's gravatar image

4★umangahuja1
202
accept rate: 0%

edited 28 Oct '18, 13:23

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.

link

answered 27 Oct '18, 22:57

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 27 Oct '18, 22:59

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).

link

answered 27 Oct '18, 23:50

joffan's gravatar image

5★joffan
9488
accept rate: 13%

edited 28 Oct '18, 00:31

1

Oh. It was just a simple implementation.

(27 Oct '18, 23:58) taran_14076★

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★

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

link

answered 28 Oct '18, 00:14

pkdhirasaria's gravatar image

2★pkdhirasaria
1
accept rate: 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

link

answered 28 Oct '18, 00:55

alpha_better's gravatar image

4★alpha_better
31
accept rate: 0%

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

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

link

answered 28 Oct '18, 01:44

sibasish_14's gravatar image

3★sibasish_14
111
accept rate: 0%

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

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

link

answered 28 Oct '18, 13:05

sharacco_123's gravatar image

2★sharacco_123
1
accept rate: 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

link

answered 28 Oct '18, 17:36

sanchit777's gravatar image

3★sanchit777
1
accept rate: 0%

Try corrected test case

$# . .$
$. . #$

(29 Oct '18, 22:42) taran_14076★

it's always good to see @Taranpreet Singh's editorial :)

link

answered 29 Oct '18, 00:14

knakul853's gravatar image

3★knakul853
963
accept rate: 16%

1

Glad you liked :)

(29 Oct '18, 00:56) taran_14076★

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?

link

answered 29 Oct '18, 19:47

white_shadow_'s gravatar image

2★white_shadow_
11
accept rate: 0%

edited 29 Oct '18, 19:54

@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

link

answered 29 Oct '18, 22:44

knakul853's gravatar image

3★knakul853
963
accept rate: 16%

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

link

answered 01 Nov '18, 07:57

gitinit's gravatar image

3★gitinit
1
accept rate: 0%

Have you considered variations on this case:

........
........
...#....
.....#..
....#...
........
........
(02 Nov '18, 05:51) joffan5★

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

link

answered 14 Nov '18, 12:53

jcnitdgp25's gravatar image

1★jcnitdgp25
1
accept rate: 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

link

answered 25 Dec '18, 13:06

sabios's gravatar image

2★sabios
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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