D1. Prefix XOR Problem(Easy Version)

Codeforces
IDCFD1
Time1000ms
Memory256MB
Difficulty
English · Original
Chinese · Translation
Formal · Original
*This is the easy version of this problem.The only difference is that you can perform at most $3 n$ operations.* You are given two binary strings $a$ and $b$ of the same length $n$. You can perform the following operation: Output any scheme to transform $a$ into $b$ by performing at most $3 n$ operations.If there's no such scheme,output $-1$ instead. The first line of the input contains a single integer $t$ ($1 <= t <= 10^4$) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 <= n <= 2 dot.op 10^5$). The second line contains the binary string $a$ of length $n$. The third line contains the binary string $b$ of length $n$. The sum of $n$ over all test cases does not exceed $2 dot.op 10^5$. For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$. Otherwise, output $2$ lines. The first line should contain a single integer $m$ ($0 <= m <= 3 dot.op n$) — the number of operations. The second line should contain $m$ integers ($1 <= i_1, i_2, \\dots, i_m <= n$) — indices defining the operations. It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $3 dot.op n$ operations. ## Input The first line of the input contains a single integer $t$ ($1 <= t <= 10^4$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $n$ ($1 <= n <= 2 dot.op 10^5$).The second line contains the binary string $a$ of length $n$.The third line contains the binary string $b$ of length $n$.The sum of $n$ over all test cases does not exceed $2 dot.op 10^5$. ## Output For each test case, if it is impossible to transform $a$ into $b$ by performing such operations, output $-1$.Otherwise, output $2$ lines.The first line should contain a single integer $m$ ($0 <= m <= 3 dot.op n$) — the number of operations.The second line should contain $m$ integers ($1 <= i_1, i_2, \\dots, i_m <= n$) — indices defining the operations.It is guaranteed that if there is a way to transform $a$ into $b$, then it can be done in at most $3 dot.op n$ operations. [samples]
*这是本题的简单版本,唯一的区别是你可以执行至多 $3n$ 次操作。* 给你两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。 你可以执行以下操作: 请输出一种方案,通过执行至多 $3n$ 次操作将 $a$ 转换为 $b$。如果不存在这样的方案,请输出 $-1$。 输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$)。 第二行包含长度为 $n$ 的二进制字符串 $a$。 第三行包含长度为 $n$ 的二进制字符串 $b$。 所有测试用例中 $n$ 的总和不超过 $2 dot.op 10^5$。 对于每个测试用例,如果无法通过上述操作将 $a$ 转换为 $b$,则输出 $-1$。 否则,输出两行。 第一行应包含一个整数 $m$ ($0 lt.eq m lt.eq 3 dot.op n$) —— 操作的次数。 第二行应包含 $m$ 个整数 ($1 lt.eq i_1, i_2, dots.h, i_m lt.eq n$) —— 定义操作的索引。 保证如果存在将 $a$ 转换为 $b$ 的方法,则可以在至多 $3 dot.op n$ 次操作内完成。 ## Input 输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试用例的描述。每个测试用例的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$)。第二行包含长度为 $n$ 的二进制字符串 $a$。第三行包含长度为 $n$ 的二进制字符串 $b$。所有测试用例中 $n$ 的总和不超过 $2 dot.op 10^5$。 ## Output 对于每个测试用例,如果无法通过上述操作将 $a$ 转换为 $b$,则输出 $-1$。否则,输出两行。第一行应包含一个整数 $m$ ($0 lt.eq m lt.eq 3 dot.op n$) —— 操作的次数。第二行应包含 $m$ 个整数 ($1 lt.eq i_1, i_2, dots.h, i_m lt.eq n$) —— 定义操作的索引。保证如果存在将 $a$ 转换为 $b$ 的方法,则可以在至多 $3 dot.op n$ 次操作内完成。 [samples]
**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. Let $ T = \{(n_k, a_k, b_k) \mid k \in \{1, \dots, t\}\} $ be the set of test cases, where for each $ k $: - $ n_k \in \mathbb{Z} $ is the length of binary strings. - $ a_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) \in \{0,1\}^{n_k} $ is the source binary string. - $ b_k = (b_{k,1}, b_{k,2}, \dots, b_{k,n_k}) \in \{0,1\}^{n_k} $ is the target binary string. **Operation** An operation at index $ i $ ($1 \le i \le n$) flips all bits in the prefix of length $ i $: $$ a_{k,j} \leftarrow 1 - a_{k,j} \quad \text{for all } j \in \{1, \dots, i\} $$ **Constraints** 1. $ 1 \le t \le 10^4 $ 2. $ 1 \le n_k \le 2 \cdot 10^5 $ for each test case 3. $ \sum_{k=1}^t n_k \le 2 \cdot 10^5 $ 4. Each operation index $ i_j \in \{1, \dots, n_k\} $ 5. Total number of operations $ m \le 3 n_k $ **Objective** For each test case $ k $: - If $ a_k $ cannot be transformed into $ b_k $ using any sequence of operations, output $ -1 $. - Otherwise, output a sequence of $ m $ operations $ (i_1, i_2, \dots, i_m) $ such that applying them in order transforms $ a_k $ into $ b_k $, with $ 0 \le m \le 3 n_k $.
API Response (JSON)
{
  "problem": {
    "name": "D1. Prefix XOR Problem(Easy Version)",
    "description": {
      "content": "*This is the easy version of this problem.The only difference is that you can perform at most $3 n$ operations.* You are given two binary strings $a$ and $b$ of the same length $n$. You can perform ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CFD1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "*This is the easy version of this problem.The only difference is that you can perform at most $3 n$ operations.*\n\nYou are given two binary strings $a$ and $b$ of the same length $n$.\n\nYou can perform ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "*这是本题的简单版本,唯一的区别是你可以执行至多 $3n$ 次操作。*\n\n给你两个长度均为 $n$ 的二进制字符串 $a$ 和 $b$。\n\n你可以执行以下操作:\n\n请输出一种方案,通过执行至多 $3n$ 次操作将 $a$ 转换为 $b$。如果不存在这样的方案,请输出 $-1$。\n\n输入的第一行包含一个整数 $t$ ($1 lt.eq t lt.eq 10^4$) —— 测试用例的数量。接下来是测试...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ T = \\{(n_k, a_k, b_k) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of test cases, where for each $ k $:  \n- $ n_k \\in \\math...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments