Editorial : SUBSFREQ , CHEFWED , SKMP

Editorial | August long challenge 2020 | Video Editorial|video solution

Beginer friendly Editorial

  1. Subsequence Frequency Counting: SUBSFREQ
    https://youtu.be/xHsyp-g1pVc

  2. Chef and Wedding Arrangements: CHEFWED
    https://youtu.be/0qyEsqymonc

  3. Smallest KMP : SKMP
    https://youtu.be/2woDuXBKCbo

  4. Another Card Game Problem: CRDGAME3
    https://youtu.be/J4VPSjtwlS8

  5. Chef and Linear Chess: LINCHESS
    https://youtu.be/37cSsGCXCD4

  6. Chef Wars - Return of the Jedi: CHEFWARS
    https://youtu.be/OGe73pn1x1o

2 Likes
        #include<bits/stdc++.h>
        using namespace std;

        typedef long long ll;
        ll MOD =  1000000007;
        #define MX 500002

        unsigned long long power(ll x, ll y) 
        { 
            unsigned long long res = 1;
            x = x % MOD; 
            while (y > 0) { 
                if (y & 1) 
                    res = (res * x) % MOD; 
                y = y >> 1; // y = y/2 
                x = (x * x) %  MOD; 
            } 
            return res; 
        } 
        
        unsigned long long modInverse(ll n) 
        { 
            return power(n,  MOD - 2); 
        } 
        unsigned long long NcR(ll n, ll r) 
        { 
            if (r == 0) 
                return 1; 
            unsigned long long fac[n + 1]; 
            fac[0] = 1; 
            for (int i = 1; i <= n; i++) 
                fac[i] = (fac[i - 1] * i) %  MOD; 
        
            return (fac[n] * modInverse(fac[r]) % MOD * modInverse(fac[n - r]) % MOD) % MOD; 
        }

        void solve(){
            
        ll n;
        cin>>n;
        ll A[n+1];

        for(int i=0;i<n;i++)
        cin>>A[i];

        ll Frq[n+1];
        memset(Frq, 0 ,sizeof(Frq));

        for(int i=0;i<n;i++)
        Frq[A[i]]++;

        ll res[n+1];

        vector<ll> get[n+1];
        for(ll i=1;i<=n;i++)
        {
            ll prev = 0;
            get[i].push_back(0);
            for(ll j=1;j<=Frq[i];j++){
            ll nc = NcR(Frq[i], j)%MOD;
            get[i].push_back( (prev + nc)%MOD);
            prev += nc;
            prev%=MOD;
            }
        }

        // for(ll i=1;i<=n;i++)
        // {
        //     for(auto x:get[i])
        //     cout<<x<<" + ";
        //     cout<<"\n";
        // }

        for(ll i=1;i<=n;i++)
        {

        ll prod;
        ll rs = 0;

        for(ll j = 1;j<= Frq[i];j++){
            
            prod = NcR(Frq[i] , j)%MOD;
            for(ll k = 0;k<=n;k++)
            {
            
                if(Frq[k]!=0)
                {if(k < i){
                
                ll add = 0;
                add += get[k][min(j-1 , Frq[k])]%MOD;
                add+=1LL;        
                prod *= add%MOD;
                prod %=MOD;
                }else if (k >i){

                ll add = 0;
                add += get[k][min(j , Frq[k])]%MOD;
                add+=1LL;
                prod *= add%MOD;
                prod %=MOD;
                }
                }
            }
        rs += prod%MOD;
        }
        res[i] = rs%MOD;
        }

        for(ll i=1;i<=n;i++)
        cout<<(res[i]%MOD)<<" ";
        cout<<"\n";

        }

        int main(void){
            ios_base::sync_with_stdio(false);
            cin.tie(NULL);
            test;

            return 0;
        }

Where am I going wrong for subtask 1, probably Modulo?
https://www.codechef.com/viewsolution/36854165

https://www.codechef.com/viewsolution/36855781 can anyone tell me where am I getting wrong for atleast 10 points in the question SUBSFREQ

Take this as your custom input
1
3
3 2 1
your answer would be 1 2 4
but its wrong , it should be 4 2 1 .
And even if custom input is
1
3
1 2 3
Then also answer is 4 2 1 .

For each test case, print a single line containing NN space-separated integers. For each valid i, the i-th of these integers should be the number of occurrences of i on Chef’s sheet of paper.

The chefs write down is a bit different from what u took .

Read the above para carefully you will get it :slight_smile:

1 Like