HPIRATES - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Constructive Algorithms and Observations.

PROBLEM:

Consider a grid of dimension R*C having either 0 or 1 at each position. We define associated graph as the graph formed by compressing all positions having same values which are adjacent to each other in all 8 directions, into 1 node, and connecting it to other nodes having the different value, which are adjacent to the current node in all eight directions.

Now, we are given a graph, and we have to find a grid whose associated graph will be isomorphic to the given graph. In case no such grid exists, print -1.

Two graphs are Isomorphic if one can be graph means a graph same in structure, and we can obtain the same graph just by renumbering the vertices of one graph.

SUPER QUICK EXPLANATION

  • A valid grid exist if any only if the given graph is a tree.
  • For any tree, We can make a grid of the following type.

For a graph with N = 3 and edges 1-2 and 1-3, one possible answer is

00000
01010

EXPLANATION

Impossible condition

First of all, try to make a grid for which the associated Graph is cyclic. You will notice, that due to all 8 directions being considered adjacent, we cannot make the graph cyclic.

Consider the following grid.

01
10

Had the adjacent sides being considered, this would have resulted in a cyclic graph, but, since we have all 8 sides adjacent, both zeroes will be connected as well as both ones will be connected, resulting in a graph with two vertices connected with each other.

Also, the graph will be connected, as for any position, if the adjacent position has the same value, it will be merged, otherwise they will be connected by an edge, resulting in a connected graph. Also, the edges will be undirected.

A connected acyclic undirected graph is also called Tree. :slight_smile:

Hence, if the input graph is not a tree, we can immediately report the answer as impossible.

Construction

Now, Let’s move toward construction of the grid for a given tree.

Since multiple solutions exist, being a constructive problem, I’ll be sharing the intended construction. Other constructions may exist, and please share, if you used any other construction. :slight_smile:

Let’s define the construction respectively. Each node is assigned the bit which is the parity of its depth in the tree. I’ll explain the reason at the end.

Suppose, for every node, we define a valid grid for the subtree rooted at that node.

For a node u, each of its children has grid g1, g2, g3 … gk where node u has k children.

It is guaranteed, that parity of d[u] is always opposite to parity of any of its children. Hence, assume bit assigned to the current node is 0.

Make a row of a bit of current node, and in next row, make the graph as

0 g1 0 g2 0 g3 0 … gk 0

Like,

“current bit, grid for first child, current bit, the grid for second child, current bit, grid for third child followed by current bit.” and so on.

That is, the First row is fully filled with the bit assigned to the current node and in the second row, Surround each grid associated with each child by current bit in the second row.

For example, consider tree with N = 3 with edges 1-2 and 1-3. Following grid is generated by this construction.

0 0 0 0 0
0 1 0 1 0

Consider another tree with N = 3 with edges 1-2 and 2-3. Following the grid is generated.

0 0 0 0 0
0 1 1 1 0
0 1 0 1 0

See, we can always make the grid in a similar fashion.

The reason of assigning d[u]%2 as the bit to the current node is that each pair of connected vertices should have opposite bit at their corresponding positions in grid, which implies, no two adjacent nodes in tree can have same bit and depth of each pair of adjacent node differ in parity.

Number of cells in this grid

We can see, that we add a row for each depth level. Turns out this is the maximum number of rows needed by this method. The number of rows generated in the grid is actually the max depth of any node in the tree.

About Number of columns, we can see, that Number of columns will always be 2*N+1. The proof is left as an exercise.

So, in the worst case with a linear chain given, we will have N*(2*N+1) which is 20100 in the worst case for N = 100, far below 10^5.

Time Complexity

Time complexity is O(N^2) per test case, O(N) for DFS, but O(depth*N) time for construction.

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:

1 Like
2

Could you give a proof of the first observation (the graph can’t contain any cycles)?

1 Like
3

Can someone share their method of construction of the binary matrix? I think there must have been a way other than the one based on parity as explained in the editorial. This method seems a little hard to come up with.

4

For building the matrix, you can imagine it like a rectangle candy covered by chocolate with some different flavours inside it. See this link: https://goo.gl/u6FdWj
A chocolate bar with 0s and 1s inside.

For example, if you are in the root and you have 3 other vertexes connected to it, it will be like a chocolate with three parts of 1 covered by 0, like this:

000
010
000

So, all of them together:

0000000
0101010
0000000

Remember that each vertex can have more vertexes connected to it (with more 0s and 1s inside), like this:

00000
01110
01010
01110
00000

So you should do this recursively. First try to find the size of the matrix by counting how much space you need to construct like this.
Then just go “painting” the matrix.

1 Like
5

Ignore parity. We know, if a node is assigned 0, all nodes adjacent to it has to be assigned 1, then all nodes adjacent to these nodes have to be assigned 0 again. You may assign node values beforehand and proceed the same way.

The thing about parity is, that it is making our work easier because it is automatically assigning values. Your choice to assign them in the way you like.

6

Because of 8-sided connectivity.

7

the editorial is so well written!!!

thank you for such a wonderful editorial taran_1407 :))

however, i am new to coding and cannot understand it. can you please recommend me any problem to solve previously attempt this? thank you!