3
$\begingroup$

I am trying to solve a competitive-programming-style problem which I've boiled down to the following: given two arrays $a, b$ of length $n$, where $a_i, b_i > 0$ for all $i=1\ldots n$, compute $$\max_{i, j : i\neq j} \quad a_ib_i + a_jb_j + \max \{ a_ib_j, a_jb_i \}. $$

Of course, this can be solved by brute force by searching over all relevant pairs $(i,j)$, which is $\Theta (n^2)$. I'm wondering how to come about a more efficient solution, e.g. running in $\mathcal{O} (n\log n)$ time.

I toyed around with an approach where I sorted $a$ and $b$, then iterated through $i = 1\ldots n$ and performed binary-searches at each iteration, but I've been unable to get the right answer, much less prove correctness. I thought of a geometric interpretation of the objective in terms of areas of rectangles, which led me to an alternate form of the objective: $$\max_{i,j : i\neq j} \quad (a_i + a_j)(b_i + b_j) - \min\{ a_ib_j, a_jb_i \},$$ but I'm not sure this is useful.

I would appreciate some help figuring out how to tackle this problem.

$\endgroup$
2
  • $\begingroup$ Can the numbers be negative? $\endgroup$
    – rus9384
    Dec 15, 2023 at 13:02
  • $\begingroup$ @rus9384 $a_i,b_i>0$ for all $i=1..n$ $\endgroup$ Dec 15, 2023 at 15:14

5 Answers 5

2
$\begingroup$

I think it is possible to solve this problem in $\mathcal O(n \log n)$. Note that this is an improvement to this answer, which previously did not handle that $i \ne j$. See below for how this is added. Also note that what described below is a version of the Convex Hull Trick.

First, observe that the $\max\{a_i b_j, a_j b_i\}$ is unnecessary: It can be replaced by $a_i b_j$, since we get the other result by swapping $i, j$.

This leaves us with finding this: $$\max_{i, j} \quad a_ib_i + a_jb_j + a_ib_j $$

Our approach will now be to iterate over $i$ and find the largest $j$ in $\mathcal O(\log n)$ time. Note that for this, it suffices to, given $c$, find $j$ maximizing this: $$\max_{j} \quad (a_j + c) b_j $$ (Set $c := a_i$ and observe that $a_i b_i$ is not dependent on $j$)

Now notice that this defines a collection of functions $f_j(x) = a_j b_j + x b_j$, which are all linear (plus offset). We now want to find which of these functions is the largest, given $x$. We now build a data structure that can solve this quickly (i.e. in $\log n$).

First notice that for functions with the same $b_j$, the one with the highest $a_j$ is always higher. Geometrically, these are parallel lines, but those with higher $a_j$ are higher. We thus ignore all such dominated functions.

Then notice that a function with higher $b_j$ eventually dominates those with smaller $b_j$. We will now build a ordered list, where the function that dominates for $x \to \infty$ comes first, the ones that dominates to the left of it comes second, etc. The list will only contain those functions that dominate somewhere. Graphically, the list would contain [black, blue, red, green] , since the functions in this image below would dominate in that order from right to left. orange does not appear, since it dominates nowhere:

enter image description here

So we start with the function with the highest $b_j$ and add it to the list. The list is ordered such that the functions dominating more left come last, and we add from the back¹. Not that each function dominates in a unique interval. We also store the right end of this interval (which is $+\infty$ for the first function).

We now add the other functions, in order of decreasing $b_j$. (This means we sort the arrays once, which is $\mathcal O(n \log n)$). To add such a function $f$, compare it with the function $g$ currently dominating the most on the left (which is the last function in the list). There are several options, depending on where $g$ starts dominating $f$ (which we can compute easily with some linear algebra):

  • $f$ dominates $g$ on some interval, but not on the entire interval where $g$ dominates. It still leaves space for $g$ to dominate somewhere. In this case, we add $f$ to the back of the list.
  • $f$ dominates $g$ everywhere. In this case, we remove $g$ (we drop $g$), and continue with the rest of the list.
  • $f$ dominates $g$ nowhere: Technically, the point of domination is $<0$. As an optimization, we can choose to do leave the list unchanged (but it does not really matter, the algorithm should still work for numbers $<0$).
  • As a special case, we can also do the pruning of smaller functions with equal $b_j$ here: If two functions have same $b_j$, process those with higher $a_j$ first, and drop the others here since they never dominate.

The runtime analysis here is easy, once you see that each step either adds a function directly, or drops a function, where each function is only dropped once. Thus by amortized analysis, where each function in the list has a potential of $2$ (and adding thus requires a potential of $3$), we see that this is works in $\mathcal O(n)$.

We now have a sorted list that tells us where each function dominates. Thus, we can find the highest function for given $x$ in $\mathcal O(\log n)$ by binary search.

This means we're done. We can find for each $i$ the highest $j$ by doing the above binary search with $x := c := a_i$. We have $n$ iterations of the outer loop, each taking $\mathcal O(\log n)$. We also have $\mathcal O(n \log n) + \mathcal O(n)$ (for sorting and building the function sorted list) of setup time. Together, that's $\mathcal O(n \log n)$.


To handle $i \ne j$, we must additionally keep track of the second-highest function each. This seems to actually not be that hard, the trick is to maintain a similar data structure for the second-highest function.

When adding a function $f$, all the functions that we dropped are now the second-highest functions on the interval left of the intersection point of $f$ with $g$ (the function it non-trivially intersects with). But first, we notice that right of the intersection point, $f$ is now a candidate for the second-highest function, that is also higher than all second-highest functions left of the intersection point. So we can add it to the second-highest-function lookup structure (using a regular insert), and then force-add all the things we dropped, that were to the left of the intersection point. What is tricky here is that there are various edge-cases, and that the data structure is no longer as well-behaved (since when going right, functions can become less steep).

This idea actually generalized to also keeping track of the $m$-th highest list. The runtime complexity for an insert should then be $\mathcal O(n m)$ using amortized analysis. For us, $m=2$ is sufficient, making it linear.

I've implemented this, and tested it a bit, and it seems to work. But I am sure there are bugs somewhere, and it's quite possible that this approach is wrong in general. But have a look yourself here: https://github.com/JoJoDeveloping/some-optimization-problem

Unfortunately, I don't see how to extend this to handling $i \neq j$. Perhaps you can somehow save the second-hightest function for each point? But I don't know how to build this lookup structure efficiently. The second-highest function is also way less well-behaved (observe that blue is the second-highest function for two disjoint intervals in the picture above).


1: This allows us to use an array. Alternatively, we can use a linked list and convert it to an array later.

$\endgroup$
4
  • 2
    $\begingroup$ thanks for this writeup, it's a clever perspective I wouldn't have thought of. I haven't thought of a way to address the $i\neq j$ constraint yet either. $\endgroup$ Dec 14, 2023 at 5:45
  • 1
    $\begingroup$ @ArchieGertsman here's an idea: When you add a function $f$ to the lookup structure that dominates $g$ somewhere, the function you just dominated is the second-highest function everywhere until that point where they intersect. From this point, if you have a similar data structure for the second-highest function, you can insert $f$ into this with the existing algorithm (since is a candidate for the second-highest function). But beware of off-by-1s wrt two identical functions, functions with the same gradient, and what happens precisely at the intersection point (where both functions are equal). $\endgroup$ Dec 14, 2023 at 15:38
  • 1
    $\begingroup$ @ArchieGertsman see my edits. $\endgroup$ Dec 15, 2023 at 2:40
  • 2
    $\begingroup$ Interesting, I'll check out your code! I also came up with my own version that doesn't require a second data structure, but I'm still trying to convince myself it's correct. Like you say, it seems to work from testing but there could be a subtle bug somewhere. I'll keep you posted. $\endgroup$ Dec 15, 2023 at 2:56
1
$\begingroup$

Okay, so I think I found a bit of an optimization?


Firstly, since arrays are accessed by the same index, - you aren't dealing with 2 arrays, you're dealing with array of 2-tuples
and 2-tuples can represent points on 2D plane: $(x_i, y_i)$

And for brevity, let's call what we optimize over as function $f()$: $$f((x_1,y_1), (x_2,y_2)) := x_1y_1 + x_2y_2 + max(x_1y_2, x_2y_1)$$


Main property to use is this:

$$x_1 \le x_2\text{ and }y_1 \le y_2\implies\forall P : f((x_1,y_1), P)\le f((x_2,y_2),P)$$

So we can define that condition as partial ordering
$$P_1(x_1,y_1) \le P_2(x_2,y_2) \iff x_1\le x_2 \text{ and } y_1\le y_2$$

In other words, points that are "above and to the right at the same time" are "bigger" and can be substituted in place of "smaller" ones to get bigger value.
This allows us to prune "smaller" points, with only exception being... taking "bigger" and "smaller" point together (because we can't repeat indices)

This gives a way for 2 pruning techniques:

1) if point is less than 2 (or more) other points - prune it completely
2) if point $P_1$ is less than only 1 other point $P_2$ - prune it, but store $f(P_1,P_2)$

