Need help in graph problem - Solved with approach defined - Google Kickstart Round H, Diagonal Puzzle

help
1

This is not necessarily a graph problem, but it can be solved using graphs. I was doing some practice on past google kickstart and found this problem.

Now, in the analysis section of this problem, one of the solutions is creating the graph where each node is a diagonal and each cell represents edge which connects them. I am not able to visualize this analogy and thus can’t able to proceed. It seems to be a really nice trick. Can you help me to understand this solution?
It would be nice if you can mention such problems which can be solved using such analogy.

==============================SOLUTION APPROACH ======================
I have been going over many articles for this problem. There are two approaches that can solve this given problem.

  1. In order to arrive at this, it required huge pattern recognition and mathematics visually intuition. The Solution lies in that fact that “You are guaranteed that it is possible to make all the squares black.”
    It basically meaning, there is a mathematical relationship that exist over diagonals that while flipping never ended up revolving each other. (thus infinite loop if we simply do greedy - like when we got “W” simply rotate one of the diagonal and check for other “W”)
    If we closely work over many examples then we wil find that it (this relationship among diagonals) depends over each other through each grid cell. (of course, one grid cell can be part of two diagonals, ). Example:

    000
    000
    000
    Now, If its “W” that meaning we have to flip one diagonal only (out of the two) to make it black. While, If its “B” already meaning, we wether never flip both diagonal or flip both diagonal(to retain its colour). In order to make number of flips minimum, we have to start from the diagnal which must have the highest impact.
    That will be the middle diagonal and sub middle diagonal. We will then have 4 choices wether we flip one or both or nothing and look for White cells, in both these diagonal. If there is white, then we flip another diagonal which is perpendicular to current (these two longest diagonal). Again, there will be solution exist by doing this because as given in problem, You are guaranteed that it is possible to make all the squares black. In other words, intuitively things will get unfold once, you automate this technique as it will never ended up revolving and its will result in least as we are starting from diagnal which is having the highest impact(meaning containing highest number of grid cells hence the intersection point).
    NOTE: I never think, that I can able to come up with this approach while competing in real time. That’s, why i need to learn this 2nd technique to encounter such type of question in future.

  2. In this, you have to find a pattern. If you closely look at the examples given you will see, (as discussed in 1st approach above ) that for each cell two diagonal will be connected using this cell. And the fate of this cell(Colour of this cell) depends upon the flipping status of these two diagonals.

    So the pattern here is:
    If Current cell is “black”- we either flip both or none
    If Current cell is “white”- we flip one of the two

    Look at this in another way. If Cell is “black”, we want to behave these two diagonals in same way while if cell is “white” we want to behave these two diagonals in different way.
    Any pattern yet?
    Actually this is something similar to what we do in bipartite graphs. In bipartite graph, if current node is coloured lets say, “Colour 1” then all of its neighbour should have to be in different colour. Only the difference here, is that here the diagonal which is acting here as node while these grid cell is acting as edges. If this grid cell is “white” (meaning edge) then it means we want to have two of its endpoing to have different colour while if Cell is “black” (meaning that edge) we wants two endpoint to behave in similar fashion.
    So, We create a graph in which nodes are the diagonals, and edges are the grid cell. A diagonal is connected with others by these cells. So total edges in this graph will be n*n. And we will do dfs staring from any random node(or diagonal). While dfs, we will look at the edge colour. if its “black” then we will colour node (other endpoint in consideration) in same colour, lets say “Colour 1” while if edge or cell is white then we will colour other endpoint diagonal or node with different colour lets say “colour 2”.
    We will also make a count of total number of colour 1 and colour 2 that we did. And which ever is minium we will add that to the result.
    One implementation problem, that I encouter is how to translate this diagonal in node. That can look into the property as below.
    00 01 02
    10 11 12
    20 21 22

    Take above diagonal, some of the indices are always 2. So if its below left to top right diagonal, then its indices sum is equal.
    While,
    00 01 02
    10 11 12
    20 21 22

    While above diagonals, can be distinguies by the difference in the indices, as it will be same.

For Images, and Code.
Credit: KickStart 2019 Round H Problem B - 知乎

1 Like
2

is it necessary to use google-chrome to login into https://codingcompetitions.withgoogle.com/ ? Because i can’t login, and it doesn’t show any kind of error.

3

Not necessary. I’m able to view it with FireFox!

4

Visible without chrome

5

@niks_vat Though I am not sure I think this is it.
Every cell has two diagonals passing through it. So, we can somehow create a graph with diagonals as nodes and connect those nodes with the other diagonal of every cell in that diagonal.
Hope this will be of some help to you :grinning:

6

Thanks @satwik_bhv1. So it seems like we need to look at each cell(now edge) if its color white, meaning one of the diagonal crossing over it needs to be flipped(white->black). But if its colour is black, meaning whether no diagonal crossing over it needs to flip or both needs to be flipped. So now after this, how to proceed?

9

But there are no colored vertices in our graph! We only have white and black edges. And if we arbitrarily choose a white edge to toggle, how do we decide which vertex (diagonal) to flip?

10

I meant cell.

11

Yeah, that’s fine. But how do we choose which diagonal to flip?
Example:
BWB
BBW
BBB

Here choosing if we start out dfs by choosing one vertex, we’ll get count as 4 and for the other vertex it’ll be done with count = 1. I’m not able tackle this issue…

12

we start with a white cell and run two dfs on either diagonal as a starting vertex. minimum of both is the answer.

13

@aneee004 your problem only arises at the starting vertex and after that in the dfs you won’t get that issue because you already chosen a diagonal of that cell if its white no problem if its black call the dfs on other diagonal as a vertex

14

B W B
B B W
B B B

  1. lets say, we chosen, (0,1) W lets, we did dfs on left diagonal. We will get
    B B B
    WBW
    B B B
  1. Now, again lets we choose, (1,0) W, and did dfs on above digonal we will get
    B W B
    B B W
    B B B
    Now, we arrive at same intial configuration, so didn’t we ended up getting in infinite loop. or am I missing something?
15

we will choose the other diagonal. we maintain visited at each cell for both left and right diagonals

16

Ok, so if we encounter any cell which is white in dfs, we need to check whether we already did dfs(visited) on this or not, despite whatever the configration of the matrix currently is?

17

yes

18

i think it’s better not to change the contents of the matrix. because we have the initial colour and number of flips. anyhow it all comes under the implementation part.

19

I am not getting the intuition that, lets we have arrive a vertex(W) (Currently not visited before) and did dfs on it, which will essentially change the configuration of the whole matrix. Now, lets say after doing some more dfs, we arrive at same vertex again(it got White again due to some other flipping of diagonal). But since, current configuration is different, we might get the result by doing just one more flip(as now configuration is changed)

20

That’s right. So we just try both paths and return the minimum?

21

yeah

22

Do you agree that we can flip the colour of a current cell only in two ways either left or right. retain the colour in two ways both or none.