C. Changing Game

Codeforces

IDCF10286C

Time5000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Welcome to _Changing Game_! In this game, you are given an integer array $A$ of $n$ *distinct* values $a_1, a_2, \\\\cdots, a_n$. You are allowed to do some operations on array $A$. In each operation you can select an element from $A$ and replace it with an integer $c$. Note that you need to keep all elements of $A$ distinct after each operation. Now, you are given an integer array $B = [ b_1, b_2, \\\\cdots, b_n ]$ which derives from $A$ through some number of operations by Master Yi. Could you restore the operation sequence performed by Master Yi that produces $B$ from $A$? It sounds too easy to do this job. In order to increase the difficulty of this problem, Master Yi recommended that you need to find the most optimal one. In other words, you should find the minumum number of operation(s) that produces $B$ from $A$. You need to process $t$ test cases. The first line contains an integer $t " "(1 <= t <= 100)$ — the number of test cases. Then descriptions of $t$ test cases follow. It is guaranteed that the sum of the length $n$ for all test cases does not exceed $2 " "000 " "000$. For each test case, you should print several lines as follow. If there are multiple answers, you can print any of them. ## Input You need to process $t$ test cases.The first line contains an integer $t " "(1 <= t <= 100)$ — the number of test cases. Then descriptions of $t$ test cases follow. The first line of each test case contains one integer $n " "(1 <= n <= 100 " "000)$ — the length of the given arrays $A$ and $B$. The second line contains $n$ integers $a_1, a_2 \\\\cdots, a_n " "(1 <= a_i <= 1 " "000 " "000 " "000)$ — the elements of array $A$ in order. It's guaranteed that all elements in $A$ are distinct. The third line contains $n$ integers $b_1, b_2, \\\\cdots, b_n " "(1 <= b_i <= 1 " "000 " "000 " "000)$ — the elements of array $B$ in order. It's guaranteed that all elements in $B$ are distinct. It is guaranteed that the sum of the length $n$ for all test cases does not exceed $2 " "000 " "000$. ## Output For each test case, you should print several lines as follow. The first line of each test case should contain one integer $m$ — the the minimum number of operation(s). Then the next $m$ line(s), each line should contain $2$ integers $p " "(1 <= p <= n)$ and $c " "(1 <= c <= 1 " "000 " "000 " "000)$ — to choose the position $p_i$ to modify $a_{p_i} arrow.l c_i$ in $i$-th operation. If there are multiple answers, you can print any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of rooms. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the number of devices in room $ i $. Let $ f: \mathbb{N}_0 \to \mathbb{R} $ be a recursive function (unspecified form, but fixed and deterministic). Let $ P = (p_1, p_2, \dots, p_n) $, where $ p_i = f(a_i) $, be the power requirement for each room. **Constraints** 1. $ 1 \le n \le 10^4 $ 2. $ 0 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the number of unordered pairs $ \{i, j\} $ with $ i < j $ such that $ p_i = p_j $. That is, compute: $$ \sum_{\substack{1 \le i < j \le n \\ p_i = p_j}} 1 $$

API Response (JSON)

{
  "problem": {
    "name": "C. Changing Game",
    "description": {
      "content": "Welcome to _Changing Game_! In this game, you are given an integer array $A$ of $n$ *distinct* values $a_1, a_2, \\\\\\\\cdots, a_n$. You are allowed to do some operations on array $A$. In each operation",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10286C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Welcome to _Changing Game_! In this game, you are given an integer array $A$ of $n$ *distinct* values $a_1, a_2, \\\\\\\\cdots, a_n$.\n\nYou are allowed to do some operations on array $A$. In each operation...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of rooms.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the number of devices in room $ i $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments