G. Getting Confidence

Codeforces
IDCF10234G
Time1000ms
Memory256MB
Difficulty
English · Original
Formal · Original
The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf [samples]
**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of strings $ s $ and $ t $. Let $ s, t \in \{a, b\}^n $ be two strings of equal length consisting of characters 'a' and 'b'. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $ 2. $ s, t $ contain only characters 'a' and 'b'. **Objective** Determine the minimum number of operations to make $ s = t $, where each operation consists of swapping $ s[i] $ with $ t[j] $ for any indices $ i, j \in \{1, \dots, n\} $. Define the set of mismatched positions: $$ D = \{ i \in \{1, \dots, n\} \mid s[i] \ne t[i] \} $$ For each $ i \in D $, define the pair $ (s[i], t[i]) \in \{ (a,b), (b,a) \} $. Let: - $ d_{ab} = |\{ i \in D \mid s[i] = a, t[i] = b \}| $ - $ d_{ba} = |\{ i \in D \mid s[i] = b, t[i] = a \}| $ **Feasibility Condition** It is possible to make $ s = t $ if and only if $ d_{ab} + d_{ba} $ is even. **Objective Function** If feasible, the minimum number of operations is: $$ k = \left\lceil \frac{d_{ab}}{2} \right\rceil + \left\lceil \frac{d_{ba}}{2} \right\rceil $$ **Output** - If $ d_{ab} + d_{ba} $ is odd, output $-1$. - Otherwise, output $ k $, followed by $ k $ pairs $ (i, j) $ representing swaps between $ s[i] $ and $ t[j] $ that achieve equality.
API Response (JSON)
{
  "problem": {
    "name": "G. Getting Confidence",
    "description": {
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10234G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The complete problemset is available on http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf\n\n[samples]...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of strings $ s $ and $ t $.  \nLet $ s, t \\in \\{a, b\\}^n $ be two strings of equal length consisting of characters 'a' and 'b'.  \n\n**Constrain...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments