TOOMANYLIS2-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setters: Daanish Mahajan
Tester: Manan Grover, Abhinav Sharma
Editorialist: Devendra Singh

DIFFICULTY:

3157

PREREQUISITES:

Catalan Number, Dynamic Programing, Difference Array, Longest Increasing subsequence

PROBLEM:

This problem has two subtasks worth 50 points each.

You are given an integer N. You also have N empty sets S_1, S_2, \ldots, S_N.

Consider all the arrays A of length N such that 0 \leq A_i \leq 1 for each 1 \leq i \leq N (there are 2^N such arrays in total).

For each of these 2^N arrays, we compute an array B of length N where B_i = length of longest non-decreasing subsequence for the prefix of length i of array A. (For example: if N = 5 and A = [0, 1, 0, 1, 1], then B = [1, 2, 2, 3, 4].) Next we add the array B to the set S_{B_N} (For example, B = [1, 2, 2, 3, 4] would be added to S_4).

Output the size of sets S_1, S_2, \ldots, S_N as N space-separated integers. Since the size of the sets might be large, output the values modulo 10^9+7.

Note that the S_i are sets, and hence do not contain duplicate elements. Please look at the sample cases below for an explained example.

EXPLANATION:

Difference array: D_i of a given array A is defined as D_i = A_i-A_{i-1} (for 0 < i < N ) and D_0 = A_0 considering 0 based indexing.
Observation 1: For any array B (The array formed by computing the length of longest non-decreasing subsequence for the prefix of length i of array A) its difference array consists of only 0 and 1 as the length of longest non decreasing subsequence cannot increase by more than 1 in any case.
Observation 2: For any array B, each B_i is at least ceil(i/2). Simply take the maximum of count of zeroes or the count of ones in the prefix.
Observation 3: In the difference array formed by any array B, For any prefix length, the number of ones is greater than or equal to the number of zeroes in it.
Since each B_i is greater than ceil(i/2) and B_i is same as number of ones in the prefix of length i of difference array. Let C_1 be the count of ones and C_0 be the count of zeroes in the prefix of length i of difference array.
\therefore C_1 \geq ceil(i/2) Let i be even then C_1\geq i/2 \implies C_1>=(C_1+C_2)/2\implies (C_1>=C_2). Similar analysis can be carried out when i is odd.
Observation 4: Every such difference array is valid. An example of the array which produces the same difference array is the difference array itself. Example Let difference array be [1,0,1,0] and let A be [1,0,1,0], Then array B is [1,1,2,2] difference array is [1,0,1,0]. Each difference array corresponds to a different array B.
Thus we need to find difference arrays of size N which have total number of ones (same as B_N) in them as i for each 1<=i<=N

Dp solution
Let dp[i][j] represent we are at index i of the array and there are j ones in the prefix of the array making sure there are no more zeroes than ones in the prefix.Initialize dp[0][0] as 1.
Then either the element at i^{th} index is 1 or it is 0. Consider the dp states for both these cases as:
Then dp[i][j] = dp[i-1][j-1]+(i-j\leq j)?dp[i-1][j]:0
The answer to the problem is dp[n][i] for all i from 1 to N.
But this is and O(N^2) solution and not enough to pass all the test cases.

Combinatorics Solution
Let ^NC_K denote the usual binomial coefficient, i.e. number of ways to select K objects from set of N objects). Then number of such difference arrays having i ones in total comes out to be ^NC_{N-i}-^NC_{N-i-1} if 2*i>N else 0.
Explanation: Let f(K, N) be the number of B-arrays of length N such that the last element is K. We want to find f(1, N), f(2, N), ..., f(N, N). f(K, N) = 0 when K < N/2 or when K > N, and f(0, 0) = 1. We have the recurrence f(K, N) = f(K-1, N-1) + f(K, N-1). Think of this as lattice paths on the xy-plane. We start at (0, 0) and reach (K, N) using two types of moves:

  1. Move one step up
  2. Move diagonally up-right

The only restriction is that we aren’t allowed to cross the line y = 2\cdot x. Now let’s bring this to a more well-known form. Suppose that, instead of moving diagonally up-right, we only moved right. What happens then? If we would normally reach (K, N), now we would reach (K, N-K) instead because the number of times we moved right stays the same, and the number of times we moved up decreases by K. What about the restriction that we don’t cross y = 2x? We can see that in the new model this translates to the restriction that we don’t cross the line y = x

Proof: Consider a path that crosses the line y = 2\cdot x in the first model. Let the first time this happens be at the point (s, 2s+1) To reach (s, 2s+1), we must have made 2s+1 moves of which s were diagonal and s+1 were up. In the new model, this translates to s right moves and s+1 up moves, hence reaching (s, s+1) Similarly, reaching (s, s+1) in the new model means reaching (s, 2s+1) in the old model. So, all we need to do is count the number of standard lattice paths from (0, 0) to (K, N-K) that don’t cross the line y = x. This can be calculated by standard reflection principle stuff. The total number of paths without any constraints is just C(K + N-K, N-K) = C(N, N - K) via reflecting bad paths about y=x+1, We can derive that the total number of bad paths equals the total number of unconstrained paths to (N-K-1, K+1), which is C(N - K - 1 + K + 1, K + 1) = C(N, K+1). The answer is then their difference

