Functional Array ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 The functional array of an array 

A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$ is the array fA$fA$ of size N−1$N-1$, where fAi=Ai+1−Ai$f{A}_i=A_{i+1}-A_i$ for 1≤i<N$1\le i<N$. For example, if A=[2,3,9,11]$A=[2,3,9,11]$ then fA=[1,6,2]$fA=[1,6,2]$.

You are given two arrays B=[B1,B2,…,BN]$B=[B_1,B_2,\dots ,B_N]$ and Z=[Z1,Z2,…,ZM]$Z=[Z_1,Z_2,\dots ,Z_M]$ of length N$N$ and M$M$ respectively. Find out whether there exists an array A$A$ such that:

Output Format

For each test case, output a single line containing one word - either "YES" or "NO". You may print each character of the string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤M≤105$1\le M\le {10}^5$
• 0≤Bi≤105$0\le B_i\le {10}^5$
• 0≤Zi≤105$0\le Z_i\le {10}^5$
• The sum of N$N$ over all test cases does not exceed 105${10}^5$
• The sum of M$M$ over all test cases does not exceed 105${10}^5$

Subtasks

Subtask #1 (5 points):

• 1≤M≤10$1\le M\le 10$
• 1≤N≤103$1\le N\le {10}^3$
• 0≤Bi≤103$0\le B_i\le {10}^3$
• 0≤Zi≤103$0\le Z_i\le {10}^3$
• The sum of M$M$ over all test cases does not exceed 100$100$

Subtask #2 (40 points):

• 1≤M≤103$1\le M\le {10}^3$
• 1≤N≤103$1\le N\le {10}^3$
• 0≤Bi≤103$0\le B_i\le {10}^3$
• 0≤Zi≤103$0\le Z_i\le {10}^3$
• The sum of M$M$ over all test cases does not exceed 103${10}^3$

Subtask #3 (55 points):

• Original constraints

Code: click

• Tweet
• Share
• Share
• Share
• Share

Related Post