logoChat01.ai

Given two multisets S and T of size n and a pos...

Created on: August 10, 2025

Answered using GPT-5 Thinking by Chat01

Question

Given two multisets S
and T
of size n
and a positive integer k
, you may perform the following operations any number (including zero) of times on S
:

Select an element x
in S
, and remove one occurrence of x
in S
. Then, either insert x+k
into S
, or insert |x−k|
into S
.
Determine if it is possible to make S
equal to T
. Two multisets S
and T
are equal if every element appears the same number of times in S
and T
.

Input
Each test contains multiple test cases. The first line contains an integer t
(1≤t≤104
) — the number of test cases. The description of the test cases follows.

The first line contains two integers n
and k
(1≤n≤2⋅105
, 1≤k≤109
) — the size of S
and the constant, respectively.

The second line contains n
integers S1,S2,…,Sn
(0≤Si≤109
) — the elements in S
.

The third line contains n
integers T1,T2,…,Tn
(0≤Ti≤109
) — the elements in T
.

It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105
.

Output
For each test case, output "YES" if it is possible to make S
equal to T
, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
InputCopy
5
1 3
1
2
1 8
4
12
3 5
6 2 9
8 4 11
2 7
2 8
2 9
3 2
0 1 0
1 0 1
OutputCopy
YES
YES
YES
NO
NO
Note
In the first test case, we can remove one occurrence of 1
from S
and insert |1−k|=|1−3|=2
into S
, making S
equal to T
.

In the second test case, we can remove one occurrence of 4
from S
and insert 4+k=4+8=12
into S
, making S
equal to T
.

In the last test case, we can show that it is impossible to make S
equal to T
.

code in java
I think it will have a easy solution

Thought

Investigating transformations in multiset

I’m trying to figure out whether we can transform multiset S to set T using allowed operations. The operation lets us add or subtract k, but when x < k, we flip it to k - x. I’m comparing residues modulo k — adding k doesn't change the residue, but subtracting does if x >= k, or transforms it otherwise.

Exploring residue transformations

Residues flip from r to -r modulo k, and we can flip the value back by adding or subtracting k. If x < k, the result flips and stays within k, but adding k doesn’t change the residue. After some transformations, each value x can turn into either r or -r modulo k, and magnitude can grow or shrink based on operations.

Transforming multiset conditions

When x ≥ k, subtracting k reduces the value. For x < k, we get k - x, which might be larger than x unless x > k/2. Residues flip, but they can’t be decreased further, except by switching to their complement (k - x). Operations revolve around residues mod k, with special cases for 0 and k/2.

Residue transformations and limits

We can increase a value by multiples of k but can’t reduce it below the minimal value in its residue class. For a residue r, we can reach the minimal value by repeatedly subtracting k if x >= r. The |x - k| operation flips residues, but can’t lead directly to a different residue.

Residue transformation criteria

Given a residue r, you can use transformations to change numbers between their corresponding residue pairs, r and k - r. The key condition for a successful transformation is matching the count of numbers in those residue classes between two sets, S and T. This approach works by adjusting through multiples of k, ensuring values match in "residue pair" counts.

Optimizing residue comparison for large k

To compare residue frequencies between two sets, I’ll iterate over unique residues from both sets without needing to traverse all values up to k. The key is to check pairs of residues that are related by transformation within a specific range. This helps avoid inefficient computation while ensuring count accuracy.

Explaining solution implementation

The crux of the solution involves matching residues from two sets, taking into account the modulo arithmetic for both. We pair residues from S and T carefully to verify equality in their counts. The key observation is that residues can only flip within specific pairs, and we handle edge cases, such as k = 1, seamlessly.

Thought for 1m 24s

Answer

You're right — there’s a clean invariant here.

Observation: each move keeps an element’s residue modulo k, except it can flip r to k−r (because |x−k| turns residue r into k−r).
So each number can only move within its pair of residues {r, k−r}. Special residues 0 (and k/2 when k is even) are fixed to themselves.

Therefore, S can become T iff for every residue-pair {r, k−r} the total count of elements of S in that pair equals the total count in T (and for 0 and possibly k/2 the counts match exactly).

Here’s an O(n) Java solution using that idea:

java
import java.io.*;
import java.util.*;

public class Main {
    // Fast input
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do { c = read(); } while (c <= ' '); // skip spaces
            long sgn = 1;
            if (c == '-') { sgn = -1; c = read(); }
            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sgn;
        }

        int nextInt() throws IOException { return (int) nextLong(); }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();
        int t = fs.nextInt();

        while (t-- > 0) {
            int n = fs.nextInt();
            long k = fs.nextLong(); // k >= 1

            HashMap<Long, Integer> freqS = new HashMap<>(n * 2);
            HashMap<Long, Integer> freqT = new HashMap<>(n * 2);

            for (int i = 0; i < n; i++) {
                long v = fs.nextLong();
                long r = v % k; // 0 <= r < k
                freqS.merge(r, 1, Integer::sum);
            }
            for (int i = 0; i < n; i++) {
                long v = fs.nextLong();
                long r = v % k;
                freqT.merge(r, 1, Integer::sum);
            }

            // Collect unique residue-pair "bases" (min(r, k - r))
            HashSet<Long> bases = new HashSet<>();
            for (Long r : freqS.keySet()) {
                long other = (k - r) % k; // for r=0 -> 0
                long base = Math.min(r, other);
                bases.add(base);
            }
            for (Long r : freqT.keySet()) {
                long other = (k - r) % k;
                long base = Math.min(r, other);
                bases.add(base);
            }

            boolean ok = true;
            for (Long base : bases) {
                long r1 = base;
                long r2 = (k - base) % k; // partner residue (could equal r1)
                int cs = freqS.getOrDefault(r1, 0) + (r1 == r2 ? 0 : freqS.getOrDefault(r2, 0));
                int ct = freqT.getOrDefault(r1, 0) + (r1 == r2 ? 0 : freqT.getOrDefault(r2, 0));
                if (cs != ct) { ok = false; break; }
            }

            out.append(ok ? "YES\n" : "NO\n");
        }

        System.out.print(out.toString());
    }
}

Why this works:

  • You can freely move within residue-pair {r, k−r} by subtracting/adding k and doing the < k flip via |x−k|.
  • You cannot escape that pair (and for r=0 or r=k/2 you can’t even flip), so matching total counts per pair is both necessary and sufficient.

Share this Q&A