ADAMTR - Editorial

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-

Click to view
for(int i=0;i< N;i++){
		for(int j=0;j< N;j++){
			if(x[i][j]==x[j][i] and y[i][j]==y[j][i] and x[i][j]==y[i][j])continue;//Dont add ege
			if(x[i][j]==y[i][j] and x[j][i]==y[j][i]){adj[i].pb({j,1});adj[j].pb({i,1});continue;}//Same color
			if(x[j][i]==y[i][j] and x[i][j]==y[j][i]){adj[i].pb({j,-1});adj[j].pb({i,-1});continue;}//Different color
			cout<<"No";//If this falls in none of 3 cases above, then answer is not possible.
			
		}
	}

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-

Click to view
void dfs(int u,int col){//Col=Color to assign to node u.
	if(vis){//If already colored
		if(vis!=col)good=0;
		return;
	}
	vis=col;
	for(auto i:adj){
		dfs(i.F,col*i.S);//Tester used edge weights as 1 and -1. -1 for flipping and +1 for keeping it same.
	}
}

SOLUTION

Setter - Using 2-SAT

Click to view
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
//2-sat from tourist, all rights reserved :) https://www.codechef.com/viewsolution/18335332
template <typename T>
class graph {
  public:
    struct edge {
      int from;
      int to;
      T cost;
    };
 
    vector<edge> edges;
    vector< vector<int> > g;
    int n;
 
    function<bool(int)> ignore;
 
    graph(int _n) : n(_n) {
      g.resize(n);
      ignore = nullptr;
    }
 
    virtual int add(int from, int to, T cost) = 0;
 
    virtual void set_ignore_edge_rule(const function<bool(int)> &f) {
      ignore = f;
    }
 
    virtual void reset_ignore_edge_rule() {
      ignore = nullptr;
    }
};
 
template <typename T>
class digraph : public graph<T> {
  public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;
    using graph<T>::ignore;
 
    digraph(int _n) : graph<T>(_n) {
    }
 
    int add(int from, int to, T cost = 1) {
      assert(0 <= from && from < n && 0 <= to && to < n);
      int id = (int) edges.size();
      g[from].push_back(id);
      edges.push_back({from, to, cost});
      return id;
    }
 
    digraph<T> reverse() const {
      digraph<T> rev(n);
      for (auto &e : edges) {
        rev.add(e.to, e.from, e.cost);
      }
      if (ignore != nullptr) {
        rev.set_ignore_edge_rule([&](int id) {
            return ignore(id);
            });
      }
      return rev;
    }
};
 
template <typename T>
vector<int> find_scc(const digraph<T> &g, int &cnt) {
  digraph<T> g_rev = g.reverse();
  vector<int> order;
  vector<bool> was(g.n, false);
  function<void(int)> dfs1 = [&](int v) {
    was[v] = true;
    for (int id : g.g[v]) {
      if (g.ignore != nullptr && g.ignore(id)) {
        continue;
      }
      auto &e = g.edges[id];
      int to = e.to;
      if (!was[to]) {
        dfs1(to);
      }
    }
    order.push_back(v);
  };
  for (int i = 0; i < g.n; i++) {
    if (!was[i]) {
      dfs1(i);
    }
  }
  vector<int> c(g.n, -1);
  function<void(int)> dfs2 = [&](int v) {
    for (int id : g_rev.g[v]) {
      if (g_rev.ignore != nullptr && g_rev.ignore(id)) {
        continue;
      }
      auto &e = g_rev.edges[id];
      int to = e.to;
      if (c[to] == -1) {
        c[to] = c[v];
        dfs2(to);
      }
    }
  };
  cnt = 0;
  for (int id = g.n - 1; id >= 0; id--) {
    int i = order[id];
    if (c[i] != -1) {
      continue;
    }
    c[i] = cnt++;
    dfs2(i);
  }
  return c;
  // c[i] <= c[j] for every edge i -> j
}
 
class twosat {
  public:
    digraph<int> g;
    int n;
 
    twosat(int _n) : g(digraph<int>(2 * _n)), n(_n) {
    }
 
    inline void add(int x, int value_x) {
      // (v[x] == value_x)
      assert(0 <= x && x < n);
      assert(0 <= value_x && value_x <= 1);
      g.add(2 * x + (value_x ^ 1), 2 * x + value_x);
    }
 
    inline void add(int x, int value_x, int y, int value_y) {
      // (v[x] == value_x || v[y] == value_y)
      assert(0 <= x && x < n && 0 <= y && y < n);
      assert(0 <= value_x && value_x <= 1 && 0 <= value_y && value_y <= 1);
      g.add(2 * x + (value_x ^ 1), 2 * y + value_y);
      g.add(2 * y + (value_y ^ 1), 2 * x + value_x);
    }
 
