6.26cf simulation match B: solution to array reduction problem

Title Description

link

CF Simulation game B: Array reduction

A word description

B. Array reduction
time limit per test1 s.
memory limit per test256 MB
inputstandard input
outputstandard output
Kristina has two arrays a and b, each containing n non-negative integers. She can perform the following operation on array a any number of times:

Kristina There are two arrays a and b, Each one contains n Nonnegative integers . She can treat a The array performs the following operations any number of times ：

For each non 0 Element minus 1, That is, all greater than 0 Of ai Replace with ai−1 (1≤i≤n). If ai yes 0, Its value remains unchanged .
Determine whether Kristina can get an array b from an array a in some number of operations (probably zero). In other words, can she make ai=bi after some number of operations for each 1≤i≤n?

Judge Kristina Whether it can pass several times （ It can be 0 Time ） Operation will a The array becomes b Array ？ let me put it another way , Can she let ai=bi For any 1≤i≤n establish ？

For example, let n=4, a=[3,5,4,1] and b=[1,3,2,0]. In this case, she can apply the operation twice:

after the first application of the operation she gets a=[2,4,3,0];
after the second use of the operation she gets a=[1,3,2,0].
For example, for n=4, a=[3,5,4,1] and b=[1,3,2,0], She can operate twice ：

After the first operation a=[2,4,3,0];
After the second operation a=[1,3,2,0].
Thus, in two operations, she can get an array b from an array a.

So after two operations , She can put a become b.

Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.

The first line contains an integer t (1≤t≤104) — Number of representative test data groups .

The descriptions of the test cases follow.

The description of each group of data is as follows .

The first line of each test case contains a single integer n (1≤n≤5⋅104).

The first line contains an integer n (1≤n≤5⋅104).

The second line of each test case contains exactly n non-negative integers a1,a2,…,an (0≤ai≤109).

The second line contains n Nonnegative integers a1,a2,…,an (0≤ai≤109).

The third line of each test case contains exactly n non-negative integers b1,b2,…,bn (0≤bi≤109).

The third line contains n Nonnegative integers b1,b2,…,bn (0≤bi≤109).

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

Data assurance Of all test data n The sum does not exceed 2⋅105.

Output
For each test case, output on a separate line:

YES, if by doing some number of operations it is possible to get an array b from an array a;
NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

For each group of test data , Output YES perhaps NO.

Example
inputCopy
6
4
3 5 4 1
1 3 2 0
3
1 2 1
0 1 0
4
5 3 7 2
1 1 1 1
5
1 2 3 4 5
1 2 3 4 6
1
8
0
1
4
6
outputCopy
YES
YES
NO
NO
YES
NO
Note
The first test case is analyzed in the statement.

For the first set of test data , It has been analyzed in the problem description .

In the second test case, it is enough to apply the operation to array a once.

For the second set of test data , One operation is enough .

In the third test case, it is impossible to get array b from array a.

For the third set of test data , Cannot from a become b.

Topic analysis

1. This question is complex and has a lot of data , Point by point analysis
2. First judgement b[i]>a[i] As long as there is one NO Next group
3. b[i] Is full of 0,YES Next group
4. b[i]！=0 Of a[i]-b[i] There is a difference NO Next group
5. b[i]==0 Of a[i]-b[i]>(4.)NO Next group , otherwise YES Next group

Code implementation

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e4+10;
int t,n,cnt;
int a[maxn],b[maxn];
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		//2
		int flag=1;
		cnt=-1;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
    
			scanf("%d",&b[i]);
			if(b[i]!=0)flag=0;
		}
		if(flag){
    
			printf("YES\n");
			continue;
		}
		//3
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]>a[i]){
    
				flag=0;
				break;
			}
		}
		if(!flag){
    
			printf("NO\n");
			continue;
		}
		//4
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]!=0){
    
				if(cnt==-1)cnt=a[i]-b[i];
				else {
    
					if(cnt!=a[i]-b[i]){
    
						flag=0;
						break;
					}
				}
			}
		}
		if(!flag){
    
			printf("NO\n");
			continue;
		}
		//5
		flag=1;
		for(int i=1;i<=n;i++){
    
			if(b[i]==0){
    
				if(cnt<a[i]-b[i]){
    
					flag=0;
					break;
				}
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}