FUNARR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Abhinav sharma
Tester: Samarth gupta and Manan Grover
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Knapsack DP using Bitsets, Greedy

PROBLEM

The functional array of an array A = [A_1, A_2, \dots, A_N] is the array fA of size N-1, where fA_i = A_{i+1} - A_i for 1\leq i \lt N. For example, if A = [2, 3, 9, 11] then fA = [1, 6, 2].

You are given two arrays B = [B_1, B_2, \dots, B_N] and Z = [Z_1, Z_2, \dots, Z_M] 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.

QUICK EXPLANATION

  • Since each element in B is present in A, the difference between adjacent elements of B represents a continuous subarray in fA.
  • We have Z such that fA is a subsequence of Z, so each B_{i+1}-B_i must be represented by a subsequence of Z.
  • We need to partition Z into N-1 partitions such that i^{th} partition contains a subsequence with sum B_{i+1}-B_i for each 1 \leq i \leq N-1.
  • We process B_{i+1}-B_i one by one and try to find the leftmost endpoint for the current partition greedily. The problem becomes the classical Knapsack DP problem.

EXPLANATION

Observations

We have fA_i = A_{i+1}-A_i. Let’s consider two adjacent elements in B, say B_i and B_{i+1}. Since B is a subsequence of A, these two values have their corresponding position in sequence A. Let’s assume B_i appears at position p in A, and B_{i+1} appears at position q in A for some p and q (p \lt q).

We can observe that \displaystyle \sum_{i = p}^{q-1} f A_i = \sum_{i = p}^{q-1} A_{i+1}-A_i = A_q-A_p.

The idea here is that if two elements x and y appear together in B, there must exist a subarray in f A, such that the subarray sum is y-x.

Now, we don’t have f A, but Z such that fA is a subsequence of Z. This implies that there must be a subsequence of Z with sum y-x

Problem with N = 2

Let’s assume B contains only two elements, x and y. If fhe corresponding A has A_p = x and A_q = y, then \displaystyle \sum_{i = p}^{q-1} f A_i = y-x.

This implies there must be a subsequence of Z with sum y-x.

So, for N = 2, the problem reduces to classical knapsack DP problem, checking whether there exists a subsequence with given sum in Z.

General case

Let’s assume N = 3. We will have to find two subsequences, one with sum B_2-B_1 and one with sum B_3-B_2.

The chosen subsequences must not be interleaved.

Example: Consider B = [2,4,9] and Z = [1,3,1,2]. Even though we can choose [1,1] as first subsequence and [3, 2] as second subsequence, this is not a valid solution, since fA is a subsequence of Z without changing order, so the subarray of fA_1 must end before subarray of f A_2 starts.

Hence, we aim to partition Z into N-1 contiguous parts P_i such that each element is a part of exactly one part, and and each P_i must contain a subsequence with sum B_{i+1}-B_i.

Greedy Partitioning

We know that first partition begins at cell one. It would be optimal to keep toe current partition size as small as possible. For this, we want to find the smallest position x such that first x elements of Z contain a subsequence with sum B_2-B_1. As soon as we found x, we can discard B_1 and first x elements of Z.

We can repeat this process until either we manage to find N-1 partitions (the answer is yes in that case), or the elements of Z are used up (answer is no in that case).

Finding subsets with given sum incrementally

We need to add element one by one, and after each addition, determine whether some sum is achievable or not. This is standard 0-1 Knapsack DP.

Wouldn’t this time out? Time complexity analysis

  • Observation: If the answer is YES, B is a non-decreasing sequence.
    Proof: All elements of Z are non-negative. This means B_{i+1}-B_i \geq 0 \implies B_{i+1} \geq B_i
  • Considering each part (B_i, B_{i+1}), we only need to build a knapsack of size B_{i+1}-B_i, as elements larger than this value do not matter. The time complexity of building this knapsack would be O(M*(B_{i+1}-B_i))
  • The knapsack would be built N-1 times, but the sum of sizes of knapsack cannot exceed B_N-B_1 \leq 10^5, as B is a non-decreasing sequence. So the overall time taken for all knapsacks would be O(MX*M) where MX = 10^5
  • We can implement knapsack dp using bitsets, which would further improve the constant factor by factor of 32 or 64 depending upon underlying implementation.

TIME COMPLEXITY

The time complexity is O(M*MX/32) per test case.

SOLUTIONS

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

const ll mod = 1000000007;
const ll INF = (ll)1e18;
const ll MAXN = 1000006;

ll po(ll x, ll n){ 
    ll ans=1;
    while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
    return ans;
}

