Functional Array FUNARR Solution Codechef

Functional Array FUNARR Solution

Functional Array FUNARR Solution The functional array of an array A=[A1,A2,…,AN]A=[A1,A2,…,AN] is the array fAfA of size N−1N−1, where fAi=Ai+1−AifAi=Ai+1−Ai for 1≤i<N1≤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=[B1,B2,…,BN] and Z=[Z1,Z2,…,ZM]Z=[Z1,Z2,…,ZM] of length NN and MM respectively. Find out whether there exists an array AA such that: BB is a subsequence of AA, and fAfA is a subsequence of ZZ Print “YES” (without quotes) if such an array AA exists, and “NO” otherwise. Input Format The first line of input contains … Read more