D. Suit and Tie

Codeforces

IDCF996D

Time2000ms

Memory256MB

Difficulty—

brute forcegreedymath

English · Original

Chinese · Translation

Formal · Original

Allen is hosting a formal dinner party. $2n$ people come to the event in $n$ pairs (couples). After a night of fun, Allen wants to line everyone up for a final picture. The $2n$ people line up, but Allen doesn't like the ordering. Allen prefers if each pair occupies adjacent positions in the line, as this makes the picture more aesthetic. Help Allen find the minimum number of swaps of **adjacent** positions he must perform to make it so that each couple occupies adjacent positions in the line. ## Input The first line contains a single integer $n$ ($1 \le n \le 100$), the number of pairs of people. The second line contains $2n$ integers $a_1, a_2, \dots, a_{2n}$. For each $i$ with $1 \le i \le n$, $i$ appears exactly twice. If $a_j = a_k = i$, that means that the $j$\-th and $k$\-th people in the line form a couple. ## Output Output a single integer, representing the minimum number of adjacent swaps needed to line the people up so that each pair occupies adjacent positions. [samples] ## Note In the first sample case, we can transform $1 1 2 3 3 2 4 4 \rightarrow 1 1 2 3 2 3 4 4 \rightarrow 1 1 2 2 3 3 4 4$ in two steps. Note that the sequence $1 1 2 3 3 2 4 4 \rightarrow 1 1 3 2 3 2 4 4 \rightarrow 1 1 3 3 2 2 4 4$ also works in the same number of steps. The second sample case already satisfies the constraints; therefore we need $0$ swaps.

Allen 正在举办一场正式的晚宴。$2 n$ 个人以 $n$ 对（情侣）的形式到场。经过一夜的欢乐后，Allen 希望将所有人排成一列拍最后一张照片。$2 n$ 个人排成一列，但 Allen 不喜欢当前的顺序。他更希望每对情侣占据相邻的位置，这样照片会更美观。帮助 Allen 找出他必须执行的最少相邻位置交换次数，使得每对情侣都占据相邻位置。第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$），表示情侣对数。第二行包含 $2 n$ 个整数 $a_1, a_2, dots.h, a_(2 n)$。对于每个满足 $1 lt.eq i lt.eq n$ 的 $i$，数字 $i$ 恰好出现两次。若 $a_j = a_k = i$，则表示排在第 $j$ 位和第 $k$ 位的人是一对情侣。请输出一个整数，表示为使每对情侣占据相邻位置所需执行的最少相邻交换次数。在第一个样例中，我们可以经过两步变换：$11233244 arrow.r 11232344 arrow.r 11223344$。注意，序列 $11233244 arrow.r 11323244 arrow.r 11332244$ 也能在相同步数内完成。第二个样例已经满足条件，因此需要 $0$ 次交换。 ## Input 第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$），表示情侣对数。第二行包含 $2 n$ 个整数 $a_1, a_2, dots.h, a_(2 n)$。对于每个满足 $1 lt.eq i lt.eq n$ 的 $i$，数字 $i$ 恰好出现两次。若 $a_j = a_k = i$，则表示排在第 $j$ 位和第 $k$ 位的人是一对情侣。 ## Output 请输出一个整数，表示为使每对情侣占据相邻位置所需执行的最少相邻交换次数。 [samples] ## Note 在第一个样例中，我们可以经过两步变换：$11233244 arrow.r 11232344 arrow.r 11223344$。注意，序列 $11233244 arrow.r 11323244 arrow.r 11332244$ 也能在相同步数内完成。第二个样例已经满足条件，因此需要 $0$ 次交换。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of couples. Let $ A = (a_1, a_2, \dots, a_{2n}) $ be a sequence of integers where each integer $ i \in \{1, 2, \dots, n\} $ appears exactly twice, representing the couple IDs of the people in line. **Constraints** 1. $ 1 \le n \le 100 $ 2. For each $ i \in \{1, \dots, n\} $, there exist exactly two indices $ j, k \in \{1, \dots, 2n\} $, $ j \ne k $, such that $ a_j = a_k = i $. **Objective** Find the minimum number of adjacent swaps required to transform $ A $ into a sequence $ A' = (a'_1, a'_2, \dots, a'_{2n}) $ such that for every couple $ i \in \{1, \dots, n\} $, the two occurrences of $ i $ are in adjacent positions (i.e., for some $ \ell $, $ a'_\ell = a'_{\ell+1} = i $). Equivalently, partition $ A' $ into $ n $ consecutive blocks of size 2, each containing two identical elements.

Samples

Input #1

4
1 1 2 3 3 2 4 4

Output #1

Input #2

3
1 1 2 2 3 3

Output #2

Input #3

3
3 1 2 3 1 2

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Suit and Tie",
    "description": {
      "content": "Allen is hosting a formal dinner party. $2n$ people come to the event in $n$ pairs (couples). After a night of fun, Allen wants to line everyone up for a final picture. The $2n$ people line up, but Al",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF996D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Allen is hosting a formal dinner party. $2n$ people come to the event in $n$ pairs (couples). After a night of fun, Allen wants to line everyone up for a final picture. The $2n$ people line up, but Al...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Allen 正在举办一场正式的晚宴。$2 n$ 个人以 $n$ 对（情侣）的形式到场。经过一夜的欢乐后，Allen 希望将所有人排成一列拍最后一张照片。$2 n$ 个人排成一列，但 Allen 不喜欢当前的顺序。他更希望每对情侣占据相邻的位置，这样照片会更美观。\n\n帮助 Allen 找出他必须执行的最少相邻位置交换次数，使得每对情侣都占据相邻位置。\n\n第一行包含一个整数 $n$（$1 lt.eq ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of couples.  \nLet $ A = (a_1, a_2, \\dots, a_{2n}) $ be a sequence of integers where each integer $ i \\in \\{1, 2, \\dots, n\\} $ appears exactly t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments