ISSNAKE - Editorial

dfs
easy
editorial
issnake
snackdown
snckpa17

#1

PROBLEM LINK:

Practice
Contest

Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak

DIFFICULTY:

Easy

PREREQUISITES:

Connected components

PROBLEM:

Given a grid with 2 rows and n columns, where each cell is either white or black, find out if all black cells can form a single snake. A snake is a connected component of black cells, which, after distinguishing a head and a tail of the snake, such that we can go from H to T visiting all black cells, and visit each such cell exactly once.

EXPLANATION:

The problem can be divided into two parts:

  1. Finding out if all black cells form a connected component
  2. Finding out if there exist two black cells, H and T, such that we can go from H to T visiting all black cells, and visiting each such cell exactly once.

##Part 1:

This can be solved easily by building a graph G consisting only of black cells and running a DFS over G to find out if all its vertices are in a single component. Two vertices (cells) in G are connected if and only if they share a common side. If all vertices form a single component, then we can proceed to the second part. Otherwise, the answer is clearly negative, because there are at least two black cells, such that one cannot be reached from the other, so if even some black cells can form a snake, there will still exist a black cell which is not a part of the snake.

##Part 2:
Now, we know that all black cells form a connected component i.e. each two cells are reachable from each other in G. The next question is: are there two black cells, H and T, such that we can draw a path from H to T visiting all black cells, and visit each such cell only once.

If we take a closer look at the possible columns of the grid, there are only 4 possibilities:

Type 1:
alt text

Type 2:
alt text

Type 3:
alt text

Type 4:
alt text

and only the first 3 of the above ones are interesting. Now, there are two cases to consider:

Case 1: The number of columns of types 1 or 2 is at most 1
Case 2: There are at least 2 columns of types 1 and 2

Solving Case 1: In the first case, the answer is automatically positive. To illustrate that, let’s consider a few example grids (only the interesting part showing the full connected component of G is shown). Letters H and T corresponds to the first and the last vertices of the path, and the path itself is denoted by a red line:

Example 1: There is no column with one black cell:
alt text

Example 2: There is a single column with a black cell surrounded by columns with two black cells:
alt text

Of course, the situation is similar when the column with a single black cell has this cell in the bottom row.

Example 3: There is a single column with a single black cell and it’s the left-most column with black cells:
alt text

Of course, the situation is similar when the column with a single black is the right-most column with black cells.

There is also a case when there is only a single black cell in the grid, but then solution trivial - we just set H = T.

Solving Case 2: In the second case, let’s consider two columns with single black cells such that all columns between them have two black cells, and let indices of these columns to be i and j, where i < j. For simplicity, let’s assume that cell H is to the left of cell T in the grid. It should be obvious that H should be in a column with index less or equal to i, and T should be in a column with an index greater or equal to j. This is true because each black cell can be visited only once, so if the path crosses column i from the left, it cannot cross it again from the right side.

We can separate two subcases here:

Subcase 1: Columns at indices i and j have their black cells in the same rows
Subcase 2:. Columns at indices i and j have their black cells in different rows

We can claim that in the first subcase, the solution can exist if and only if the number of columns with two black cells between i and j is even.

Moreover, we can argue that in the second subcase, the solution can exist if and only if the number of columns with two black cells between i and j is odd. To see that, let’s take a look at these two cases in the pictures below:

Example of Subcase 1:
alt text

Example of Subcase 2:
alt text

The observations follow from the facts that there are only two rows in the grid, the path goes from column i to column j (because we assumed that H is to the left to T), and so it can never turn from left to right between columns i and j, in other words, it can only go vertically and to the right.

Based on the above observation, the only thing left to do is to consider every pair of columns with a single black cell such that all columns between them have two black cells. In total, there are at most n such columns. For each such pair, based on the type of these two columns and the parity of the number of columns between them, i.e. j-i-1, we can verify if such pair of columns is valid or not. The overall solution exists if and only if all such pairs of columns are valid. You can also notice, that to the left of the left-most columns with a single cell can be columns with two black cells (similarly to the right of the right-most column with a single cell), but this can be handled in the same manner as the case when there is only one column with a single black cell in the grid.

The above solution can be implemented in O(n) time.

AUTHOR’S AND TESTER’S SOLUTIONS:


Setter's solution can be found [here][15]. Tester's solution can be found [here][16]. Editorialist’s solution can be found [here][17].

#2

Solution links are not visible, please fix them.


#3

Check out my solution to the problem with explanation. Quite easy as compared to the editorial.


#4

I made a Finite automaton state table using all the possibilities i.e. type 1,2,3 or 4, then using that state table it is pretty easy to find an answer. here is a link to my accepted solution: https://www.codechef.com/viewsolution/13822064


#5

Can I get the test cases for this problem ? I am not able to identify the wrong turn in my code


#6

solution in python 3.4 ISSNAKE python


#7

Here is my solution in Java. Used DFS to solve the problem:
https://www.codechef.com/viewsolution/13859782


#8

what is wrong in this code https://www.codechef.com/viewsolution/13860319


#9

How to approach the problem Case it has three or more columns with a single black cell. Why didn’t you add editorial for that?


#10

Another thing to observe is that in an array with only two rows, if the snake is at (row, column) then if a path exists and the cell (~row, column) is black then it must pass through it. Also, if there exists a solution, then there always exists a solution in which the next immediate step is (~row, column) which can be easily proved. So, I navigated my snake in such a way that whenever an up or down move was possible, it made that move.

Here, ~ is the binary NOT operator. So, ~0 is 1 and ~1 is 0.

Here, is the link to the solution.


#11

lINK TO SOLUTION

Can you please say at which testcase the program is failing, or why it’s causing a runtime error (NZEC)

I am new here at CodeChef and am completely at a loss, because it’s running all right in m computer and online compilers like ideone but coming up with NZEC when submitted.


#12

I solved this with a different approach. I made an array of size ‘n’.

  • If both the places of string are white ,i put 0 in array.
  • If upper one is black and lower is white ,i put 1 in array.
  • If upper is white and lower is black , i put 2 in the array.
  • If both are black i put 3 in the array

For example :

.##.

.###

My array becomes : 0,3,3,2

Now solving this becomes very simple

  • if 1,2 come together in array , answer is no
  • if there is 1,2, or 3 in both left and right of any 0, answer is no
  • If even 3’s come anywhere check left and right part of 3’s subarray. Both must be either 2 or 1. If not answer is no.
  • If odd 3’s come anywhere check left and right part of 3’s subarray. They can be either 1,2 or 2,1 . If not answer is no

Solution link : https://github.com/mayank2498/Algorithms/blob/master/ISSNAKE.cpp


#13

I know, I wanted to post editorial as soon as I finished writing it. Links will be updated. Meanwhile, you can see my solution here: https://www.codechef.com/viewsolution/13817894


#14

awesome idea


#15

I have a different approach…it gave me a wrong answer but I am unable to figure where I went wrong. Kindly help out.

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


#16

Interesting!


#17

Amazing!!
Can you please elaborate your solution?


#18

Hey if you can explain the state table it would be awesome!


#19

Here is the link of my finite automata as requested by @ash_code and @shivam9753. I tried to be as clear as possible. Automata may look complex but relate with the question you will surely understand it easily.


#20

Awesome ! This made my day. :slight_smile: