DOOFST - Editorial

Contest : Division 1

Contest : Division 2

Practice

Setter : Kasra Mazaheri

Tester : Istvan Nagy

Editorialist : Anand Jaisingh

Medium

Graph Theory.

PROBLEM :

You are given a graph G consisting of N nodes and M edges. We need to find a sequence of moves to convert a graph G' with N nodes and 0 edges into the given graph. Now, in a single move, we can divide the set \{1,2,...N \} into 2 groups. After this move, there will be added an edge in G' ( if it did not exist ) between any two nodes lying in different groups. Each move is independent of one another.

We need to find and print any such sequence of moves, such that after these, G=G'

Quick Explanation :

It can be proven that if a solution exists, we can create a new graph G_{new} consisting of many connected components, such that in each component, for any pair of nodes in it, there does not exist an edge between them in the original graph G, and for any pair of nodes in different connected components in G_{new}, there exists an edge between them in G.

Now, when we divide the graph into 2 groups during a single move, all the nodes in a single connected component in G_{new} shall always appear in the group.

So, the task then comes down to finding a set of moves, such that using them, any pair of connected components from G_{new} appear in a different group at least once. This can be accomplished using some bit-manipulation/divide and conquer.

EXPLANATION :

First of all, I’m sorry for the delay in posting this editorial, I was quite exhausted after writing the first 9 ones

This problem is about making some crucial observations and some basic graph theory. Let’s go ahead and make some observations.

Let’s call the graph given in the input as graph G, and the division of the graph into 2 groups as a single move.

Observation 1.

For any pair of nodes a,b such that the edge (a,b) does not exist in the given graph G, in any move they shall always be in the same group.

Proof :

We’ll proceed with proof by contradiction. Let’s assume for a pair of nodes a,b an edge does not exist between them in G, and they appear in different groups in at least a single move. Then, in such a case we introduce hatred between these 2 nodes. But since the edge (a,b) does not exist, there should not exist hatred between these nodes.

Using this observation, we create a new graph G_{new}, consisting of many connected components, where, for every pair of nodes a,b if there is no edge between them in G, then they are in the same connected component in G_{new}

Observation 2

If for any pair of nodes a,b such the edge (a,b) does exists in the graph G, they should be in different connected components in G_{new}

Proof :

If a pair of nodes a,b are in the same connected component in G, then it implies in any move they shall be in the same group. But since, the edge (a,b) exists in the graph G, they should have to appear in different groups at least once, which is a contradiction.

Now, we should check if the given graph G is such that we can build a valid graph G_{new} from it. To build the graph G_{new}, we can do a DFS over the inverse graph \bar{G} of G. If not, we should simply print -1. For example, you can check this exclusive codeforces problem based on exactly the same.

If a valid graph G_{new} can be built, then our given task now transforms to : Find a set of moves, such that for any pair of connected components in G_{new}, they appear in different groups in at least one of those moves.

We can accomplish this part using some divide and conquer. Let the connected components be c_1,c_2,....c_m. Then, we take the components, divide them into 2 subarrays, through the middle, introduce hatred between components in different subarray in this move, and then in the next move, we solve recursively for each of the subarrays.

For example, the pseudo-code for such a function would be something like :

 void Solve(int l, int r, int muv)
{
int md = (l + r) >> 1;
if (l == r)
return ;
for (int i = l; i <= md; i ++)
{
for all nodes x in connected component i
{
set color of node x in move number "muv" as '1'.
}
}
Solve(l, md, muv + 1);
Solve(md + 1, r, muv + 1);
}


This would take exactly \left\lceil{\log_{2}(N)}\right\rceil steps at max. For example, assume G_{new} consists of 6 components, then we could introduce the hatred between components as follows :