And it can be achieved by
1) sorting our tuples strictly (first by x, and only if $x_1 = x_2$, you sort by y) - $O(n*log(n))$
2) running one sweep from largest x to the smallest, while remembering 2 highest y values encountered - prune by the 2 rules above, store unpruned points and highest encountered f() - $O(n)$


Now you have some candidate maximum $f()_{\text{comparable}}$ and a set of maximal points (incomparable between each other, but bigger than all the rest).

What to do with these? I have no idea

Incomparable points are nice in that in each pair one has "bigger x" and the other has "bigger y" (think about their set as strictly-decreasing function) - so we know which branch is taken in that $max()$ from $f()$

One more idea - x and y can be scaled with same multiple for all points, so now our "strictly-decreasing function" can be limited to $(0,1]\times (0,1]$. Does it give anything? idk

$\endgroup$
1
  • 1
    $\begingroup$ thanks for the pruning ideas! In the case it's impossible to do better than $\Omega(n^2)$, I think pruning is a big improvement over a blind search. $\endgroup$ Dec 14, 2023 at 5:48
1
$\begingroup$

I think if you use my preprocessing before Jojo's line algo, it will work for $i \ne j$

Jojo's algo assumes you need both $ij$ and $ji$ to find the optimum, but my prunning defines exactly which Point should be the first and which should be the second in each pair.

So best "second" Point can be found "on the go" while constructing that line structure


resulting algorithm would be

  1. sort by $x$ and $y$ - $O(n \log n)$
  2. prune lower-left points, get best $f()$ from pruned Points - $O(n)$
  3. for each Point left, in already sorted order - $n \text{ times}$
    a) find best $f()$ from the data structure - $O(\log n)$
    b) add the Point to the data structure - $O(1)$

neither step applies Point onto itself
and (what concerned me much more) same $(a,b)$ tuple repeated would work fine as well


Implementation

$\endgroup$
4
  • 1
    $\begingroup$ I can't quite follow. Why do you do steps 3a) and 3b) interleaved? Can you give an intuition for why this should work? How does your pruning define which point is first, which is second? (And why does this matter, if it's symmetric)? How is it meaningful to query the data structure before having added all points? $\endgroup$ Dec 14, 2023 at 23:10
  • 1
    $\begingroup$ @JoJoModding f() stops being symmetric if we choose one of the max's branches. Your solution counteracts that by computing both, my pruning - by making one branch have both bigger numbers (e.g. i has high a, j has high b). We only need to query once because the other is (small a * small b) branch. Each pair of points is checked once - when later point queries data structure containing earlier point $\endgroup$ Dec 14, 2023 at 23:54
  • 1
    $\begingroup$ I'm not convinced :P but feel free to implement it. You can find an implementation of my answer's idea here: github.com/JoJoDeveloping/some-optimization-problem. It also includes an approach for handling i != j by computing the second-highest function, which I think might work (but could also be terribly broken, as the off-by-ones are quite tricky). $\endgroup$ Dec 15, 2023 at 2:28
  • 1
    $\begingroup$ @JoJoModding gist_link. I tried explaining through the code comments as much as I could. (also please use @ mentions in stackexchange comments - comment sections generally don't get auto-followed to get inbox notifications) $\endgroup$ Dec 15, 2023 at 5:57
0
$\begingroup$

What I would try: Sort the arrays by $a_i \cdot b_i$. Combine them starting with the smallest indices, and you should be able to show that any smaller product needs components of different sizes, because you want to combine a large a_i with a large b_j.

So if the largest products are say about 100, a product 50 x 1 could be useful.

Or maybe make two copies of the arrays, one sorted by a_I and one sorted by b_j, and combine a large a_i with a large b_j.

$\endgroup$
-1
$\begingroup$

If you convert all (ai, bi) to coordinates on a graph, I believe this can be solved similarly to the, closest pairs problem. Which has a nlogn solution, related to comparing all coordinates together to find some max or min value.

$\endgroup$
2
  • $\begingroup$ I don't understand the relationship to the closest pairs problem. You might have two points $(a_1,b_1)$ and $(a_2,b_2)$ that are both very close to each other and where $a_1,a_2,b_1,b_2$ are very small in magnitude, so they lead to a very poor value for the objective function in the original problem. $\endgroup$
    – D.W.
    Dec 13, 2023 at 5:39
  • $\begingroup$ Just generally thinking of divide and conquer, if you split the lists into two halves, and solve those sub-cases individually, we'll have 2 values for i, and 2 values for j (1 for each half) Will the overall list, simply be some i, and j value from the two halves? $\endgroup$ Dec 13, 2023 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.