I've spent some time on the following problem, which is quite generic (and is similar to many well-known problems):

You are given $$$2n$$$ pairs of integers $$$(x_i, y_i)$$$, where $$$1 \leq x_i, y_i \leq M$$$. Your goal is to choose exactly $$$n$$$ of them, such that their pointwise sum $$$(X, Y)$$$ (that is, you sum each coordinate on its own), minimizes the cost function $$$f(X, Y)$$$. What is the best time complexity you can achieve, given some properties about the function $$$f$$$?

Since the time complexity can depend on both $$$n$$$ and $$$M$$$, the order in which the best complexity is determined is:

Polynomial in $$$n$$$ and in $$$\log M$$$.

Polynomial in $$$n$$$ and in $$$M$$$.

$$$O(\binom{2n}{n})$$$ (applicable to all of them).

Try to solve each of the following variations, with varying difficulties. **This post is purposed for all levels**, and I'll try to write solutions that can be understood by all levels (except maybe for the advanced problems).

I'm interested to know if you have any other variations with interesting insights that I can add to here, as I find this topic quite interesting to research.

Problem A. $$$f(X,Y) = X + Y$$$

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

Problem B. $$$f$$$ can be any function

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

Problem C. $$$f$$$ is monotonic: for each pair of pairs $$$(x_1,y_1), (x_2, y_2)$$$ such that $$$x_1 \leq x_2$$$ and $$$y_1 \leq y_2$$$, you have $$$f(x_1, y_1) \leq f(x_2, y_2)$$$.

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

Problem D. $$$f(x,y) = \frac{x}{y}$$$

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

Problem E. $$$f(x,y) = xy$$$

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

Problem F. $$$f(x,y) = x^2 + y^2$$$

**Solution complexity**

**Solution**

**Extra notes (don't read before solution)**

**Problem G. Open after reading the solutions to E and F**