Move 1 : 111000 ( We divide the range [1,6] through the middle

Move 2 : 100100

Move 3 : 010010

We can just check if \log_2{M} \cdot N \le 10^6 , and if not print -1. Else we can print these sets and we’re done. We can easily see, that after this, each connected component will appear in a different group from every other component at least once.

That’s it, thank you !

COMPLEXITY ANALYSIS :

Time Complexity : O( N \cdot \log(N) + M )

Space Complexity : O(N \cdot \log(N)+M).

Setter
// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, LG = 11;
int n, m, k, cp, C[N], M[N];
vector < int > Adj[N], V[N];
char S[LG][N];
void Solve(int l, int r, int h)
{
int md = (l + r) >> 1;
if (l == r)
return ;
k = max(k, h);
for (int i = l; i <= md; i ++)
for (int j : V[i])
S[h][j] = 1;
Solve(l, md, h + 1);
Solve(md + 1, r, h + 1);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++)
{
int v, u;
scanf("%d%d", &v, &u);
}
long long mp = 1LL * n * (n - 1) / 2;
for (int i = 1; i <= n; i ++)
if (!C[i])
{
cp ++;
int cnt = 0;
memset(M, 0, sizeof(M));
M[j] = 1;
for (int j = 1; j <= n; j ++)
if (!M[j] && C[j])
return !printf("-1\n");
for (int j = 1; j <= n; j ++)
if (!M[j]) C[j] = cp, cnt ++;
mp -= 1LL * cnt * (cnt - 1) / 2;
}
for (int i = 1; i <= n; i ++)
if (C[i] == C[j])
return !printf("-1\n");
if (mp != m)
return !printf("-1\n");
for (int i = 1; i <= n; i ++)
V[C[i]].push_back(i);
Solve(1, cp, 1);
for (int i = 1; i <= k; i ++)
for (int j = 1; j <= n; j ++)
S[i][j] += '0';
printf("%d\n", k);
for (int i = 1; i <= k; i ++)
printf("%s\n", &S[i][1]);
return 0;
}

Tester
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd || g == -1) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}

string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

using namespace std;
int main(int argc, char** argv)
{
#ifdef HOME
if (IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int n, m, u, v;

vector<pair<int, int> > edges(m);
vector<vector<int> > neighb(n);
set<pair<int, int> > ss;
for (uint32_t i = 0; i < m; ++i)
{
//scanf("%d %d", &u, &v);
--u, --v;
assert(u != v);
assert(ss.count(make_pair(min(u, v), max(u, v))) == 0);
ss.insert(make_pair(min(u, v), max(u, v)));
edges[i] = { u, v };
neighb[u].push_back(v);
neighb[v].push_back(u);
}
assert(getchar() == -1);
for (auto& actn : neighb)
{
sort(actn.begin(), actn.end());
}
vector<int> part(n, -1);
int64_t edgeCtr = 0;
int partctr = 0;
for (uint32_t i = 0; i < n; ++i) if (part[i] == -1)
{
part[i] = partctr++;
auto& actn = neighb[i];
auto it = lower_bound(actn.begin(), actn.end(), i);
int actitem = i + 1;
while (actitem < n)
{
if (it == actn.end() || *it > actitem)
{
part[actitem++] = part[i];
}
else if (*it == actitem)
{
actitem++;
++it;
}
else
{
assert(false);
}
}
}

int twop = 0;
while ((1 << twop) < partctr)
twop++;
if (twop * n > 1000000)
{
printf("-1\n");
return 0;
}
vector<string> fin(twop, string(n, '0'));
vector<vector<int> > v1(twop), v2(twop);
set<pair<int, int> > s;
bool ok = true;
for (int i = 0; i < twop; ++i)
{
for (int j = 0; j < n; ++j)
{
bool acts = part[j] & (1 << i);
if (acts)
{
v1[i].push_back(j);
fin[i][j] = '1';
}
else
{
v2[i].push_back(j);
}

}
if (v1[i].size()*static_cast<int64_t>(v2[i].size()) > edges.size())
{
printf("-1\n");
return 0;
}
for (auto a : v1[i])
for (auto b : v2[i])
{
s.insert(make_pair(min(a, b), max(a, b)));
}
if (s.size() > edges.size())
{
printf("-1\n");
return 0;
}
}
if (s.size() != edges.size())
{
printf("-1\n");
return 0;
}
printf("%d\n", twop);
for (auto& str : fin)
{
printf("%s\n", str.c_str());
}
return 0;
}

6 Likes

Thanks so much for posting it

Edit:

Weird - the forum software turned the 9 into 999 - I bet it feels like that many anyway XD

1 Like

How to handle the case for printing the - 1?

This way you can check if it is -1

Can there be a portal where problems are solved or explained in the form of video?

@anand20 Well explained! I am expecting more of this kind of explanation in editorials. The reference problem was equally good. It will be helpful if you could add your code at the end of editorial.

1 Like