D. Two Sequences

Codeforces
IDCF10196D
Time6000ms
Memory256MB
Difficulty
English · Original
Formal · Original
You are given two sequences of integers $A$ and $B$, and an integer $k$. Two sequences are equal if it is possible to rearrange one of the sequences such that each element in the sequence is equal to the corresponding element from the other sequence. You can select one of the elements in sequence $A$, and add to it any integer from the range $[ -k, k ]$. Is it possible to make the two sequences equal by doing the specified operation *exactly* once? The first line of input contains a single integer $T$, the number of test cases. The first line of each case contains two space-separated integers $n$ and $k$ ($1 <= n <= 10^5$)($1 <= k <= 10^9$), the length of each sequence and the number $k$ specified in the problem statement. The next line contains $n$ space-separated integers ($1 <= A_i <= 10^9$), the elements in sequence $A$. The next line contains $n$ space-separated integers ($1 <= B_i <= 10^9$), the elements in sequence $B$. For each test case, output a single line with *YES* if it is possible to make the two sequences equal in a single operation. Otherwise output *NO*. ## Input The first line of input contains a single integer $T$, the number of test cases.The first line of each case contains two space-separated integers $n$ and $k$ ($1 <= n <= 10^5$)($1 <= k <= 10^9$), the length of each sequence and the number $k$ specified in the problem statement.The next line contains $n$ space-separated integers ($1 <= A_i <= 10^9$), the elements in sequence $A$.The next line contains $n$ space-separated integers ($1 <= B_i <= 10^9$), the elements in sequence $B$. ## Output For each test case, output a single line with *YES* if it is possible to make the two sequences equal in a single operation. Otherwise output *NO*. [samples]
**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n \in \mathbb{Z} $ be the length of sequences $ A $ and $ B $. - Let $ k \in \mathbb{Z} $ be the bound on the allowed adjustment. - Let $ A = (a_1, a_2, \dots, a_n) $, $ B = (b_1, b_2, \dots, b_n) $ be sequences of integers. **Constraints** 1. $ 1 \le T \le \text{unspecified} $ 2. $ 1 \le n \le 10^5 $ 3. $ 1 \le k \le 10^9 $ 4. $ 1 \le a_i, b_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Determine whether there exists an index $ j \in \{1, \dots, n\} $ and an integer $ d \in [-k, k] $ such that, after setting $ a_j \leftarrow a_j + d $, the multiset $ A $ becomes equal to the multiset $ B $. That is, define $ A' = (a_1, \dots, a_{j-1}, a_j + d, a_{j+1}, \dots, a_n) $. Check if there exists $ j $ and $ d \in [-k, k] $ such that $ \text{multiset}(A') = \text{multiset}(B) $.
API Response (JSON)
{
  "problem": {
    "name": "D. Two Sequences",
    "description": {
      "content": "You are given two sequences of integers $A$ and $B$, and an integer $k$. Two sequences are equal if it is possible to rearrange one of the sequences such that each element in the sequence is equal to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10196D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two sequences of integers $A$ and $B$, and an integer $k$.\n\nTwo sequences are equal if it is possible to rearrange one of the sequences such that each element in the sequence is equal to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the length of sequences $ A $ and $ B $.  \n- Let $ k \\in \\mathbb{Z} $ be t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments