G. Coin Game

Codeforces

IDCF10053G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that's why they feel bored again and again. They just invented a new game, as they usually did. They are playing with coins. They have a row of $1 and $2 coins. They want to change this row so that all $1's are grouped together and all $2's are grouped together. They are just allowed to swap two neighbor coins. Using the best strategy what is the minimum number of swaps required to do this task? Each test case is a line with a string composed of 1 and 2. (1 ≤ length of the input string ≤ 25000) Print the minimum number of swaps required to do this task. ## Input Each test case is a line with a string composed of 1 and 2. (1 ≤ length of the input string ≤ 25000) ## Output Print the minimum number of swaps required to do this task. [samples]

**Definitions** Let $ s \in \{1, 2\}^* $ be a string of length $ n $, representing a sequence of coins of denomination 1 or 2. **Constraints** $ 1 \leq n \leq 25000 $ **Objective** Compute the minimum number of adjacent swaps required to group all 1s together and all 2s together (i.e., to obtain a string of the form $ 1^*2^* $ or $ 2^*1^* $). Let $ c_1 $ be the number of 1s in $ s $, and $ c_2 = n - c_1 $ the number of 2s. The target configurations are: - $ 1^{c_1}2^{c_2} $ - $ 2^{c_2}1^{c_1} $ Define: - $ S_1 $: minimum adjacent swaps to transform $ s $ into $ 1^{c_1}2^{c_2} $ - $ S_2 $: minimum adjacent swaps to transform $ s $ into $ 2^{c_2}1^{c_1} $ Then the answer is: $$ \min(S_1, S_2) $$ Where: - $ S_1 = \sum_{i: s_i = 2} \left( \text{number of 1s to the left of position } i \right) $ - $ S_2 = \sum_{i: s_i = 1} \left( \text{number of 2s to the left of position } i \right) $

API Response (JSON)

{
  "problem": {
    "name": "G. Coin Game",
    "description": {
      "content": "Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that's why they feel bored again ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10053G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob are very smart guys and they like to play all kinds of games in their spare time. The most amazing thing is that they always find the best strategy, and that's why they feel bored again ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{1, 2\\}^* $ be a string of length $ n $, representing a sequence of coins of denomination 1 or 2.\n\n**Constraints**  \n$ 1 \\leq n \\leq 25000 $\n\n**Objective**  \nCompute the...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments