Question

Phonepe | OA Coding Questions and Solutions | 2022 | Set-14

Answer 1

 

 

IMAGES OF QUES

Answer 2

Solution in O(n^2) time, for each restricted position we have a[i]>a[i+1]<a[i+2] or a[i]<a[i+1]>a[i+2]. Ofcourse if we have the same type of restriction for two consecutive place then there is not even a single good permutation. Otherwise the n length sequence breaks up to smaller blocks, where in each block we see that: a[k]<a[k+1]>a[k+2]<a[k+3]>a[k+4]< etc. or a[k]>a[k+1]<a[k+2]>a[k+3]<a[k+4]> etc. but notice that it isn't interesting that we see which sequence we have the same number of possibilities due to the x->N+1-x symmetry. And if we want to calculate the number of such permutations for given N, then there is an easy recursion: u[N]=sum(i=2,N,2,binomial(N-1,i-1)*u[i-1]*u[N-i]) where we sum only on even i values, the idea behind this is that see where you can place N, then the N length breaks up to i-1 and N-i length. Notice that it is possible that some numbers from [1,n] will still remain so in the end we just multiple by N!.
Used also the little Fermat theorem: 1/x==x^(p-2) mod p.
Overall interesting, but hard problem.

 

class Solution{

#define mod 1000000007
private: vector<int> fact;
public:

int powmod(int base,int expo,int m){
    
    int ret=1,mult=base;
    while(expo){
        if(expo&1) ret=((long)ret*mult)%m;
        mult=((long)mult*mult)%m;
        expo>>=1;
    }
    return ret;
}

int inv(int x) { return powmod(x,mod-2,mod); }

int binom(int n,int k){
    
    int mult=((long)fact[k]*fact[n-k])%mod;    
    return ((long) inv(mult)*fact[n])%mod;
}

int sequence(int n,vector<int> A,vector<int> B){
 
    fact.resize(n+1);
    vector<long> u(n+1);
    
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=((long)i*fact[i-1])%mod;
    
    u[0]=1;
    u[1]=1;
    // for u: a[1]<a[2]>a[3]<a[4]>a[5]<a[6]
    for(int N=2;N<=n;N++){
        long sum=0;
        for(int i=2;i<=N;i+=2)
            // sum+=binomial(N-1,i-1)*u[i-1]*u[N-i]
            sum=(sum+(long)binom(N-1,i-1)*((u[i-1]*u[N-i])%mod))%mod;
        u[N]=sum;
    }
    
    vector<bool>inc(n+2,false),dec(n+2,false);
    for(int p:A)inc[p]=true;
    for(int p:B)dec[p]=true;
    
    for(int i=1;i<=n;i++){
        if(dec[i] && inc[i]) return 0;
        if(dec[i] && dec[i+1]) return 0;
        if(inc[i] && inc[i+1]) return 0;
    }
    
    int N=n;
    long ans=1;
    for(int i=1;i<=n;){
        int len=0;
        while(i<=n && (dec[i]||inc[i])) {len++;i++;}
        if(len>0){
            len+=2;
            long mult=(binom(N,len)*u[len])%mod;
            ans=(ans*mult)%mod;
            N-=len;
        }
        else i++;
    }    
    ans=((long) ans*fact[N])%mod;
    
    return ans;
}};

int main(void){
    
    Solution *s=new Solution;
    
    cout<<s->sequence(4,{2},{3})<<endl;
    
    cout<<s->sequence(10,{2,4,9},{3,8})<<endl;
    
    return 0;
}
/* 
output
5
100800
*/