Hello, codeforces!
Recently I came up with a task, but I couldn't solve it.
The task is:
You are given a two arrays a and b of size n (1 ≤ n ≤ 105). You should answer q (1 ≤ q ≤ 105) queries:
- for given integer k (1 ≤ k ≤ n) you need to find maximal value ai + bk - i.
Basically you want to compute the max convolution of two array in subquadratic time. I once spent like 3 hours searching for it and only found some recent articles mentioning that no prior results are known to solve it. I found at the time some probabilistic method (written by some Germans about 40 years ago) that worked in practice but failed really hard certain tests. My final answer would be: I'm 99% sure there is no known solution yet. There was some algorithm in N^1.8something (that worked only if the arrays met certain conditions and from what I've read in practice it worked as bad as N^2)
PS: Also, I find the post extremely useful because it took me a lot to find out what I just said about the problem, and it's also the kind of subproblem that may appear as part of solving other tasks that it'd be better to know if it is solvable or not
For fun, could you share the probabilistic method?
https://www.gams.com//TR-93-01.pdf
here is the probabilistic method written by some Germans about 40 years ago (1993)
Yep that's it. Seems like my memory starts failing:)) 15 years difference
Sorry, i misunderstood you
I see only that we can change ai+bk-i to 1,00000001^ai*1,00000001^bk-i and now it more similar to multiplication of polynomials.
Like geniucos has mentioned, this might be a bit of a challenging problem.
What are you trying to compute is called convolution in the "tropical semiring". You can find more on here: Link
My only idea would be to employ some kind of randomized algorithm with a good "success" rate.
What's range for
a_iandb_i,10^5or10^9Does it matter? If so 109 will be better.
I remember that there is an early cf problem .. but i can't find .. sorrry