The functional array of an array A=[A1,A2,…,AN] is the array fA of size N−1, where fAi=Ai+1−Ai for 1≤i<N. For example, if A=[2,3,9,11] then fA=[1,6,2]. You are given two arrays B=[B1,B2,…,BN] and Z=[Z1,Z2,…,ZM] of length N and M respectively. Find out whether there exists an array A such that: B is a subsequence of A, and fA is a subsequence of Z Print "YES" (without quotes) if such an array A exists, and "NO" otherwise.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n;
int b[n];
cin >> m;
int z[m];
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
for (int i = 0; i < m; i++)
{
cin >> z[i];
}
int j = m + n;
int a[j];
for (int i = 0; i < n; i++)
{
a[i] = b[i];
}
int k, i;
int f[j];
for (i = 0, k = n; k < j && i < m; i++, k++)
{
a[k] = z[i];
}
// for (int i = 0, u = n; u < j, i < m; i++, u++) {
// a[u] = z[i]; }
sort(a, a + j);
for (int i = 0; i < j - 1; i++)
{
// p= b[i];
f[i] = a[i + 1] - a[i];
}
unordered_set<int> s;
for (int i = 0; i < m; i++)
{
s.insert(f[i]);
}
int p = s.size();
for (int i = 0; i < n; i++)
{
s.insert(z[i]);
}
if (s.size() == p)
{
cout << "YES"<<endl;
}
else
{
cout << "NO"<<endl;
}
}
}
