Given a set of integers. Divide this set into two sets s1 and s2 such that union(s1,s2) = the initial set and intersection(s1,s2) = empty set. Also the difference between any two pairs in s1 should be >= x and in s2 it has to be >=y . Count the number of ways to divide % 1e9+7.
N = [1,1e5]
values = [1,1e18]
Example: [0,2,4,7,8,11,15] x = 5 and y = 3
4 ways
[2,7,15] [0,4,8,11]
[2,8,15] [0,4,7,11]
[2,7] [0,4,8,11,15]
[2,8] [0,4,7,11,15]
if anyone has a link to this similar problem or the solution pls tell. Thanks in advance :)
Assume that x > y and all numbers are put in ascending order.
First, consider the case that the difference between any two adjacent numbers is less than x. In this situation, any two adjacent numbers can't be both in S1.
If there exists an i such that the difference between the (i-1)-th and the (i+1)-th number is less than y, then obviously there's no way to split.
Otherwise:
Let dp[i] be the number of ways to split the first i numbers into two sets satisfying the condition so that the i-th number is in S1.
Now, dp[i] can be transferred from dp[j](j < i) if and only if:
1) the difference between the i-th and the j-th number is not less than x;
2) among the interval (i, j)(exclusive), the difference between any two numbers is not less than y.
The DP algorithm above can be optimalized to O(n log(n)) with precalculation and segment trees.
Now, consider the general case.
If the difference between the i-th and the (i+1)-the number is not less than x, then we can deal with the interval [1, i] and [i+1, n] individually. Or, to say, the final answer is the number of ways to split the interval [1, i] into two sets multiplied by the number of ways to split the interval[i+1, n] into two sets.
This can be done recursively until in each interval, the difference between any two adjacent numbers is less than x. Then, simply multiply the answer to each interval together.
Total complexity: O(n log(n))
UPD: We don't even need to use segment trees -- prefix sum is enough. But as we need to sort the array in ascending order before the main procedure of the algorithm, the complexity is still O(n log(n)).