Can You Solve the Following Minimization Problems?

Правка en8, от Noam527, 2024-05-03 19:22:12

I've spent some time on the following problem, which is quite generic:

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

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

Solution complexity
Solution
Extra notes (don't read before solution)

Problem D. $$$text$$$

Solution complexity
Solution
Extra notes (don't read before solution)

Problem E. $$$text$$$

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)