E. Googles wants to maximize

Codeforces

IDCF10240E

Time8000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Diego and Googles are playing a game, in this game there are exactly $2 * N$ numbers laid out around a circle such that for every position $i$, the numbers with positions $i + 1 mod 2 * N$ and $i -1 mod 2 * N$ are beside it. In this game first is Diego's turn, he will grab exactly $N$ consecutive numbers and then is Googles' turn, he will grab the remaining $N$ numbers. Then both of them sum all the numbers they grabbed and whoever has the biggest number will win. Googles immediately realized that if Diego plays perfectly there is no way for Googles to win, in the best case scenario they can tie. Therefore Googles asked Diego if he can reorder the numbers however he wants before Diego's turn, and he agreed. Now, given $2 * N$ numbers, what you have to do is find a permutation such that if Diego plays perfectly Googles can obtain the maximum amount of points possible. An integer $N$ $(1 <= N <= 6)$, there are exactly $2 * N$ numbers. Followed by a line with $2 * N$ positive integer numbers, each smaller or equal to 1 million. $2 * N$ numbers in a single line (separated by a single space), a permutation of the original $2 * N$ numbers such that it doesn't matter what Diego does Googles' score is maximized. If there are several possible solutions, print any of them. In the first case the maximum Diego can get given the permutation is $1456$ which means that Googles can get $1445$. ## Input An integer $N$ $(1 <= N <= 6)$, there are exactly $2 * N$ numbers.Followed by a line with $2 * N$ positive integer numbers, each smaller or equal to 1 million. ## Output $2 * N$ numbers in a single line (separated by a single space), a permutation of the original $2 * N$ numbers such that it doesn't matter what Diego does Googles' score is maximized. If there are several possible solutions, print any of them. [samples] ## Note In the first case the maximum Diego can get given the permutation is $1456$ which means that Googles can get $1445$.

**Definitions** Let $ N \in \mathbb{Z} $ with $ 1 \leq N \leq 6 $. Let $ A = (a_1, a_2, \dots, a_{2N}) $ be a multiset of $ 2N $ positive integers. Let $ P = (p_1, p_2, \dots, p_{2N}) $ be a cyclic permutation of $ A $ arranged around a circle, where position $ i $ is adjacent to $ i+1 \mod 2N $ and $ i-1 \mod 2N $. **Constraints** Diego selects $ N $ consecutive elements in the circle (contiguous arc). Googles receives the remaining $ N $ consecutive elements (the complementary arc). Diego chooses his arc to maximize his sum; Googles aims to maximize his *minimum possible* sum under optimal play by Diego. **Objective** Find a cyclic permutation $ P $ of $ A $ such that: $$ \max_{\text{Diego's choice}} \left( \sum_{i \in D} p_i \right) = S_{\text{max}} \quad \text{and} \quad S_{\text{Googles}} = \left( \sum_{j=1}^{2N} a_j \right) - S_{\text{max}} $$ is **maximized**, i.e., minimize the maximum sum Diego can achieve. Equivalently: $$ \min_{P \in \text{Perms}(A)} \left( \max_{k=1}^{2N} \sum_{i=k}^{k+N-1 \mod 2N} p_i \right) $$ Output any such optimal permutation $ P $.

API Response (JSON)

{
  "problem": {
    "name": "E. Googles wants to maximize",
    "description": {
      "content": "Diego and Googles are playing a game, in this game there are exactly $2 * N$ numbers laid out around a circle such that for every position $i$, the numbers with positions $i + 1 mod 2 * N$ and $i -1 m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10240E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Diego and Googles are playing a game, in this game there are exactly $2 * N$ numbers laid out around a circle such that for every position $i$, the numbers with positions $i + 1 mod 2 * N$ and $i -1 m...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 6 $.  \nLet $ A = (a_1, a_2, \\dots, a_{2N}) $ be a multiset of $ 2N $ positive integers.  \nLet $ P = (p_1, p_2, \\dots, p_{2N}) $ be a cyc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments