Can You Solve the Following Minimization Problems?

Правка en11, от Noam527, 2024-05-04 19:17:43

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:

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

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

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский Noam527 2024-05-04 19:57:57 3091 Tiny change: '$\alpha = X, \beta = Y$ but this' -> '$\alpha = Y, \beta = X$ but this' (published)
en11 Английский Noam527 2024-05-04 19:17:43 4558 Tiny change: '$O(n \log nM)$.\n</spo' -> '$O(n \log (nM))$.\n</spo'
en10 Английский Noam527 2024-05-03 21:59:44 149
en9 Английский Noam527 2024-05-03 19:50:37 2049 Tiny change: '1 \leq x_2, y_1 \leq y' -> '1 \leq x_2$ and $y_1 \leq y'
en8 Английский Noam527 2024-05-03 19:22:12 3 Tiny change: 'ze $dp[0][*][*][*] = 0$, e' -> 'ze $dp[0][\*][\*][\*] = 0$, e'
en7 Английский Noam527 2024-05-03 19:21:35 71
en6 Английский Noam527 2024-05-03 19:16:37 475 Tiny change: 'on">\n####$O(n^4' -> 'on">\n######$O(n^4'
en5 Английский Noam527 2024-05-03 18:59:54 119
en4 Английский Noam527 2024-05-03 18:49:04 438
en3 Английский Noam527 2024-05-03 18:45:34 1257
en2 Английский Noam527 2024-05-03 18:31:17 1717 Tiny change: 'n $\log M$' -> 'n $\log M$.\n\n2. Polynomial in $n$ and in $M$.'
en1 Английский Noam527 2024-05-03 18:16:06 450 Initial revision (saved to drafts)