×

Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey

Easy-Medium

PROBLEM:

Given $2$ matrices $A$ and $B$. In an operation, you can swap a row $i$ with column $i$. Tell if its possible to change matrix $A$ to matrix $B$.

QUICK-EXPLANATION:

Key to AC- See that swapping both row $i$ and row $j$ lead to same effect, i.e. element at $A_{i,j}$ remains at its position. Hence, we can make a logical expression, one for each row (whether to swap it or not) and solve it with $2-sat$.

OR

Key to AC- Identify it as a graph coloring problem with edges telling if nodes have to be of same color or not.

An element $A_{i,j}$ is swapped only if one of row $i$ OR row $j$. Swapping both of them leads $A_{i,j}$ to remain at its place. Hence, construct a graph with nodes from $1$ to $N$. Add an edge from every row $i$ to every other row $j$ with label telling if their color must be same (both swapped or both not swapped) or different (only one of them swapped). Now do $DFS$ on this graph to see if it can be colored under such constraints. Answer does not exist if coloring is impossible.

EXPLANATION:

We will be primarily discussing tester's graph coloring solution. Dont worry $2-SAT$ lovers, I am very sure that @alei will discuss his $2-Sat$ here (/* end of shameless advertisement of setter's blog*/).

We will first see that how the graph is formed, and then how to color it.

1. How to form the graph-

With regards to swapping row $i$ and row $j$, we have a total of $4$ choices -

• Swap neither $i$ nor $j$ - No change to $A_{i,j}$ and $A_{j,i}$.
• Swap row $j$ with column $j$ - $A_{i,j} \implies A_{j,i}$, i.e. both get swapped.
• Swap row $i$ with column $i$ - $A_{i,j} \implies A_{j,i}$, i.e. both get swapped.
• Swap BOTH row $i$ and $j$ - No change to $A_{i,j}$ and $A_{j,i}$.

Now, for every element of $A$ do the following-

• If its not possible to make $A_{i,j}$ and $A_{j,i}$ same as corresponding elements in $B$ by given operations, print No
• If $A_{i,j}==B_{i,j}$ and $A_{j,i}==B_{j,i}$, add an edge between Node $i$ and Node $j$ signifying that color of these $2$ nodes should be same.
• If $A_{i,j} \neq B_{i,j}$ and $A_{j,i} \neq B_{j,i}$, we need exactly one swap. Add an edge from Node $i$ to Node $j$ signifying that these nodes must be of different color.

However, there is one case we failed to capture in above. If $A_{i,j}==A_{j,i}==B_{i,j}==B_{j,i}$ then this means we don't care if they are of same or different color. For such cases, we don't put any edge as edges are put to constraint the color of node. If there is no constraint, we do not add the edges.

A brief code to do this is below, in case you need help in implementation-

View Content

2. How to Color the Graph-

Its nothing but simple DFS for all the connected components in our graph (recall that we are not adding edges in some cases - the graph can be disconnected!!).

One of the ways to do it is, start DFS from any node of the connected component. Assign it some color, say $1$. If we travel an edge, flip color to $0$ OR keep it $1$ depending on what type of edge it is. If at any point of time, we arrive at an already colored node, and the color we need to assign to it is different from its current color, the answer would be $NO$.

An implementation of the DFS function is given below if anyone needs help-

View Content

SOLUTION

Setter - Using $2-SAT$

View Content

Tester - Using Graph Coloring.

View Content

$Time$ $Complexity=O(N^2)$
$Space$ $Complexity=O(N^2)$

CHEF VIJJU'S CORNER :D

1. Setter's Notes-

View Content

2. Tester's Notes-

View Content

3. You are given a general graph of $N$ nodes and $M$ edges. Can you give an algorithm to tell how many colors the graph needs to be colored - such that no $2$ adjacent nodes are of same color? What info do you need? (HINT: Degree of nodes...)

4. Given a tree of $N$ nodes, where $N \leq 10^{18}$, how many colors are needed for coloring it if adjacent nodes cannot have same color? How many colors does a $N*M$ bipartite graph needs? Can we draw some interesting observation from it?

