$$$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 in 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 = Y, \beta = X$$$ 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.

This case is NP-hard (and the decision variant is NP-complete). Haven't tried to do anything better than treating it as a monotonic function.

Proof of NP-hardness in the next spoiler.

Proof of NP-hardness:

Let us do a reduction from the following problem, which is almost the subset sum problem:

Given $$$2n$$$ integers, is there a subset of size $$$n$$$ with sum $$$0$$$?

Let the integers be $$$d_1, \ldots, d_{2n}$$$. Compute $$$M = \max{|d_i|} + 1$$$, and map $$$d_i \to (M + d_i, M - d_i)$$$. Having obtained $$$2n$$$ pairs of positive integers, solve the $$$f = x^2 + y^2$$$ minimization problem on them. Notice how any solution $$$(X, Y)$$$ satisfies $$$X + Y = 2nM$$$, and the pair minimizing $$$f$$$ is $$$X = Y = nM$$$.

If a solution $$$(nM, nM)$$$ exists, then it is found by the minimization problem, and it implies a solution to the $$$0$$$ subset sum problem. Similarly, if the original problem has a subset of sum $$$0$$$ with size $$$n$$$, then $$$(nM, nM)$$$ is a possible solution.

Reduction from the well known subset sum problem to the above one: Given $$$a_1, \ldots, a_n$$$, if their sum is $$$0$$$ then there is a solution. Otherwise, if $$$n = 1$$$ there is no solution, else append $$$n - 2$$$ zeros to this sequence. You obtain a sequence of $$$2n - 2$$$ integers, find a subset with sum $$$0$$$ and size $$$n - 1$$$, and obtain a solution to the original subset sum problem.

Nothing really, it just made me very sad that this variant is NP-hard :(

Problems E and F suggest the following criterion on $$$f$$$:

Let $$$f$$$ be a continuous (differentiable?) function in $$$\mathbb{R}^2 \to \mathbb{R}$$$. Consider the problem of the blog, except that all pairs are now pairs of rational numbers (not necessarily positive integers). Then:

• If for all $$$t$$$, the set of points $$$\lbrace f > t \rbrace$$$ is convex, then the problem is solvable in polynomial time — specifically $$$O(n^2 \log n)$$$.
• Otherwise, if there exists $$$t$$$ such that $$$\lbrace f > t \rbrace$$$ is not convex, then the problem is NP-hard.

For the first direction, this should be easy — the solution should lie on the convex hull of all solutions. Take the optimal solution $$$(X, Y)$$$, where $$$f(X, Y) = t$$$, and show that there exists a slope to which $$$(X, Y)$$$ is the minimizing solution (using the fact that $$$\lbrace f > t \rbrace$$$ is convex).

For the second direction, you can take a pair of points $$$p_1, p_2$$$ such that $$$f(p_1), f(p_2) > t$$$ and there is a point $$$q$$$ on the segment connecting $$$p_1, p_2$$$ such that $$$f(q) \leq t$$$. You can use a similar construction in problem F (that forces all solutions to lie on this segment and aim to land near $$$q$$$), and obtain an algorithm that gives a constant-factor approximation to the subset sum / partition problem, but we already know this is achievable.

An example of such a function for which I didn't prove NP-hardness is $$$f(p) = \max (0, 1 - d(p,s)) + \max (0, 1 - d(p,t))$$$, where $$$s = (-10, 0), t = (10, 0)$$$ and $$$d$$$ is euclidean distance.

Any fix or proof of this criterion will be highly appreciated.