DIVIDE - Editorial

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.

Solutions : setter tester

can any body give a psuedo code of the above problem?

It says error 403 when I try to view setter and tester solutions

2 Likes