Ans-

View Content

4. Related Problems-

This question is marked "community wiki".

15.5k12066
accept rate: 18%

19.8k350498541

(26 Jan, 00:29)

 1 some guys got an AC in O(n^3) link to the solution : - link to O(n^3) solution I don't think codechef should make these type of questions especially in cookoff I m deeply demotivated after seeing his solution because I thought of the same solution at first glance but left it because it was O(n^3) and plz can anyone tell me how O(n^3) is working answered 21 Jan, 02:10 371●6 accept rate: 0% 1 not only this guy many of the top scorers used same O(n^3) solution (21 Jan, 02:15) It is given that the sum of N^2 over all test cases does not exceed 310^6. while 1<=T<=10^5. So may be problem setter has used small value of N like N=10,T=10^5. Then N^3=10^3. It means NT=(10^3)(10^5)=10^8, which can pass the time limit. We can say that weak test cases are used, that's why O(N3) solution passed:) (21 Jan, 03:22)
 1 exactly its unfair answered 21 Jan, 16:51 30●4 accept rate: 9%
 0 Is anyone able to see the setter's solution? I am getting a different login screen arter clicking on it. answered 21 Jan, 02:18 1 accept rate: 0%
 0 This test case 1 4 1 3 11 7 3 9 12 16 2 12 2 9 3 14 9 2 1 3 2 7 3 9 12 14 11 12 2 9 3 16 9 2 Breaks 13 out of the 18 AC submissions in Division 2 answered 21 Jan, 05:18 3★juckter 2 accept rate: 0% it's answer is no right? (21 Jan, 16:29)
 0 can anybody explain how o(n^3) how it works answered 21 Jan, 09:28 2★karun369 1●1 accept rate: 0%
 0 I didn't get AC for this problem. My approach was somewhat similar to the one using graph, but I was using disjoint set. If A(i,j)==B(i,j) and A(j,i)==B(j,i), then I put i and j in same set. Later I checked once again for the condition (If A(i,j)≠B(i,j) and A(j,i)≠B(j,i) and A(i,j)==B(j,i) and A(j,i)==B(i,j)), i and j should not be in same set. If this condition is contradicted then answer would be No otherwise answer would be Yes. Can someone tell me if there is any flaw in my logic? Here is the link to my solution. answered 21 Jan, 14:30 5★rp789 2●2 accept rate: 0%
 0 Can someone tell me what is wrong with my code https://www.codechef.com/viewsolution/22567749 answered 21 Jan, 16:30 66●4 accept rate: 0%
 0 Can someone tell me what is wrong with my code https://www.codechef.com/viewsolution/22567749 answered 21 Jan, 16:30 66●4 accept rate: 0%
 0 Either You should have added strong testcases. OR You should have provided feature of hacking as provided in contests on codeforces. Because many solutions which are not correct got accepted. It is unfair. answered 21 Jan, 16:44 5★amitgomi 0 accept rate: 0%
 0 how 10^8 is an acceptable solution please explain @gjaiswal108? answered 21 Jan, 21:57 1 accept rate: 0%
 0 I am not getting this part of editorial. Can someone please explain it? "However, there is one case we failed to capture in above. If A[i][j] == A[j][i] == B[j][i] == B[i][j] then this means we don't care if they are of same or different color. For such cases, we don't put any edge as edges are put to constraint the color of node. If there is no constraint, we do not add the edges." answered 22 Jan, 16:00 0 accept rate: 0% This part says that this condition satisfies criteria for both, adding edges for "Nodes have same color" "Nodes have different color". One of this would contradict obviously - but honestly there is no "constraint" for this case - its just that node can be of any color. Since addition of edges mean "The nodes must be of same color/different color depending on type of edge", we dont add edge between i and j in this case. Refer to tester's solution for more info :) (22 Jan, 16:38) Got it. Thanks :) (22 Jan, 23:28)
 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:

×734
×195
×26