$$$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))$$$.

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