Problem link :
Contest
Practice
Difficulty : Easy
Pre-requisites : Binary Search, Graph bipartiteness
Problem : Split the given numbers in two groups in such a way that the maximal value of the similarity function of any two numbers within one set is the maximal possible
Explanation
Let’s do the binary search on the answer’s value. Now let’s state a way to check, whether it is possible to split the numbers in two groups in such a way that the maximal similarity of any two numbers within a single group doesn’t exceed some number X.
To do this, let’s build a graph of N nodes, where the nodes will correspond to the numbers. Then, let’s add an edge between the node i and the node j in case the i-th and the j-th number has the similarity function value greater than X (i.e. they cannot belong to a single group). Now, you can easily see that you can split all the numbers in two groups only in case the graph is 2-colorable, in the other words - the bipartite one.
We should also point out that since the similarity function is calculated in O(log max Ai), you should precompute it in the very beginning and use the precomputed values, rather than calculating them in the checking function.