logoChat01.ai

You're given an array a of length n . For each in...

Создано: 10 августа 2025 г.

Отвечено с использованием GPT-5 Thinking от Chat01

Вопрос

You're given an array a
of length n
. For each index i
such that 1≤i<n
, you can perform the following operation at most once:

Assign ai:=ai⊕ai+1
, where ⊕
denotes the bitwise XOR operation. .
You can choose indices and perform the operations in any sequential order.

Given another array b
of length n
, determine if it is possible to transform a
to b
.

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

The first line of each test case contains one integer n
(2≤n≤2⋅105
).

The second line of each test case contains n
integers a1,a2,…,an
(0≤ai<230
).

The third line of each test case contains n
integers b1,b2,…,bn
(0≤bi<230
).

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

Output
For each test case, output "YES" (quotes excluded) if a
can be transformed to b
; otherwise, output "NO". 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
7
5
1 2 3 4 5
3 2 7 1 5
3
0 0 1
1 0 1
3
0 0 1
0 0 0
4
0 0 1 2
1 3 3 2
6
1 1 4 5 1 4
0 5 4 5 5 4
3
0 1 2
2 3 2
2
10 10
11 10
OutputCopy
YES
NO
NO
NO
YES
NO
NO
Note
In the first test case, you can perform the operations in the following order:

Choose index i=3
and assign a3:=a3⊕a4=7
, and a
becomes [1,2,7,4,5]
.
Choose index i=4
and assign a4:=a4⊕a5=1
, and a
becomes [1,2,7,1,5]
.
Choose index i=1
and assign a1:=a1⊕a2=3
, and a
becomes [3,2,7,1,5]
.

code in java

Python

python
from itertools import permutations, product

def reachable(a):
    n=len(a)
    ops=list(range(n-1))
    res=set()
    res.add(tuple(a))
    # For each subset of ops, apply in all orders
    from itertools import combinations
    for mask in range(1<< (n-1)):
        idx=[i for i in range(n-1) if mask>>i &1]
        for order in permutations(idx):
            arr=a.copy()
            for i in order:
                arr[i]=arr[i]^arr[i+1]
            res.add(tuple(arr))
    return res

def check(a,b):
    return tuple(b) in reachable(a)

def possible_i_values(a,i):
    n=len(a)
    vals=set()
    for b in reachable(a):
        vals.add(b[i])
    return vals

def brute_conditions(a):
    n=len(a)
    # compute allowed sets from prefix-XOR idea
    allowed=[set() for _ in range(n)]
    for i in range(n):
        s=0
        allowed[i].add(a[i]^0)
        x=0
        for j in range(i+1,n):
            x ^= a[j]
            allowed[i].add(a[i]^x)
    return allowed

# test random examples
import random
random.seed(0)
for n in range(2,6):
    for _ in range(50):
        a=[random.randint(0,7) for __ in range(n)]
        R=reachable(a)
        allowed_i=brute_conditions(a)
        # Check if for all b in R, for all i, b_i in allowed_i[i]; that's necessary: must be true
        if not all(all(b[i] in allowed_i[i] for i in range(n)) for b in R):
            print("counterexample allowed necessary false", a)
            raise SystemExit
        # Now check if any b choices that pick for each i independently a value from allowed_i is always realizable?
        # We'll test random selection of b using per-i allowed sets
        for _ in range(100):
            b=[random.choice(tuple(allowed_i[i])) for i in range(n)]
            if (tuple(b) in R) != True: # check maybe false
                # Not all combos are reachable; but to find if condition "each b_i in allowed set" suffices for existence
                if all(b[i] in allowed_i[i] for i in range(n)):
                    if tuple(b) not in R:
                        print("found b in allowed but not reachable", a, b, n)
                        raise SystemExit
        # So far none failing
print("no counterexamples for small n <=5 with small values")

Python

python
a=[5,0,2]
R=reachable(a)
allowed=[set() for _ in range(3)]
for i in range(3):
    x=0
    allowed[i].add(a[i])
    for j in range(i+1,3):
        x ^= a[j]
        allowed[i].add(a[i]^x)
allowed, R


([{5, 7}, {0, 2}, {2}], {(5, 0, 2), (5, 2, 2), (7, 2, 2)})

Python

python
def reachable_orders(a):
    n=len(a)
    res=set()
    ops=list(range(n-1))
    from itertools import combinations, permutations
    for mask in range(1<<(n-1)):
        idx=[i for i in range(n-1) if mask>>i &1]
        for order in permutations(idx):
            arr=a.copy()
            for i in order:
                arr[i]=arr[i]^arr[i+1]
            res.add(tuple(arr))
    return res

