NikitaMikhaylov's blog

By NikitaMikhaylov, history, 2 years ago, In English,

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.
 
 
 
 
  • Vote: I like it
  • +58
  • Vote: I do not like it

»
2 years ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

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, # |
  Vote: I like it +21 Vote: I do not like it

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   Vote: I like it +10 Vote: I do not like it

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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's range for a_i and b_i, 10^5 or 10^9

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does it matter? If so 109 will be better.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I remember that there is an early cf problem .. but i can't find .. sorrry