$$$O(n)$$$.

This is a warmup. Map each pair $$$(x, y)$$$ to $$$x + y$$$, and find the $$$n$$$ smallest resulting values. Their original pairs are the $$$n$$$ pairs you should choose.

Can be done in linear time by finding the median in linear time.

Why can we change all our pairs of integers to a single integer? For which other functions $$$f$$$ could this work?

$$$O(n^4M^2)$$$.

Can also be solved in $$$O(n^3M^2 \cdot \log (nM))$$$.

$$$O(n^4M^2)$$$

Solve with dynamic programming, with the following states:

For each $$$(i, j, x, y)$$$, the value would be $$$1$$$ if we can use exactly $$$j$$$ pairs from the first $$$i$$$ pairs, such that their pointwise sum is $$$(x, y)$$$, and $$$0$$$ otherwise. Here we have $$$0 \leq i \leq 2n, 0 \leq j \leq n, 0 \leq x, y \leq n\cdot M$$$, so overall $$$O(n^4M^2)$$$ states.

Initialize $$$dp[0][*][*][*] = 0$$$, except for $$$dp[0][0][0][0] = 1$$$.

Iterate over all pairs from first to last. On the $$$i$$$-th pair $$$(p,q)$$$, iterate over all $$$(j, x, y)$$$ and set $$$dp[i][j][x][y] = 1$$$ only if one of the following values is 1: $$$dp[i-1][j][x][y], dp[i-1][j-1][x-p][y-q]$$$. For each pair it takes $$$O(n^3M^2)$$$ time, so overall $$$O(n^4M^2)$$$ time here.

In the end, iterate over all $$$(x, y)$$$, and across all of them that satisfy $$$dp[2n][n][x][y] = 1$$$, take the minimum $$$f(x,y)$$$.

With another table of the same size you can reconstruct the chosen pairs. Overall $$$O(n^4M^2)$$$ time and space.

$$$O(n^3M^2 \cdot \log (nM))$$$

This is more advanced. I'll write down the main points, you can work out the details and the time complexity.

• Map each pair $$$(a, b)$$$ to the polynomial $$$P_i(t,x,y) = 1 + tx^ay^b$$$.
• Multiply $$$P_1 \cdot P_2 \cdots P_{2n}$$$ in a D&C fashion using FFT.
• Extract from the product the optimal solution.

• You most likely cannot solve this problem in complexity $$$O(poly(n)\cdot polylog(M))$$$, as this problem is NP-hard, and it can be proven quite easily (prove it).

• Optimize the algorithm in space: Keep the time complexity $$$O(n^4M^2)$$$ but reduce the space complexity to $$$O(n^3M^2)$$$. In this subtask, you are not required to reconstruct the chosen pairs, only output the optimal result $$$f(x, y)$$$.

• (Hard) Optimize space complexity to $$$O(n^3M^2)$$$ with time complexity $$$O(n^4M^2)$$$, and reconstruct the chosen pairs.

$$$O(n^3M)$$$.

This is very similar to problem B, so solve B beforehand. We can prove that we only need to maintain, for each $$$(i,j,x)$$$, the smallest $$$y$$$ such that $$$dp[i][j][x][y] = 1$$$, instead of maintaining all possible $$$y$$$'s. Proof:

Suppose we've found two reachable states in the dynamic programming (i.e their value is 1), differing only in their $$$y$$$ coordinate: $$$(i,j,x,y)$$$ and $$$(i,j,x,y+k)$$$ where $$$k \geq 1$$$.

Suppose some final state $$$(2n,n,X,Y)$$$ is reachable from $$$(i,j,x,y+k)$$$, which means that $$$f(X,Y)$$$ is a reachable solution. Then we can take the same subset of pairs that took us there, and instead use them from $$$(i,j,x,y)$$$ to reach the state $$$(2n,n,X,Y-k)$$$. So $$$f(X,Y-k)$$$ is also a reachable solution, and by monotonicity it is not worse than the other one.

So, just like B, maintain $$$dp[i][j][x]$$$ as the minimum $$$y$$$ such that state $$$(i,j,x,y)$$$ is reachable. This takes $$$O(n^3M)$$$ space. Work out the details so that the time complexity is the same.

