{"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**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ s, t $ contain only characters 'a' and 'b'.  \n\n**Objective**  \nDetermine 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\\} $.  \n\nDefine the set of mismatched positions:  \n$$ D = \\{ i \\in \\{1, \\dots, n\\} \\mid s[i] \\ne t[i] \\} $$  \n\nFor each $ i \\in D $, define the pair $ (s[i], t[i]) \\in \\{ (a,b), (b,a) \\} $.  \nLet:  \n- $ d_{ab} = |\\{ i \\in D \\mid s[i] = a, t[i] = b \\}| $  \n- $ d_{ba} = |\\{ i \\in D \\mid s[i] = b, t[i] = a \\}| $  \n\n**Feasibility Condition**  \nIt is possible to make $ s = t $ if and only if $ d_{ab} + d_{ba} $ is even.  \n\n**Objective Function**  \nIf feasible, the minimum number of operations is:  \n$$ k = \\left\\lceil \\frac{d_{ab}}{2} \\right\\rceil + \\left\\lceil \\frac{d_{ba}}{2} \\right\\rceil $$  \n\n**Output**  \n- If $ d_{ab} + d_{ba} $ is odd, output $-1$.  \n- Otherwise, output $ k $, followed by $ k $ pairs $ (i, j) $ representing swaps between $ s[i] $ and $ t[j] $ that achieve equality.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10234G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}