Functional Array FUNARR Solution Codechef

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 a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains three lines of input.
  • The first line contains two integers NN and MM – the lengths of BB and ZZ respectively.
  • The second line contains NN space-separated integers B1,B2,…,BNB1,B2,…,BN; the elements of BB.
  • The third line contains MM space-separated integers Z1,Z2,…,ZMZ1,Z2,…,ZM; the elements of ZZ.

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≤1051≤T≤105
  • 1≤N≤1051≤N≤105
  • 1≤M≤1051≤M≤105
  • 0≤Bi≤1050≤Bi≤105
  • 0≤Zi≤1050≤Zi≤105
  • The sum of NN over all test cases does not exceed 105105
  • The sum of MM over all test cases does not exceed 105105

Subtasks

Subtask #1 (5 points):

  • 1≤M≤101≤M≤10
  • 1≤N≤1031≤N≤103
  • 0≤Bi≤1030≤Bi≤103
  • 0≤Zi≤1030≤Zi≤103
  • The sum of MM over all test cases does not exceed 100100

Subtask #2 (40 points):

  • 1≤M≤1031≤M≤103
  • 1≤N≤1031≤N≤103
  • 0≤Bi≤1030≤Bi≤103
  • 0≤Zi≤1030≤Zi≤103
  • The sum of MM over all test cases does not exceed 103103

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]A=[1,2,3] is one possible array.

  • B=[2,3]B=[2,3] is a subsequence of AA
  • fA=[1,1]fA=[1,1] is a subsequence of Z=[1,1]Z=[1,1].

Test case 2:

It can be shown that no array AA can both contain B=[2,4]B=[2,4] as a subsequence and also have fAfA be a subsequence of Z=[1,3]

Functional Array FUNARR Solution is updated. Click Below

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

Codechef Long Challenges Solution

October Long Challenge 2021 Solution

September Long Challenge 2021 Solution

Leave a Comment