Swap If Equal Sum

AtCoder

IDarc203_b

Time2000ms

Memory256MB

Difficulty—

You are given length-$N$ integer sequences $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_N)$, each consisting of $0$ and $1$. Let $A[i,j]$ denote the consecutive subsequence of $A$ from the $i$\-th through the $j$\-th element. If $i>j$, then $A[i,j]$ is a length-$0$ sequence. You can perform the following operation on $A$ any number of times: * Choose four integers $a,b,c,d$ that satisfy the following two conditions: * $1 \leq a \leq b < c \leq d \leq N$ * $\sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}$ * Swap $A[a,b]$ and $A[c,d]$. More precisely, replace $A$ with the sequence formed by concatenating $A[1,a-1]$, $A[c,d]$, $A[b+1,c-1]$, $A[a,b]$, $A[d+1,N]$ in this order. Determine whether $A$ can be made to match $B$. Solve $T$ test cases for each input file. ## Constraints * $1 \leq T \leq 10^5$ * $2 \leq N \leq 2 \times 10^5$ * $0 \leq A_i \leq 1$ * $0 \leq B_i \leq 1$ * The sum of $N$ over all test cases is at most $2\times 10^5$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each case is given in the following format: $N$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$ [samples]

Samples

Input #1

3
6
1 1 1 0 0 1
0 1 1 0 1 1
2
0 0
1 0
3
1 1 1
1 1 1

Output #1

Yes
No
Yes

In the first test case, $A$ is initially $(1,1,1,0,0,1)$.  
By choosing $(a,b,c,d)=(1,2,3,6)$ and performing the operation, $A$ becomes $(1,0,0,1,1,1)$.  
Next, by choosing $(a,b,c,d)=(1,2,3,4)$ and performing the operation, $A$ becomes $(0,1,1,0,1,1)$, which matches $B$.  
In the second test case, $A$ cannot be made to match $B$.  
In the third test case, $A$ already matches $B$ from the beginning.

API Response (JSON)

{
  "problem": {
    "name": "Swap If Equal Sum",
    "description": {
      "content": "You are given length-$N$ integer sequences $A=(A_1,A_2,\\dots,A_N)$ and $B=(B_1,B_2,\\dots,B_N)$, each consisting of $0$ and $1$. Let $A[i,j]$ denote the consecutive subsequence of $A$ from the $i$\\-th ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc203_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given length-$N$ integer sequences $A=(A_1,A_2,\\dots,A_N)$ and $B=(B_1,B_2,\\dots,B_N)$, each consisting of $0$ and $1$. Let $A[i,j]$ denote the consecutive subsequence of $A$ from the $i$\\-th ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments