### NikitaMikhaylov's blog

By NikitaMikhaylov, history, 2 years ago, ,

Hello, codeforces!

Recently I came up with a task, but I couldn't solve it.

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.

• +58

 » 2 years ago, # | ← Rev. 2 →   +30 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
•  » » 2 years ago, # ^ |   0 For fun, could you share the probabilistic method?
•  » » » 2 years ago, # ^ |   +34 https://www.gams.com//TR-93-01.pdfhere is the probabilistic method written by some Germans about 40 years ago (1993)
•  » » » » 2 years ago, # ^ |   +10 Yep that's it. Seems like my memory starts failing:)) 15 years difference
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   -25 Sorry, i misunderstood you
 » 2 years ago, # |   +21 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.
 » 2 years ago, # | ← Rev. 2 →   +10 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: LinkMy only idea would be to employ some kind of randomized algorithm with a good "success" rate.
 » 2 years ago, # |   0 What's range for a_i and b_i, 10^5 or 10^9
•  » » 2 years ago, # ^ |   0 Does it matter? If so 109 will be better.
•  » » » 2 years ago, # ^ |   0 I remember that there is an early cf problem .. but i can't find .. sorrry