HackerEarth Buy Em All problem solution

In this HackerEarth Buy ‘Em All problem solution Alice went shopping with her Dad to a magical shop.

She wants to buy some golden snitches from the shop. All the snitches in the shop are kept on a rack in straight line, one kept aside the other.

Shop being magical, doesn’t let anyone pick snitch from any arbitrary position. If someone want to buy more than one snitch one can only pick contiguous segment of the items. And the cost of the segment is determined by the cost of each item in it. Alternatively Cost of segment from position l to r(inclusive) is.

Cost = Cl * Cl+1 + Cl+2 * Cl+3 +….. + Cr-1 * Cr if length of segment is even.

Cost = Cl * Cl+1 + Cl+2 * Cl+3 +….. + Cr-1 * Cr otherwise.

where C1,C2,C3,…..,Cn are the cost of each item from 1 to n.

Alice’s Dad has exactly k Rupees(Currency in India) and he wants to spend it all on Alice. Help Alice find the number of segments which she can afford to buy with k Rupees.

HackerEarth Buy ‘Em All problem solution.

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

#define ll long long int
#define MAX 100005
#define pb push_back
#define mp make_pair
#define MOD 1000000007

ll arr[100005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    map <ll, ll> m1, m2;
    ll l1 = 0, l2 = 0;
    ll ans = 0;
    m1[0]++;
    m2[0]++;
    for(int i = 2; i <= n; i++) {
        if(i&1) {
            l2 += arr[i]*arr[i - 1];
            ans += m2[l2 - k];
            m2[l2]++;
        }
        else {
            l1 += arr[i]*arr[i - 1];
            ans += m1[l1 - k];
            m1[l1]++;
        }
    }
    m1.clear();
    m2.clear();
    l1 = 0;
    l2 = 0;
    m1[0]++;
    m2[0]++;
    if(arr[1] == k) {
        ans++;
    }
    for(int i = 2; i <= n; i++) {
        if(i&1) {
            ll val = l1 + arr[i];
            ans += m1[val - k];
            l2 += arr[i] * arr[i - 1];
            m2[l2]++;
        }
        else {
            ll val = l2 + arr[i];
            l1 += arr[i]*arr[i - 1];
            ans += m2[val - k];
            m1[l1]++;
        }
    }
    cout << ans << endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

typedef complex<double> base;
typedef long double ld;
typedef long long ll;

#define pb push_back

const int LN=18,maxn=(1<<LN);
ll a[maxn],pre[maxn];
const ll mod=(ll)(1e9+7);
ld pi=2.0*acos(0.0);

int main()
{
    ios_base::sync_with_stdio(0);
    
    int n;ll k;cin>>n>>k;
    
    assert (n>=1 && n<=(int)(2e5));
    
    assert (k>=0 && k<=(ll)(1e18));
    
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        
        assert (a[i]>=0 && a[i]<=(ll)(1e6));
    }
    
    for(int i=n-1;i>=1;i--)
    {
        pre[i]=pre[i+2]+(a[i]*a[i+1]);
    }
    
    ll res=0;
    
    for(int i=n-1;i>=1;i--)
    {
        int low=1,high=(n-i+1)/2;
        
        while(low<high)
        {
            int mid=(low+high+1)>>1;
            
            ll now=pre[i]-pre[i+(mid*2)];
            
            if(now<=k)
            {
                low=mid;
            }
            else
            {
                high=mid-1;
            }
        }
        
        if(pre[i]-pre[i+(low*2)]<=k)
        {   
            //cout<<i<<" "<<low<<endl;
            
            res+=low;
        }
    }
    
    for(int i=n;i>=1;i--)
    {
        ll now=k-a[i];
        
        if(now>=0)
        {
            int low=0,high=(i-1)/2;
            
            while(low<high)
            {
                int mid=(low+high+1)>>1;
                
                ll zz=pre[i-(mid*2)]-pre[i];
                
                if(zz<=now)
                {
                    low=mid;
                }
                else
                {
                    high=mid-1;
                }
            }
            
            if(pre[i-(low*2)]-pre[i]<=now)
            {   
                //cout<<i<<" "<<(low+1)<<endl;
                
                res+=(low+1);
            }
        }
    }
    
    cout<<res<<endl;return 0;
}

coding problems solutions