const int MAX = 100002;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    cin >> T;
    while(T--){
        
        int m,r;
        cin>>m>>r;

        assert(m>0 && r>0);

        int b[m], z[r];

        rep(i,m) cin>>b[i];
        rep(i,r) cin>>z[i];

        if(m==1){
            cout<<"YES"<<el;
            continue;
        }
        if(r<m-1){
            cout<<"NO"<<el;
            continue;
        }


        int l=0;
        int f=1;

        rep(i, m-1){
            int req = b[i+1]-b[i];
            //cout<<req<<" "<<l<<el;
            if(req==0){
                while(l<r && z[l]!=0) l++;
                if(l==r){
                    f=0;
                    break;
                }
                l++;
            }
            else if(req < 0){
            	f = 0;
            	break;
            }
            else{
                bitset<MAX> b;
                b[0] = 1;
                while(l<r && !b[req]){
                    b |= (b<<z[l]);
                    //cout<<b<<" "<<l<<el;
                    l++;
                }
                if(!b[req]){
                    f=0;
                    break;
                }
            }

        }


        // if(!f){
        //     for(auto h:b) cout<<h<<" ";
        //     cout<<el;
        //     for(auto h:z) cout<<h<<" ";
        //     cout<<el;
        //     cout<<el;

        //     cout<<"wrong"<<el;
        // }

        if(f) cout<<"YES"<<el;
        else cout<<"NO"<<el;


    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}
Tester's Solution 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define asc(i,a,n) for(I i=a;i<n;i++)
#define dsc(i,a,n) for(I i=n-1;i>=a;i--)
#define forw(it,x) for(A it=(x).begin();it!=(x).end();it++)
#define bacw(it,x) for(A it=(x).rbegin();it!=(x).rend();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define all(x) (x).begin(),(x).end()
#define sz(x) (I)((x).size())
#define clr(x) (x).clear()
#define U unsigned
#define I long long int
#define S string
#define C char
#define D long double
#define A auto
#define B bool
#define CM(x) complex<x>
#define V(x) vector<x>
#define P(x,y) pair<x,y>
#define OS(x) set<x>
#define US(x) unordered_set<x>
#define OMS(x) multiset<x>
#define UMS(x) unordered_multiset<x>
#define OM(x,y) map<x,y>
#define UM(x,y) unordered_map<x,y>
#define OMM(x,y) multimap<x,y>
#define UMM(x,y) unordered_multimap<x,y>
#define BS(x) bitset<x>
#define L(x) list<x>
#define Q(x) queue<x>
#define PBS(x) tree<x,null_type,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define PBM(x,y) tree<x,y,less<I>,rb_tree_tag,tree_order_statistics_node_update>
#define pi (D)acos(-1)
#define md 1000000007
#define rnd randGen(rng)
int main(){
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<I> randGen;
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  I t;
  cin>>t;
  while(t--){
    I m,r;
    cin>>m>>r;
    I b[m],z[r];
    asc(i,0,m){
      cin>>b[i];
    }
    asc(i,0,r){
      cin>>z[i];
    }
    I x=0;
    BS(100001) bs;
    B f=false;
    asc(i,0,m-1){
      f=true;
      if(b[i]>b[i+1]){
        break;
      }
      bs&=0;
      bs[0]=1;
      while(x<r){
        if(b[i]==b[i+1]){
          if(z[x]==0){
            f=false;
            x++;
            break;
          }
        }else{
          bs|=bs<<z[x];
          if(bs[b[i+1]-b[i]]){
            f=false;
            x++;
            break;
          }
        }
        x++;
      }
      if(f){
        break;
      }
    }
    if(f){
      cout<<"NO\n";
    }else{
      cout<<"YES\n";
    }
  }
  return 0;
}
Editorialist's Solution 
T = int(input())
for _ in range(T):
    N, M = map(int, input().strip().split(' '))
    B = list(map(int, input().strip().split(' ')))
    Z = list(map(int, input().strip().split(' ')))

    yes = M >= N-1
    for i in range(1, N):
        yes = yes and B[i] >= B[i-1]

    ind = 0
    for i in range(N-1):
        if not yes:
            break
        R = B[i+1]-B[i]
        if R == 0:
            while ind < M and Z[ind] != 0:
                ind += 1
            if ind == M:
                yes = False
            ind += 1
        else:
            dp = 1
            mod = (1 << (R+1)) - 1
            while ind < M and ((dp >> R) & 1) == 0:
                if Z[ind] <= R:
                    dp |= (dp << Z[ind]) & mod
                ind += 1

            if ((dp >> R) & 1) == 0:
                yes = False

    print("YES" if yes else "NO")

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

1 Like