Functional Array FUNARR Solution
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.
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case contains three lines of input.
- The first line contains two integers N and M the lengths of B and Z respectively.
- The second line contains N space-separated integers B1,B2,…,BN; the elements of B.
- The third line contains M space-separated integers Z1,Z2,…,ZM; the elements of Z.
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≤N≤105
- 1≤M≤105
- 0≤Bi≤105
- 0≤Zi≤105
- The sum of N over all test cases does not exceed 105
- The sum of M over all test cases does not exceed 105
Subtasks
Subtask #1 (5 points):
- 1≤M≤10
- 1≤N≤103
- 0≤Bi≤103
- 0≤Zi≤103
- The sum of M over all test cases does not exceed 100
Subtask #2 (40 points):
- 1≤M≤103
- 1≤N≤103
- 0≤Bi≤103
- 0≤Zi≤103
- The sum of M over all test cases does not exceed 103
Subtask #3 (55 points):
- Original constraints
Sample Input 1
2
2 2
2 3
1 1
2 2
2 4
1 3
Sample Output 1
YES
NO
Explanation
Test case 1:
A=[1,2,3] is one possible array.
- B=[2,3] is a subsequence of A
- fA=[1,1] is a subsequence of Z=[1,1].
Test case 2:
It can be shown that no array A can both contain B=[2,4] as a subsequence and also have fA be a subsequence of Z=[1,3]
SOLUTION
Program Python: Functional Array FUNARR Solution in Python
from collections import defaultdict, deque
from bisect import bisect_left
from sys import stdin
def subset_sum (A, k):
subsets = defaultdict(list)
subsets[0] = []
for i in range(len(A)):
old_subsets = subsets
subsets = defaultdict()
for (prev_sum, subset) in old_subsets.items():
subsets[prev_sum] = subset
new_sum = prev_sum + A[i]
new_subset = subset + [i]
if k == new_sum:
new_subset.sort()
return new_subset
else:
subsets[new_sum] = new_subset
return [-1]
def solve():
results = []
for _ in range(int(stdin.readline().strip())):
N, M = map(int, stdin.readline().strip().split())
B = list(map(int, stdin.readline().strip().split()))
Z = list(map(int, stdin.readline().strip().split()))
indices = defaultdict(deque)
if N == 1:
results.append("YES")
continue
D = [B[i] - B[i-1] for i in range(1,N)]
if N-1 > M:
results.append("NO")
continue
if min(D) < min(Z):
results.append("NO")
continue
for i in range(M):
indices[Z[i]].append(i)
x = -1
for i in range(len(D)):
d = D[i]
ans = "NO"
y1, y2 = 10**10, 10**10
popcnt = 0
if d in indices and len(indices[d]):
y1 = indices[d][0]+1
popcnt += 1
while popcnt < len(indices[d]) and y1 <= x:
y1 = indices[d][popcnt]+1
popcnt += 1
if y1 <= x:
y1 = 10**10
s = 0 if x == -1 else x
e = y1 if y1 != 10**10 else M-(len(D)-i-1)
sub = subset_sum(Z[s:e], d)
if sub[0] != -1:
y2 = sub[-1]+s+1
x = min(y1, y2)
while len(indices[d]) and x > indices[d][0]:
indices[d].popleft()
if len(D)-i-1 > M-x:
break
if x != 10**10:
ans = "YES"
else:
break
results.append(ans)
print ('\n'.join(map(str, results)))
if __name__ == "__main__":
solve()
Program C++: Functional Array FUNARR Solution in C++
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define pb push_back
#define ss second
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define int long long
#define endl '\n'
const int N = 3e5+5, Mod = 1e9 + 7;
int32_t main(){
IOS;
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
// freopen("outputf.in", "w", stdout);
#endif
int t; cin >> t;
while(t--) {
int n, m; cin >> n >> m;
int a[n], b[m];
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < m; i++){
int x; cin >> x;
b[i] = x;
}
int j = 0;
int all = 0;
int ansr = 1;
for(int i = 1; i < n; i++){
int l = a[i - 1];
int flag = 0;
int r = a[i];
if(r - l == 0){
while(j < m){
if(b[j] == 0){
flag = 1;
j++;
break;
}
j++;
}
}
else {
int diff = r - l;
int sum = 0;
set<int> st;
st.insert(0);
while(j < m){
int rr = b[j];
sum += rr;
j++;
set<int> st2;
int k = 50;
auto it = st.end();
it--;
while(k--){
if(rr + *it <= diff){
st2.insert(rr + *it);
}
st2.insert(*it);
if(rr + *it == diff){
flag = 1;
break;
}
if(it == st.begin())
break;
it--;
}
if(flag == 1)
break;
st = st2;
}
}
if(flag == 0){
ansr = 0;
break;
}
}
if(ansr)
cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
November Long Challenge 2021 Solution
- Which Fuel is Cheaper CHEAPFUEL Solution
- Convex Hulk CONHULK Solution
- Functional Array FUNARR Solution
- Flip or Compress FLIPCOMP Solution
- Maximise the bridges MAXBRIDGE Solution
- Wildcard Replacement WLDRPL Solution
- Xor Equation XOREQN Solution
- Hill Sequence HILLSEQ Solution
- Weird Palindrome Making MAKEPAL Solution
- Equal Coins EQUALCOIN Solution Codechef