We’re looking for the number of arrays of 0s and 1s such that count(1) \geq count(0) for every prefix. Starting at (0, 0), consider adding a 1 to the array as moving right and adding a 0 as moving up. Then, for length N and K ones, you reach the point (K, N-K) without crossing the line y = x
Please refer to this article for refection principle: Reflection principle

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple

using namespace std;
  
FILE *fp;
ofstream outfile;

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

const string newln = "\n", space = " ";
const int maxt = 500, maxn = 200000, maxsumn = 200000, mod = 1e9 + 7, MAX = 200010;
ll fac[MAX], ifac[MAX];
ll rpe(ll a, int b){
    ll ans = 1;
    while(b != 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return ans;
}
ll ncr(int n, int d){
    if(d > n || d < 0)return 0;
    return fac[n] * ifac[d] % mod * ifac[n - d] % mod;
}
ll cal(int n, int i){
    if(i < n / 2)return 0;
    return (ncr(n, n - i) - ncr(n, n - i - 1) + mod) % mod;
}
int main()
{   
    fac[0] = 1;
    for(int i = 1; i < MAX; i++){
        fac[i] = i * fac[i - 1] % mod;
    }
    ifac[MAX - 1] = rpe(fac[MAX - 1], mod - 2);
    for(int i = MAX - 2; i >= 0; i--){
        ifac[i] = (i + 1) * ifac[i + 1] % mod;
    }
    int sumn = 0;
    int t = readIntLn(1, maxt);
    while(t--){
        int n = readIntLn(1, maxn); sumn += n;
        for(int i = 1; i <= n; i++)cout << cal(n, i) << " \n"[i == n];
    }
    assert(sumn <= maxsumn);
    assert(getchar()==-1);
} 
Tester-1'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)
#define N 300000
I modex(I a,I b,I m){
  a=a%m;
  if(b==0){
    return 1;
  }
  I temp=modex(a,b/2,m);
  temp=(temp*temp)%m;
  if(b%2){
    temp=(temp*a)%m;
  }
  return temp;
}
I mod(I a,I b,I m){
  a=a%m;
  b=b%m;
  I c=__gcd(a,b);
  a=a/c;
  b=b/c;
  c=modex(b,m-2,m);
  return (a*c)%m;
}
I ncr(I n,I r,I fact[],I m){
  if(n<0 || r<0){
    return 0;
  }
  if(n<r){
    return 0;
  }
  return mod(fact[n],fact[n-r]*fact[r],m);
}
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 fact[N];
  fact[0]=1;
  asc(i,1,N){
    fact[i]=i*fact[i-1];
    fact[i]%=md;
  }
  I t;
  cin>>t;
  while(t--){
    I n;
    cin>>n;
    asc(i,1,n+1){
      if(2*i<n){
        cout<<0<<" ";
      }else{
        cout<<mod(ncr(n,i,fact,md)*(2*i+1-n),i+1,md)<<" ";
      }
    }
    cout<<"\n";
  }
  return 0;
}
Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll max(ll l, ll r){ if(l > r) return l ; return r;}
ll min(ll l, ll r){ if(l < r) return l ; return r;}

 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1;
const int MAX_N = 100;
const int SUM_N = 300000;
const int MAX_VAL = 100; 
const int SUM_VAL = 20005 ;
const int OFFSET = 10000 ;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#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 pb push_back
#define int long long
 
ll sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;

using ii = pair<ll,ll>;

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 ll MX=200005;
ll fac[MX], ifac[MX];

void pre(){
 fac[0]=1;
 rep_a(i,1,MX) fac[i]= (i*fac[i-1])%mod;
 rep(i,MX) ifac[i]= po(fac[i], mod-2);
}

ll ncr(ll n, ll r){
 if(r>n || r<0 || n<0) return 0;
 return (fac[n]*((ifac[r]*ifac[n-r])%mod))%mod; 
}

void solve()
{   
   int n = readIntLn(1,2e5);
   sum_n+=n;

   rep_a(i,1,n+1){
    if(2*i<n) cout<<0<<" ";
    else cout<<((ncr(n,i)-ncr(n,i+1))%mod+mod)%mod<<" ";
   }

   cout<<'\n';
}
 
signed main()
{
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" , stdin) ;
    freopen("output.txt" , "w" , stdout) ;
    #endif
    
    int t = 1;
    pre();
    t = readIntLn(1,500);

    for(int i=1;i<=t;i++)
    {    
        solve() ;
    }
    
    assert(getchar() == -1);
    assert(sum_n<=2e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"Sum of lengths : " << sum_n << '\n';
    // cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Minimum length : " << min_n << '\n';
    // cerr << "Sum o f product : " << sum_nk << '\n' ;
    // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';
}

I got the dp part. But i don’t get the combinatorics part. Can someone explain more about it?

1 Like

I will update that part soon with a more detailed explanation