• This solution also works for functions monotonic the other way around (decreasing), by maintaining the maximum $$$y$$$ reachable.
• Alter the solution so that it also works for functions $$$f$$$ such that, for every $$$x$$$, the function $$$f(x,*)$$$ first increases and then decreases.
• Like B, the space complexity here can be optimized to $$$O(n^2M)$$$ while the time complexity stays the same.

$$$O(n\log (nM))$$$.

Let's determine whether the answer is at most $$$t$$$ (for some fixed $$$t$$$). We have $$$f(x,y) \leq t \iff x - ty \leq 0$$$ (when $$$y$$$ is positive).

Map each pair $$$(a,b) \to a - tb$$$, and check whether the sum of the $$$n$$$ minimum values is at most $$$0$$$, in linear time by finding the median.

We can binary search the smallest $$$t$$$ which has a solution. How many iterations do we need to do? Since all of our resulting solutions are integers in $$$[1, nM]$$$, the difference $$$|f(x_1, y_1) - f(x_2, y_2)|$$$ is either $$$0$$$, or at least $$$\frac{1}{(nM)^2}$$$. In terms of magnitude, $$$t$$$ is upto $$$M$$$ so the number of iterations required is $$$O(\log_2 n^2M^3) = O(\log nM)$$$.

Total time complexity $$$O(n \log (nM))$$$.

Solve in $$$O(poly(n))$$$, that is, in running time independent of $$$M$$$ (assuming you can do basic operations on numbers of order $$$M$$$ in $$$O(1)$$$ and not $$$O(\log M)$$$).

$$$O(n^2 \log n)$$$.

Consider the optimal solution $$$(X,Y)$$$. Any other solution lies on the set of points $$$\lbrace (p,q) | pq \geq XY \rbrace$$$, which is a convex set. This means there exist real $$$\alpha, \beta$$$ such that $$$(X,Y)$$$ is the solution that minimizes the cost function $$$g_{\alpha, \beta}(x, y) = \alpha x + \beta y$$$ (in particular here, $$$\alpha = X, \beta = Y$$$ but this result is more general). Also, note that minimizing the cost function $$$g$$$ can be done in linear time, given that we've chosen $$$\alpha$$$ and $$$\beta$$$.

The idea would be to sweep through all slopes / pairs of $$$\alpha, \beta$$$ and find the optimal solution respectively. This way we construct the lower-left convex hull of the set of possible solutions, and we've seen, the solution minimizing $$$f$$$ is on this convex hull, so we can then iterate on it.

There are two approaches to actually do this:

1. Build the convex hull recursively. First, solve $$$g_{1,0}$$$ to get the leftmost point of the hull, and $$$g_{0,1}$$$ for the bottommost. Now let's define a recursive function that determines all points on the lower-left convex hull between two points $$$p_1, p_2$$$: take the slope of the line passing through points $$$p_1, p_2$$$, and solve the respective $$$g$$$ function. If the resulting solution is either $$$p_1$$$ or $$$p_2$$$ then there is no point between them (return). Otherwise if we got a point $$$q$$$, then solve recursively for $$$(p_1, q)$$$ and for $$$(q, p_2)$$$. The running time is the time to compute $$$g$$$ ($$$O(n)$$$), times the number of points in the convex hull. There are apparently $$$O(n^2)$$$ points on the convex hull — the 2nd approach proves and uses it.

2. Imagine sweeping through all slopes, and at any moment maintaining the sorted order of input pairs. The respective solution is the first $$$n$$$ pairs — so, if during the sweep we moved to a different point on the convex hull, then in particular the order of pairs changed. Since any 2 pairs swap positions at most once, this means there are $$$O(n^2)$$$ changes done to the sorted order we maintain, and therefore $$$O(n^2)$$$ points on the convex hull. You can precompute for each pair of points the slope at which they swap (or alternatively do an "online" approach using a priority queue), and iterate over all possible sorted orders in $$$O(n^2 \log n)$$$, while simultaneously maintaining the sum of the first $$$n$$$ pairs.

Approach 1 results in $$$O(n^3)$$$ time complexity while approach 2 in $$$O(n^2 \log n)$$$.

Solve the problem in $$$k$$$ dimensions, with $$$f(x_1, \ldots, x_k) = x_1 \cdots x_k$$$, in running time $$$n^O(k)$$$.

If the $$$k$$$-dimensional problem is solvable in $$$O(poly(n)poly(k))$$$, does this imply $$$\text{P = NP}$$$? I actually haven't shown this yet, but I feel like it does.