def reachable_r2l(a):
    n=len(a)
    res=set()
    for mask in range(1<<(n-1)):
        idx=[i for i in range(n-1) if mask>>i &1]
        arr=a.copy()
        for i in sorted(idx, reverse=True):
            arr[i]=arr[i]^arr[i+1]
        res.add(tuple(arr))
    return res

import random
random.seed(1)
for n in range(2,7):
    for _ in range(100):
        a=[random.randint(0,7) for _ in range(n)]
        R1=reachable_orders(a)
        R2=reachable_r2l(a)
        if R1!=R2:
            print("Found discrepancy for n", n, a, len(R1), len(R2))
            # print (R1 - R2)
            raise SystemExit
print("For sizes up to 6 tests, sets equal")

Python

python
a=[4,1,6]
R1=reachable_orders(a)
R2=reachable_r2l(a)
R1,R2,R1-R2


({(3, 7, 6), (4, 1, 6), (4, 7, 6), (5, 1, 6), (5, 7, 6)},
 {(3, 7, 6), (4, 1, 6), (4, 7, 6), (5, 1, 6)},
 {(5, 7, 6)})

Python

python
from itertools import combinations, permutations
a=[4,1,6]
n=3
for mask in range(1<<(n-1)):
    idx=[i for i in range(n-1) if mask>>i &1]
    for order in permutations(idx):
        arr=a.copy()
        for i in order:
            arr[i]^=arr[i+1]
        if tuple(arr)==(5,7,6):
            print("order", order)

Python

python
def can_transform_greedy(a,b):
    n=len(a)
    if a[-1]!=b[-1]:
        return False
    # suffix XORs S[i] = XOR a[i..n-1]
    S=[0]*(n+1)
    for i in range(n-1,-1,-1):
        S[i]=S[i+1]^a[i]
    prev = 0  # minimal t_i (j index) cannot decrease; but t_i ∈ [i..n-1?] We'll use j in [i..n-1]; our t_i = j.
    # Clarify: our j equals t_i, range i..n-1?? Wait t_i ∈ [i..n] if we think range XOR i+1..t_i inclusive; Since indices 0-based to n-1.
    # Let t_i_use be in [i..n-1] for non-empty? If t_i = i means no change. If t_i = n-1, include upto last element.
    # We'll map to j in [i..n-1]
    prev = 0
    for i in range(n):
        d = a[i]^b[i]
        # We need d = XOR of a[i+1..j] for some j in [max(i, prev)..n-1]
        found=False
        start = max(i, prev)
        x=0
        # But if start > i, we cannot choose j = i; so but if d == 0, we can set j=i (no change) only if start==i; if start>i, we can also not change? 
        # Non-decreasing t means t_i >= prev; If prev > i, you cannot have t_i=i (no change). But is that necessary in actual orders?
        # Let's think: If prev (t_{i-1}) is > i, can t_i < prev? No, t_i must be >= prev. So if prev > i, t_i can't be i; you must include at least up to prev. That means if d==0, you need XOR(i+1..j) == 0 for some j>=prev.
        for j in range(start, n):
            # compute XOR(i+1..j)
            val = S[i+1]^S[j+1]
            if val == d:
                found=True
                prev=j
                break
        if not found:
            return False
    return True

# test against brute reachability
import random
random.seed(0)
for n in range(2,8):
    for _ in range(200):
        a=[random.randint(0,7) for __ in range(n)]
        R=reachable(a)
        for _ in range(100):
            b=list(random.choice(tuple(R)))
            if can_transform_greedy(a,b) != True:
                print("False negative", a,b)
                raise SystemExit
        # Try random b not necessarily reachable, check no false positives
        for _ in range(100):
            b=[random.randint(0,7) for __ in range(n)]
            if (tuple(b) in R) != can_transform_greedy(a,b):
                print("Mismatch", a,b, (tuple(b) in R), can_transform_greedy(a,b))
                raise SystemExit
print("Greedy matches brute for tested cases")

Python

python
a=[6,2,3,6]
R=reachable(a)
b=[7,7,5,6]
R, (tuple(b) in R)


({(1, 7, 5, 6),
  (4, 1, 3, 6),
  (4, 1, 5, 6),
  (4, 2, 3, 6),
  (4, 2, 5, 6),
  (4, 7, 5, 6),
  (6, 1, 3, 6),
  (6, 1, 5, 6),
  (6, 2, 3, 6),
  (6, 2, 5, 6),
  (6, 7, 5, 6),
  (7, 1, 3, 6),
  (7, 1, 5, 6)},
 False)

Python

