Choose whether to keep or flip each element from a second array so the resulting sequence can be made non-decreasing.
Problem
You are given two integer arrays a and b. Process the elements of a from left to right. For each position i, you may either keep a[i] as it is or replace it with b[i] - a[i].
Your task is to determine whether it is possible to make the resulting array non-decreasing.
A sequence x is non-decreasing if x[1] <= x[2] <= ... <= x[n].
Intuition
At each position, you want to choose a value that is large enough to respect the previous choice, but also as small as possible to leave room for future elements.
Input Format
The input contains multiple test cases.
For each test case:
- The first line contains an integer
n. - The second line contains
nintegersa[1..n]. - The third line contains
nintegersb[1..n].
Interpretation
For each index i, you may set:
x[i] = a[i], orx[i] = b[i] - a[i].
Decide whether some choice produces a non-decreasing array x.
Output Format
For each test case, print YES if it is possible to make the array non-decreasing, otherwise print NO.
Constraints
1 <= t1 <= n- Values are integers.
- The easy version has smaller limits than the hard version.
Because the exact official limits are not provided here, focus on the decision process rather than a specific numeric bound.
Example 1
Input
2 3 1 2 3 4 5 6 3 3 1 4 5 2 7
Output
YES NO
Explanation
Test case 1: choose values 1, 2, 3, which is already non-decreasing.
Test case 2: the available choices are too restrictive to build a non-decreasing sequence for all positions.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.