EFLIP - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Mohammed Ehab
Tester: Ramazan Rakhmatullin
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Hard

PREREQUISITES:

Graphs and Constructive

PROBLEM:

You have to construct a graph G which has a directed edge between each unordered pair of vertices. You have given a sequence of pairs of vertices (a_1, b_1), (a_2, b_2), ..., (a_M, b_M) and does the following of each i from 1 to M in this order :

  • Flip the direction of the edge between vertices a_i and b_i.
  • If the graph is strongly connected either before or after flipping this edge, declare G a bad tournament.

If G is never declared a bad tournament, Chef calls it a good tournament. Given the sequence of M edge flips, find a good tournament.

EXPLANATION:

Subtask 1
As the number of flip edges M = N-2, it is easy to divide the nodes into 2 components s1 and s2 such that all the edges between the nodes of s1 and s2 are directed from s1 to s2 and all the flip edges will be between nodes of s1 or between nodes of s2. This can be easily done by considering the M flips as the undirected edges and you can make one connected component from all the components as s1 and the rest of the components as s2. (Note orientation of the edges in s1 and s2 don’t matter only make sure that all the edges between nodes of s1 and s2 are directed from s1 to s2).

Subtask 2
For it, we will follow the following construction :

  • Choose 1 node in s2 and rest all the nodes in s1. (direct all the edges from nodes of s1 to the single node in s2, rest of the orientation doesn’t matter for now).
  • Iterate through the flip edges, if there is a flip edge which is between s1 and s2 transfer the node which is in s1(let it be x) from s1 to s2 and make the orientation of all the edges between the remaining nodes of s1 and x, from s1 to x, and continue the above process till the condition is satisfied.
  • Now you might argue that there can be several counter test cases for the above approach that’s why we choose the single node in set s2 wisely.
  • For choosing the single node we will iterate through the flip edges and note the first time the node x is involved in the flip, and we will choose the node whose first time is the largest. Why? because by this, the first \frac{N}{2}, flips won’t move any node from s1 to s2 and remaining flips can’t move all the nodes from s1 to s2, hence you will pass the subtask 2.

Subtask 3
It is similar to the above subtask, you just have to try all possible nodes as a single node in s2 and we can prove that one of them will work for M < 2*N-log(N)-2. So will pass subtask 3.

Proof

If we prove there’s a node u whose component only gets bigger in at most log(N) flips, we can take u as the single node, that way, s2's size will be at most log(N)+1 after the first N-1 flips, so we can survive N-log(N)-2 more flips for a total of 2*N-log(N)-3 flips.

Consider first N-1 flips as undirected edges then out of all the connected components formed(can be a single component i.e. a tree of N nodes or multiple components) out of all these components, it is sure that one of them will be a tree. Take that component. Now remove one edge from it and you will get 2 components, take the smaller one whose size \leq \frac{ComponentSize}{2}. Repeat the process till you get a single node which is the required node to start(to put in s2 at beginning of the process).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int n;
bool s[405],mat[405][405],ans[405][405];
void add(int node)
{
	s[node]=1;
	for (int i=1;i<=n;i++)
	{
		if (!s[i])
		{
			ans[node][i]=mat[i][node];
			ans[i][node]=!ans[node][i];
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int m;
		scanf("%d%d",&n,&m);
		vector<pair<int,int> > f;
		for (int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			f.push_back({a,b});
		}
		memset(mat,0,sizeof(mat));
		memset(ans,0,sizeof(ans));
		for (int i=1;i<=n;i++)
		{
			memset(s,0,sizeof(s));
			s[i]=1;
			for (auto p:f)
			{
				s[p.first]|=s[p.second];
				s[p.second]|=s[p.first];
			}
			if (count(s+1,s+n+1,0))
			{
				memset(s,0,sizeof(s));
				add(i);
				break;
			}
		}
		for (auto p:f)
		{
			int a=p.first,b=p.second;
			mat[a][b]^=1;
			mat[b][a]^=1;
			if (s[a]!=s[b])
			add(s[a]? b:a);
		}
		for (int i=1;i<n;i++)
		{
			for (int j=i+1;j<=n;j++)
			printf("%d ",ans[i][j]);
			printf("\n");
		}
	}
}

VIDEO EDITORIAL:

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

1 Like