CHEFDQE - Editorial

editorial
, , ,
22

getting TLE, any help

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize("Ofast")
// #pragma GCC optimize "trapv"

#define ll long long 
#define lld long double

int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    for(int T=1;T<=t;T++)
    {
        //cout<<"Case #"<<T<<": ";
        
        ll n,m;
        cin>>n>>m;
        
        ll arr[n+1];
        int ans=INT_MAX;
        for(int i=1;i<=n;i++)
        cin>>arr[i];
        
        ll pref[n+1];
        pref[0]=0;
        
        for(int i=1;i<=n;i++)
        pref[i]=(pref[i-1]+arr[i])%m;
        
        for(int i=0;i<=n;i++)
        {
            for(int j=i;;j=(j-1)&i)
            {
                if(i+j<n && (i&j)==j)
                {
                    int r=n-i;
                    int l=j+1;
                    
                    ll sum1 = pref[l-1];
                    ll sum2 = pref[r];
                    
                    ll sum = sum2-sum1;
                    
                    if(sum<0)
                    sum+=m;
                    
                   // cout<<i<<" "<<j<<" "<<l<<" "<<r<<"\n";
                    
                    if(sum%m==0)
                    {
                        ans=min(ans, __builtin_popcount(i));
                        break;
                        //cout<<l<<" "<<r<<"\n";
                    }
                    
                }
                if(j==0)
                break;
            }
        }
        if(ans==INT_MAX)
        cout<<"-1\n";
        else
        cout<<ans<<"\n";
    }
}
1 Like
23

I was also facing the same problem. You are actually repeating the builtin_popcount calculation for every sub mask for a suffix. you can calculate outside the inner loop and also check if the number of set bits in the current suffix is greater than the answer, you do not need to go further inside the inner for loop.

int p1 = __builtin_popcount(suff);
if(p1>=ans){continue;}
24

There is break, so builtin_pocount is called one time for each i


This is a small optimization I guess

Edit - still TLE Solution: 50452096 | CodeChef

25

I also got TLE on same test cases.

So try using int instead of long long and hence use
__builtin_popcount (for int)

Passed code: CodeChef: Practical coding for everyone

26 
7 13
10 2 3 8 1 10 4

how its output is 2.
can someone tell the operation applied.

27

Take k=1.
Remove 1 element from end and 1 from front.
Take k=2.
Remove 2 elements from end
now you are left with {2, 3, 8} which satisfy the condition.