B. Kayaking

Codeforces

IDCF863B

Time2000ms

Memory256MB

Difficulty—

brute forcegreedysortings

English · Original

Chinese · Translation

Formal · Original

Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers. Now the party is ready to start its journey, but firstly they have to choose kayaks. There are 2·_n_ people in the group (including Vadim), and they have exactly _n_ - 1 tandem kayaks (each of which, obviously, can carry two people) and 2 single kayaks. _i_\-th person's weight is _w__i_, and weight is an important matter in kayaking — if the difference between the weights of two people that sit in the same tandem kayak is too large, then it can crash. And, of course, people want to distribute their seats in kayaks in order to minimize the chances that kayaks will crash. Formally, the instability of a single kayak is always 0, and the instability of a tandem kayak is the absolute difference between weights of the people that are in this kayak. Instability of the whole journey is the total instability of all kayaks. Help the party to determine minimum possible total instability! ## Input The first line contains one number _n_ (2 ≤ _n_ ≤ 50). The second line contains 2·_n_ integer numbers _w_1, _w_2, ..., _w_2_n_, where _w__i_ is weight of person _i_ (1 ≤ _w__i_ ≤ 1000). ## Output Print minimum possible total instability. [samples]

Vadim 非常热衷于旅行。最近他听说了家乡附近有皮划艇活动，对此非常兴奋，于是加入了皮划艇团队。现在团队准备启程，但首先需要选择皮划艇。团队共有 #cf_span[2·n] 人（包括 Vadim），他们恰好有 #cf_span[n - 1] 艘双人皮划艇（每艘显然可载两人）和 #cf_span[2] 艘单人皮划艇。第 #cf_span[i] 个人的体重为 #cf_span[wi]，体重在皮划艇活动中非常重要——如果两人同坐一艘双人皮划艇时体重差异过大，皮划艇可能会翻覆。当然，人们希望分配座位，以最小化皮划艇翻覆的可能性。形式上，单人皮划艇的不稳定性始终为 #cf_span[0]，双人皮划艇的不稳定性是其中两人体重的绝对差值。整个旅程的不稳定性是所有皮划艇不稳定性之和。请帮助团队确定可能的最小总不稳定性！第一行包含一个数字 #cf_span[n]（#cf_span[2 ≤ n ≤ 50]）。第二行包含 #cf_span[2·n] 个整数 #cf_span[w1], #cf_span[w2], ..., #cf_span[w2n]，其中 #cf_span[wi] 表示第 #cf_span[i] 个人的体重（#cf_span[1 ≤ wi ≤ 1000]）。请输出可能的最小总不稳定性。 ## Input 第一行包含一个数字 #cf_span[n]（#cf_span[2 ≤ n ≤ 50]）。第二行包含 #cf_span[2·n] 个整数 #cf_span[w1], #cf_span[w2], ..., #cf_span[w2n]，其中 #cf_span[wi] 表示第 #cf_span[i] 个人的体重（#cf_span[1 ≤ wi ≤ 1000]）。 ## Output 请输出可能的最小总不稳定性。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 50 $. Let $ W = (w_1, w_2, \dots, w_{2n}) $ be a sequence of positive integers representing the weights of $ 2n $ people. **Constraints** $ 1 \leq w_i \leq 1000 $ for all $ i \in \{1, \dots, 2n\} $. **Objective** Partition the $ 2n $ people into: - $ n - 1 $ tandem kayaks (each carrying exactly 2 people), - 2 single kayaks (each carrying exactly 1 person). Let $ S \subseteq \{1, \dots, 2n\} $ be the set of indices assigned to single kayaks ($ |S| = 2 $). Let $ T $ be the set of $ n - 1 $ disjoint pairs (tandem kayaks) formed from the remaining $ 2n - 2 $ people. The instability of a tandem kayak with people of weights $ w_i, w_j $ is $ |w_i - w_j| $. The instability of a single kayak is $ 0 $. Minimize the total instability: $$ \min_{\substack{S \subseteq \{1,\dots,2n\} \\ |S| = 2}} \sum_{(i,j) \in T} |w_i - w_j| $$ where $ T $ is a perfect matching of $ \{1,\dots,2n\} \setminus S $.

Samples

Input #1

2
1 2 3 4

Output #1

Input #2

4
1 3 4 6 3 4 100 200

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Kayaking",
    "description": {
      "content": "Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers. Now the party is ready to start its jou",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF863B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers.\n\nNow the party is ready to start its jou...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Vadim 非常热衷于旅行。最近他听说了家乡附近有皮划艇活动，对此非常兴奋，于是加入了皮划艇团队。\n\n现在团队准备启程，但首先需要选择皮划艇。团队共有 #cf_span[2·n] 人（包括 Vadim），他们恰好有 #cf_span[n - 1] 艘双人皮划艇（每艘显然可载两人）和 #cf_span[2] 艘单人皮划艇。第 #cf_span[i] 个人的体重为 #cf_span[wi]，体重在皮划...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 50 $.  \nLet $ W = (w_1, w_2, \\dots, w_{2n}) $ be a sequence of positive integers representing the weights of $ 2n $ people.  \n\n**Constra...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments