**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 A _{i})**, you should precompute it in the very beginning and use the precomputed values, rather than calculating them in the checking function.