    inline vector<int> solve() {
      int cnt;
      vector<int> c = find_scc(g, cnt);
      vector<int> res(n);
      for (int i = 0; i < n; i++) {
        if (c[2 * i] == c[2 * i + 1]) {
          return vector<int>();
        }
        res* = (c[2 * i] < c[2 * i + 1]);
      }
      return res;
    }
};
int rint(char nxt){
  char ch=getchar();
  int v=0;
  int sgn=1;
  if(ch=='-')sgn=-1;  
  else{
    assert('0'<=ch&&ch<='9');
    v=ch-'0';
  }
  while(true){
    ch=getchar();
    if('0'<=ch && ch<='9')v=v*10+ch-'0';
    else{
      assert(ch==nxt);
      break;
    }
  }
  return v*sgn;
}
const int mx=1050;
int a[mx][mx],b[mx][mx];
int n;
bool can(){
  twosat ts(n);
  for(int i=0;i<n;i++){
    if(a[i][i]!=b[i][i])return false;
  }
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j){
    for(int x=0;x<2;x++)for(int y=0;y<2;y++){
      int vals[2]={a[i][j],a[j][i]};
      if(x^y)swap(vals[0],vals[1]);
      if(vals[0]!=b[i][j]){
      /*
        if(x==1)cout<<"not ";
        cout<<i<<" or ";
        if(y==1)cout<<" not ";
        cout<<j<<endl;
      */
        ts.add(i,x^1, j, y^1);
      }
    }
  }
  return !ts.solve().empty();
}
int main(){
//  freopen("secret/0.in","r",stdin);
//  freopen("secret/0.out","w",stdout);
  int t=rint('\n');
  int sm=0;
  while(t--){
    n=rint('\n');
    assert(1<=n&&n<=1024);
    sm+=n*n;
    assert(sm<=(1<<24));
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        a[i][j]=rint(j==n-1?'\n':' ');
        assert(1<=a[i][j]&&a[i][j]<=1e9);
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<n;j++){
        b[i][j]=rint(j==n-1?'\n':' ');
        assert(1<=b[i][j]&&b[i][j]<=1e9);
      }
    }
    if(can())puts("Yes");
    else puts("No");
  }
  assert(getchar()==EOF);
  return 0;
} 

Tester - Using Graph Coloring.

Click to view
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
 
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;
 
string to_string(string s) {
	return '"' + s + '"';
}
 
string to_string(const char* s) {
	return to_string((string) s);
}
 
string to_string(bool b) {
	return (b ? "true" : "false");
}
 
string to_string(char ch) {
	return string("'")+ch+string("'");
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
	bool start = true;
	string res = "{";
	while (first!=last) {
		if (!start) {
			res += ", ";
		}
		start = false;
		res += to_string(*first);
		++first;
	}
	res += "}";
	return res;
}
 
template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
 
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
	input>>x.F>>x.S;
	return input;
}
 
template <typename A>
istream& operator>>(istream& input,vector<A>& x){
	for(auto& i:x)
		input>>i;
	return input;
}
 
 
#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
vector<pii>adj[1<<10];
bool good;
vector<int>vis;
void dfs(int u,int col){
	if(vis){
		if(vis!=col)good=0;
		return;
	}
	vis=col;
	for(auto i:adj){
		dfs(i.F,col*i.S);
	}
}
void solve(){
	int N;
	cin>>N;
	vector<vi>x(N,vi(N));
	vector<vi>y(N,vi(N));
	cin>>x>>y;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(x[i][j]==x[j][i] and y[i][j]==y[j][i] and x[i][j]==y[i][j])continue;
			if(x[i][j]==y[i][j] and x[j][i]==y[j][i]){adj[i].pb({j,1});adj[j].pb({i,1});continue;}
			if(x[j][i]==y[i][j] and x[i][j]==y[j][i]){adj[i].pb({j,-1});adj[j].pb({i,-1});continue;}
			cout<<"No\n";
			rep(i,0,N)adj[i].clear();
			return;
		}
	}
	good=1;
	vis.resize(N);
	fill(all(vis),0);
	rep(i,0,N){
		if(vis[i])continue;
		dfs(i,1);
	}
	if(good){
		cout<<"Yes\n";
	}
	else{
		cout<<"No\n";
	}
	rep(i,0,N)adj[i].clear();
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vis.reserve(1<<10);
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

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

CHEF VIJJU’S CORNER :smiley:

1. Setter’s Notes-

Click to view

Every element can be at A[i][j] or A[j][i], construct a logic expression of n variables (one per each row) and solve with 2sat

2. Tester’s Notes-

Click to view

Element at A[i][j] can either remain at A[i][j] or swap with A[j][i]. So if multiset {A[i][j],A[j][i]} is not same as {B[i][j],B[j][i]}, the answer is NO.

To swap A[i][j] and A[j][i], exactly one of row i and row j must be swapped with respective columns.

Now, if A[i][j]=B[i][j], we have two choices-

1. Swap row i and row j with respective columns
2. Do not swap row i and do not swap row j

So, let’s create a graph with n nodes (each representing a row/column) and paint them red/blue (red for swap that row/column, blue for not swap).

Add edges depending upon A[i][j]==B[i][j] (node i and j must have same color) or A[i][j]==B[j][i] (node i and j must have different color).

Color all nodes using dfs. If it is possible to color all nodes, you get a solution, else answer is NO.

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-

Click to view

2. 2. Yes, Every tree is a bipartite graph. However, converse is not true (Bipartite graph can have cycles!)

4. Related Problems-

3 Likes

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

1 Like

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

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

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

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.

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

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

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.

exactly its unfair

1 Like

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

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[j] == A[j] == B[j]* == B*[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.**”

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

1 Like

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 N
T=(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(N
3) solution passed:)

1 Like

it’s answer is no right?

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 :slight_smile:

Got it. Thanks :slight_smile:

Another related problem is https://www.codechef.com/LTIME65A/problems/ROBAGAIN