Adding on Segments SOLUTION ADDONSEG

Adding on Segments SOLUTION ADDONSEG

There are N integers A1,A2,…,AN on a circle. For each valid i, Ai and Ai+1 are adjacent; A1 and AN are also adjacent.

Chef has a sequence of integers B1,B2,…,BN, which he may use to perform any number of operations (including zero). In one operation, he should do the following:

Choose an integer i (1≤i≤N).

Choose i consecutive integers on the circle.

Choose a sign S=±1 and add S⋅Bi to each of the chosen integers. In other words, either add Bi to each of them or subtract Bi from each of them.

The goal is to make all the integers on the circle equal to 0. Can Chef achieve it using these operations?



The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N.

The second line contains N space-separated integers A1,A2,…,AN.

The third line contains N space-separated integers B1,B2,…,BN.


For each test case, print a single line containing the string “YES” if it is possible to make all integers on the circle equal to 0 or “NO” if it is impossible.




0≤Ai,Bi≤104 for each valid i

the sum of N over all test cases does not exceed 104


Subtask #1 (40 points): A1=A2=…=AN

Subtask #2 (60 points): original constraints


Example Input



1 1 3 3 2

0 0 2 1 0


1 1 1 1

2 2 2 2


2 0 1

0 3 5

Example Output





Example case 1: We can make everything 0 using two operations: choose i=4 and change the circular sequence (1,1,3,3,2) to (1−1,1−1,3−1,3−1,2)=(0,0,2,2,2), then choose i=3 and change it to (0,0,2−2,2−2,2−2)=(0,0,0,0,0).

Example case 2: The parities of integers on the circle cannot change, so they cannot become 0.


Related : 

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS


Related :

Related :

Leave a Comment

5 × 4 =