I. Хаотичные плюмбусы

Codeforces

IDCF10218I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Пока Рик в очередной раз спасал вселенную исключительно в своих интересах, Морти нашел в гараже набор разноцветных плюмбусов, развешенных на веревке. Морти знает, что если плюмбусы разных цветов висят рядом, то они быстрее портятся, поэтому он решил минимизировать ущерб, то есть перевесить плюмбусы так, чтобы они были сгруппированы по цветам. Всего на веревке $N times K$ плюмбусов: по $N$ штук каждого из $K$ цветов. За одну секунду Морти может снять любой плюмбус и повесить его с левого или с правого края веревки, то есть левее или правее всех остальных. Морти хочет получить такое расположение плюмбусов, при котором все плюмбусы одного цвета формируют ровно одну последовательную группу. В итоге на веревке будет $K$ таких групп. Последовательность групп при этом не имеет значения. Определите, какое минимальное количество времени потребуется Морти, чтобы достичь своей цели. В первой строке задано два целых числа $N$ и $K$ — количество плюмбусов каждого цвета и количество цветов соответственно ($1 <= N, K <= 1000$). Во второй строке задано $N times K$ чисел — начальное расположение плюмбусов, в котором каждое число $A_i$ обозначает цвет плюмбуса номер $i$ ($1 <= A_i <= K$). В связи с большим объемом входных данных рекомендуется использовать эффективные методы ввода (например, scanf в C++). Необходимо вывести одно число — минимальное количество секунд, которое потребуется Морти для группировки плюмбусов описанным образом. На рисунке изображен первый пример. Оптимальный алгоритм группировки для этого примера может выглядеть так: перевесить два плюмбуса цвета $1$ из середины влево и два плюмбуса цвета $3$ из середины вправо. ## Входные Данные В первой строке задано два целых числа $N$ и $K$ — количество плюмбусов каждого цвета и количество цветов соответственно ($1 <= N, K <= 1000$).Во второй строке задано $N times K$ чисел — начальное расположение плюмбусов, в котором каждое число $A_i$ обозначает цвет плюмбуса номер $i$ ($1 <= A_i <= K$).В связи с большим объемом входных данных рекомендуется использовать эффективные методы ввода (например, scanf в C++). ## Выходные Данные Необходимо вывести одно число — минимальное количество секунд, которое потребуется Морти для группировки плюмбусов описанным образом. ## Примеры Входные данные3 31 2 3 3 2 1 1 2 3Выходные данные4Входные данные2 43 3 1 1 4 4 2 2Выходные данные0 ## Примечание На рисунке изображен первый пример. Оптимальный алгоритм группировки для этого примера может выглядеть так: перевесить два плюмбуса цвета $1$ из середины влево и два плюмбуса цвета $3$ из середины вправо. [samples]

**Definitions** Let $N, K \in \mathbb{Z}^+$ with $1 \leq N, K \leq 1000$. Let $A = (a_1, a_2, \dots, a_{NK})$ be a sequence of colors, where $a_i \in \{1, 2, \dots, K\}$, and each color $c \in \{1, \dots, K\}$ appears exactly $N$ times. **Constraints** Each color $c \in \{1, \dots, K\}$ occurs exactly $N$ times in $A$. **Objective** Find the minimum number of moves required to rearrange $A$ into a configuration where all occurrences of each color form a single contiguous block (i.e., the sequence is partitioned into $K$ contiguous segments, each consisting of $N$ identical colors), using only moves that place any element at either the leftmost or rightmost position. Equivalently, minimize the number of elements that are **not** already in their final relative order within some permutation of contiguous color blocks — i.e., maximize the length of the longest subsequence of $A$ that is a concatenation of $N$ copies of each color in some fixed order (one block per color), and then compute: $$ \text{Minimum moves} = NK - \max_{\sigma \in S_K} \left( \text{length of longest subsequence of } A \text{ matching } \underbrace{\sigma(1)\dots\sigma(1)}_{N}\underbrace{\sigma(2)\dots\sigma(2)}_{N}\dots\underbrace{\sigma(K)\dots\sigma(K)}_{N} \right) $$

API Response (JSON)

{
  "problem": {
    "name": "I. Хаотичные плюмбусы",
    "description": {
      "content": "Пока Рик в очередной раз спасал вселенную исключительно в своих интересах, Морти нашел в гараже набор разноцветных плюмбусов, развешенных на веревке. Морти знает, что если плюмбусы разных цветов вися",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10218I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Пока Рик в очередной раз спасал вселенную исключительно в своих интересах, Морти нашел в гараже набор разноцветных плюмбусов, развешенных на веревке.\n\nМорти знает, что если плюмбусы разных цветов вися...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $N, K \\in \\mathbb{Z}^+$ with $1 \\leq N, K \\leq 1000$.  \nLet $A = (a_1, a_2, \\dots, a_{NK})$ be a sequence of colors, where $a_i \\in \\{1, 2, \\dots, K\\}$, and each color $c \\in \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments