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

×

ADAMTR - Editorial

1
2

PROBLEM LINK:

Div1
Div2
Practice

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

DIFFICULTY:

Easy-Medium

PRE-REQUISITES:

2-Sat, DFS, Graph Coloring

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

asked 20 Jan, 01:39

vijju123's gravatar image

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

edited 21 Jan, 01:15

admin's gravatar image

0★admin ♦♦
19.8k350498541

(26 Jan, 00:29) taran_14076★

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

link

answered 21 Jan, 02:10

rajput1999's gravatar image

5★rajput1999
3716
accept rate: 0%

1

not only this guy many of the top scorers used same O(n^3) solution

(21 Jan, 02:15) rajput19995★

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) gjaiswal1084★

exactly its unfair

link

answered 21 Jan, 16:51

himalaya7's gravatar image

5★himalaya7
304
accept rate: 9%

Is anyone able to see the setter's solution? I am getting a different login screen arter clicking on it.

link

answered 21 Jan, 02:18

who_jeetu's gravatar image

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

link

answered 21 Jan, 05:18

juckter's gravatar image

3★juckter
2
accept rate: 0%

it's answer is no right?

(21 Jan, 16:29) eobardthawne3★

can anybody explain how o(n^3) how it works

link

answered 21 Jan, 09:28

karun369's gravatar image

2★karun369
11
accept rate: 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.

link

answered 21 Jan, 14:30

rp789's gravatar image

5★rp789
22
accept rate: 0%

Can someone tell me what is wrong with my code https://www.codechef.com/viewsolution/22567749

link

answered 21 Jan, 16:30

eobardthawne's gravatar image

3★eobardthawne
664
accept rate: 0%

Can someone tell me what is wrong with my code https://www.codechef.com/viewsolution/22567749

link

answered 21 Jan, 16:30

eobardthawne's gravatar image

3★eobardthawne
664
accept rate: 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.

link

answered 21 Jan, 16:44

amitgomi's gravatar image

5★amitgomi
0
accept rate: 0%

how 10^8 is an acceptable solution please explain @gjaiswal108?

link

answered 21 Jan, 21:57

srish_123's gravatar image

1★srish_123
1
accept rate: 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."

link

answered 22 Jan, 16:00

chirag11032000's gravatar image

4★chirag11032000
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) vijju123 ♦♦5★

Got it. Thanks :)

(22 Jan, 23:28) chirag110320004★
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:

×733
×194
×25

question asked: 20 Jan, 01:39

question was seen: 3,643 times

last updated: 26 Jan, 00:29