zglicz's blog

"Convolution" sum of 2 increasing sequences.
By zglicz, history, 3 years ago, In English

I was working on a different problem and I would need to solve this as a subproblem in faster than $$$O(n^2)$$$ to solve the actual problem.

Statement

You are given 2 arrays $$$a_{0}, a_{1}, ..., a_{n-1}$$$ and $$$b_{0}, b_{1}, ..., b_{n-1}$$$, both increasing i.e. $$$\forall_{0 \leq i < n - 1}$$$ $$$a_{i} \leq a_{i+1}$$$ and $$$b_{i} \leq b_{i+1}$$$ and also $$$\forall_{i} a_{i} \geq 0, b_{i} \geq 0$$$. You task is to find array $$$c$$$ such that:

$$$c_i = max_{0 \leq j < 2 * n} a_{j} + b_{i-j}.$$$

For example, for $$$a = [2, 3, 5, 8]$$$ and $$$b = [1, 4, 7, 8]$$$, the result would be $$$c = [3, 6, 9, 10, 12, 15, 16]$$$.

So the simple code to solve this is:

for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
    c[i + j] = max(c[i + j], a[i] + b[j]);
  }
}

Tried approach

I had a few ideas of attacking this by drawing out the full matrix of sums of $$$a$$$ x $$$b$$$ and trying to notice that the $$$c_{i}$$$'s will form a path within this matrix from the top-left to lower-right corner, but I wasn't able to complete this. Is there a better solution than the proposed brute-force solution?

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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It's called concave max plus convolution.

https://cstheory.stackexchange.com/questions/19982/complexity-of-convolution-in-the-max-plus-ring

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

    If both $$$a$$$ and $$$b$$$ are convex ($$$a_{i+1}-a_{i}$$$ is monotonically increasing), then $$$c$$$ is convex and we can calculate $$$c$$$ in $$$O(n)$$$ time using SMAWK, or $$$O(n\log n)$$$ time using divide and conquer — the divide and conquer solution is to notice that for any $$$i$$$ the optimal $$$j$$$ is monotonic.

    I'm not sure if there is a solution for when $$$a$$$ and $$$b$$$ are merely increasing — the general problem, max-plus convolution, currently has no solution significantly faster than $$$O(n^2)$$$.

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

      If both $$$a$$$ and $$$b$$$ are convex, you can just do simple two pointers technique to compute the "convolution" (no need for D&C/SMAWK).

      If you keep the partial differences arrays instead of the original ones, it's even simpler:

      Spoiler
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you elaborate more on the 2 pointers technique? Thanks.

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

          Start with $$$a_0 + b_0$$$ and iteratively choose the best value from $$$a_{i+1} + b_j$$$ or $$$a_{j+1}+b_i$$$ (and increment the corresponding pointer).

          Note that this approach only works for concave functions (in the maximization scenario) or convex functions (in the minimization scenario).

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

          Basically merge the difference arrays then do prefix sum.

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

You probably can't do much better than brute-force solution unless values are bounded. https://arxiv.org/abs/1811.12554 could be relevant.

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

To add to all that's been said, this is (almost) as difficult as max-plus convolution since you can do a[i] += i * INF; b[i] += i * INF.

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

    How is this not a perfect reduction and thus precisely as difficult?

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

      I just meant the numbers can get $$$n$$$ times larger.

      → Reply