PROBLEM LINK:
Authors: Arjun Arul, Praveen Dhinwa
Testers: Misha Chorniy
Editorialist: Praveen Dhinwa
DIFFICULTY:
medium-hard
PREREQUISITES:
Graph theory, bipartite graph, interval graph
PROBLEM:
A graph is called far graph if you can find a positive even integer L, and you can assign distinct integers a_i to its nodes such that there will be an edge between node i and j if and only if |a_i - a_j| \geq \frac{L}{2}.
You are given a graph G, tell whether this graph is a possible far graph or not. If yes, output any possible assignment of a_i values to the nodes.
Solve a simplified version
Let us assume that the problem has the condition for an edge to be | a_i - a_j | > \frac{L}{2} instead of | a_i - a_j | \geq \frac{L}{2}. Also note that for better understanding, we will output the values with the condition: 0 \leq a_i \leq L. In the original problem, you will have to output values with condition -\frac{L}{2} \leq a_i \leq \frac{L}{2}.
Let us now take any valid assignment of values to the integers and analyze the structure of the induced far graph:
Note that the set of points in [0, \frac{L}{2}] and (\frac{L}{2}, L] will form independent sets. In other words, there won’t be edges between two numbers if they both lie in the range [0, \frac{L}{2}], or in the range (\frac{L}{2}, L]. This is because there can’t exist two elements in these ranges that can have their difference greater than the length of the respective range(i.e., \frac{L}{2}). Hence, you can see that the resulting graph will be a bipartite graph.
Suppose a_1 < a_2 < ... < a_n. If we view the points a_i in [0, \frac{L}{2}] in ascending order, the neighborhoods would form a chain based on inclusion. Formally, let i, j be two indices such that i < j and 0 \leq a_i < a_j \leq \frac{L}{2}. Then the neighbors of i will be all the integers in the range [k, n] such that a_k - a_i > \frac{L}{2}. The point to note is that, the neighbors of j will be all integers in the range [k', n] for some k’ such that k' \geq k. Thus, the neighborhood of a point will be contained in the neighborhood of a point to its left.
Similarly, for the points in the range (\frac{L}{2}, L], a similar condition applies.
It turns out that this is a necessary and sufficient condition. That is, the given graph should be bipartite, and in both the partitions, the neighborhood sets of all the vertices should form a chain based on inclusion. Why is this true? Due to above arguments, you can easily see that it’s a necessary condition. As for proving sufficiency, you can greedily assign the coordinates, if these conditions are met (explained below). Thus we prove that this condition is also sufficient (ie. proof by construction).
Also note that in a valid far graph, excluding the vertices with degree 0, there is a unique bi-partition.
Details of greedy assignment
We first find any bipartition of the graph. Let A, B the bipartitions. Without loss of generality, we can assume that the partition A will be the integers in the range [0, \frac{L}{2}). We can sort the vertices in decreasing order of degree, that way we can find the order of integers a_i corresponding to the A. Similarly, for B, we can sort the integers in the increasing order of degree and that will give us the order of integers a_i for B.
Finding the actual integers a_i can be done after this. You can go in the set of vertices of A from right to left and can assign the values to some elements of B (from right to left). The ranges of values are up to 10^9, so you can assign large enough values for L and for array a.
You might have to consider degree zero elements in your code carefully.
Handle the original version
But with | a_i - a_j | \geq \frac{L}{2}, the graph need not be bipartite as 0, \frac{L}{2}, L could form a 3-cycle. Observe that if you remove this 3-cycle, then the graph is bi-partite. So this is the only obstruction. In this case, you do the same algorithm as above, but after fixing these 3 points. A few more additional conditions need to be checked too. For example, if the graph contains a 3-cycle and there exists a vertex with zero degrees, then there can’t exist a far graph for this situation and answer would be No. Suppose the 3-cycle is between a_1, a_i, a_n, then the degree of a_i should be exactly two.
Checking whether a graph contains three cycles.
For each node, we can store bitset for all of its neighbors. For checking whether the vertices u, v, w form a triangle can be done by checking whether u, v have an edge and whether w lies in the intersection of neighbors of u and v. These operations can be performed by bitwise operations to obtain a total of \mathcal{O}(\frac{n^3}{32}).
In fact, for this problem, you can use direct brute-force in \mathcal{O}(n^3/6) operations. This will also pass within time.
There is an interesting and faster solution to find the 3-cycle using the structure of the far graph. Note that only a_1, a_i, a_n can form a 3-cycle for some single i. One of the nodes a_1, a_n should have the maximal degree in the entire graph. Wlog assume it is a_1. The node a_n will be the neighbor of a_1 with the maximal degree. This way you will have fixed two of the endpoints of the 3-cycle, now iterate over all other n-2 vertices and check whether a_1, a_n and that vertex form a cycle or not.
The simplified version is called Difference Graphs in literature, and you can read more about them [here] 888.