2
$\begingroup$

There are two sets of integers with different numbers of items in them.

X= { x_0, x_1, ... x_n }, x_0 < x_1 < ... < x_n
Y= { y_0, y_1, ... y_m }, y_0 < y_1 < ... < y_m

And there is a function of a single integer defined as

F(delta) = CountOfItems( Intersection( X, { y_0+delta, y_1+delta, ... y_m+delta) ) )

That is - i add delta integer to every element of the Y and then count how many same integers are in the X and the modified Y.

And then the problem - find delta that maximizes F(delta).

max( F(delta) ), where delta is integer

Is there some "mathematical" name for such task and optimal algorithm for this? Obviously i can use brute-force here and enumerate all possible combination - but it does not work for big n and m.

$\endgroup$

1 Answer 1

2
$\begingroup$

You can compute the sumset (well, difference set) $X-Y$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT).

As an optimization, I suggest first replacing $X,Y$ with $X'=X \bmod p$, $Y'=Y \bmod p$ where $p$ is at least $n+m$ or so. Then, enumerating through the elements of the multiset $X'-Y'$ by decreasing cardinality will give you good candidates for $\delta \bmod p$. The running time to compute $X'-Y'$ will be $O((n+m)\log (n+m))$, and if the maximum value of $F(\delta)$ is sufficiently large, I expect you should be able to find the correct value for $\delta$ among the first few candidates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.