python
def witness_t(a,b):
    n=len(a)
    if a[-1]!=b[-1]:
        return None
    S=[0]*(n+1)
    for i in range(n-1,-1,-1):
        S[i]=S[i+1]^a[i]
    prev=0
    t=[]
    for i in range(n):
        d=a[i]^b[i]
        start=max(i,prev)
        found=False
        for j in range(start,n):
            if (S[i+1]^S[j+1])==d:
                t.append(j)
                prev=j
                found=True
                break
        if not found: return None
    return t

a=[6,2,3,6]; b=[7,7,5,6]
witness_t(a,b)


[2, 3, 3, 3]

Python

python
def apply(a,order):
    arr=a.copy()
    for i in order:
        arr[i]^=arr[i+1]
    return arr
a=[6,2,3,6]
apply(a,[2,1,0])


[1, 7, 5, 6]

Python

python
def condition(a,b):
    n=len(a)
    if a[-1]!=b[-1]:
        return False
    for i in range(n-2,-1,-1):
        if not (b[i]==a[i] or b[i]==(a[i]^b[i+1])):
            return False
    return True

import random
random.seed(0)
for n in range(2,7):
    for _ in range(100):
        a=[random.randint(0,15) for __ in range(n)]
        R=reachable(a)
        # check that for all reachable b, condition holds
        for b in R:
            if not condition(a,b):
                print("Reachable but condition fails", a,b)
                raise SystemExit
        # check that if condition holds, b is reachable
        for _ in range(50):
            # generate b by satisfying condition randomly
            # We'll construct b using the condition recursively
            b=[0]*n
            b[-1]=a[-1]
            for i in range(n-2,-1,-1):
                if random.choice([True,False]):
                    b[i]=a[i]
                else:
                    b[i]=a[i]^b[i+1]
            if tuple(b) not in R:
                print("Condition-produced b not reachable", a,b)
                raise SystemExit
print("Condition exactly matches reachable sets for tested cases")

Python

python
a=[11,15,13]
R=reachable(a)
[(order, apply(a,list(order))) for mask in range(1<<2) for order in permutations([i for i in range(2) if mask>>i &1]) if apply(a,list(order))==(4,2,13)]


[]

Python

python
a=[11,15,13]
R=reachable(a)
R, (4,2,13) in R


({(4, 2, 13), (4, 15, 13), (9, 2, 13), (11, 2, 13), (11, 15, 13)}, True)

Python

python
from itertools import permutations
def all_orders_for_b(a,b):
    n=len(a)
    for mask in range(1<<(n-1)):
        ops=[i for i in range(n-1) if (mask>>i)&1]
        for order in permutations(ops):
            arr=a.copy()
            for i in order:
                arr[i]^=arr[i+1]
            if tuple(arr)==tuple(b):
                yield (ops, order)

list(all_orders_for_b([11,15,13],[4,2,13]))[:10]


[([0, 1], (0, 1))]

Мысль

Designing the greedy check

I’m considering a right-to-left greedy approach to check if each b_i can match its possible target values. If b_i satisfies one of three conditions (from a_i, a_i ⊕ a_{i+1}, or a_i ⊕ b_{i+1}), it might be valid. But I’m testing this in multiple ways to ensure consistency, particularly focusing on what order operations can take. I’ll also check rigorously with random a and b arrays.

Thought for 6m 11s

Ответ

Here’s a clean O(n) check. The key observation:

For the last element, you can’t change it → a[n-1] must equal b[n-1].

For each i < n-1, depending on when (or if) you apply the operation at i, the only possible final values for a[i] are:

  • don’t use op at i: a[i]
  • use op at i before touching i+1: a[i] ^ a[i+1]
  • use op at i after finishing i+1: a[i] ^ b[i+1]

So a transformation is possible iff for every i (right to left) b[i] is one of those three values.

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

public class Main {
    // Fast scanner for large inputs
    private 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++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' '); // skip spaces
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    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();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextInt();
            for (int i = 0; i < n; i++) b[i] = fs.nextInt();

            boolean ok = true;

            // Last element must be equal (cannot be changed)
            if (a[n - 1] != b[n - 1]) {
                ok = false;
            } else {
                // Check from right to left
                for (int i = n - 2; i >= 0 && ok; i--) {
                    int v1 = a[i];
                    int v2 = a[i] ^ a[i + 1];
                    int v3 = a[i] ^ b[i + 1];
                    int bi = b[i];
                    if (!(bi == v1 || bi == v2 || bi == v3)) {
                        ok = false;
                    }
                }
            }

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

Why this works: any valid sequence of operations must make each b[i] equal to exactly one of {a[i], a[i]^a[i+1], a[i]^b[i+1]} depending on whether we skip, go before i+1, or go after i+1. Conversely, if all these local conditions hold (processing from right to left), we can always order the operations to realize b.

Поделиться этим Q&A