YouKn0wWho's blog

Yet Another Convolution?
By YouKn0wWho, 4 years ago, In English

So this problem just popped out of my head:

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$$$$(1 \leq n \leq 10^5, -10^9 \leq a_i, b_i \leq 10^9)$$$. Find an array $$$c$$$ of size $$$n$$$ such that

$$$c_k = \max\limits_{i + j = k}(a_i + b_j)$$$

It looks like a classical problem but I couldn't able to find a working solution. Can anyone help?

  • Vote: I like it
  • +51
  • Vote: I do not like it

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

I think many have thought of this before, and there exists no algorithm better than $$$O(n^2)$$$. However, you may find this interesting.

Edit: Found the source for my claim: here.

→ Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I found this.

$$$\mathcal{O} \left(\frac{n^2 (\log \log n)^3}{\log^2 n}\right)$$$ seems really scary.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I meant that no algorithm asymptotically $$$O(n^{2-\epsilon})$$$ exists, if this was a reply to me. I should have clarified that. (Source added in comment above)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Isn’t this just knapsack? It’s highly unlikely to have better complexity than quadratic, because if you cpuld, you would solve knapsack better than quadratically.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

There are some reductions to and from this problem, so existence of truly-subquadratic algorithm for it is quite unlikely.

There is a nice paper describing most of the recent results related to this problem including reductions to this problem, approximate, parametrized and $$$o(n^2)$$$ (but not $$$O(n^{2-\epsilon})$$$) algorithms for it.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

I am quite sure this problem (or a very similar one) was posed on some old Codeforces round as Div1B for n<=1e5 with guarantee that input sequence is random in some way. However I don't remember any keywords, so I don't know how to search for it.

EDIT: OK, it turns out it took me half a minute to find it xD https://codeforces.com/problemset/problem/444/B?locale=en There is product there and one of the sequences is zero-one.

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

If we have special property called "concavity" on both array $$$a$$$ and $$$b$$$, we can solve it in $$$O(n)$$$. For array $$$v = (v_1, v_2, ..., v_n)$$$, the array $$$v$$$ is concave if $$$v_i - v_{i+1}$$$ is decreasing.

That's because (if concavity holds), when $$$c_k$$$ is selected from $$$a_i + b_j$$$, the value of $$$c_{k+1}$$$ is the larger value of $$$a_{i+1} + b_j$$$ and $$$a_i + b_{j+1}$$$. We can choose it greedily.

There are many problems which uses this technique, even in competitive programming.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Oh yeah, that's a nice remark! We can regard to it as Minkowski's sum kind of thing since Minkowski's sum of areas above the plot of a and area above the plot of b (if we connect consecutive points with segments) is exactly the area above the plot of c. Sometimes this property is used when computing Minkowski's sum of polygons, since that is basically the same.

    → Reply