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