HackerEarth HP and Splitting of Array problem solution

In this HackerEarth HP and Splitting of Array problem solution, HP recently started learning about a property called inversion count. An inversion count of an array indicates how far from (or close to) being sorted the array is. If the array is already sorted, the inversion count is 0; if it’s sorted in reverse order, the inversion count is maximal.

Formally speaking, two elements and form an inversion if and . The inversion count is the number of pairs of indices such that and form an inversion.

You are given an array A with size N. Let’s denote an i-rotation of this array as the array formed by removing the first i elements from the array and adding (appending) them to the end of the array in the same order. HP wants to know the inversion counts of i-rotations of array A. Compute this inversion count for each i (1 <= i <= N).

HackerEarth HP and Splitting of Array problem solution.

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define nax 1000005

using namespace std;

long long ftree1[nax], ftree2[nax];
long long arr[nax];
long long temp[nax];
long long l[nax],r[nax];


void update(ll idx  ,ll *ftree)
{
    while(idx<nax)
    {
        
        ftree[idx]+=1;
        idx += (idx &(-idx));
    }
}
ll query(ll idx,ll *ftree)
{
    //cout<<idx<<"n";
    
    ll sum =0;
    while(idx!=0)
    {
        
        
        sum+=ftree[idx];
        idx -= (idx &(-idx));
        
    }
    return sum;
}

set<int> s;

int main()
{
    
    ll t,n,q,x;
    cin>>t;
    assert(t>=1 && t<=10);
    while(t--){
        
        
        cin>>n;
        assert(n>=1 && n<=100000);
        
        memset(ftree1,0,sizeof(ftree1));
        memset(ftree2,0,sizeof(ftree2));
        
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            assert(arr[i]>=1 && arr[i]<=1000000);
            
            if(!i)
                l[i]=(query(nax-1,ftree1)-query(arr[i],ftree1));
            else
            {
                l[i]=l[i-1]+(query(nax-2,ftree1)-query(arr[i],ftree1));
            }
            
            update(arr[i],ftree1);
            
        }
        
        r[n] = 0;
        for(int i=n-1;i>=0;i--)
        {
            if(i==n-1)
                r[i]=query(arr[i],ftree2);
            else
            {
                r[i]=r[i+1]+query(arr[i],ftree2);
            }
            update(arr[i],ftree2);
            
        }
        
        
        
        
        
        for(int i=1;i<=n;i++)
        {
            int x = i-1;
            
            ll total = (n-x-1)*(x+1);
            ll ans;
            ans = 2*l[x]+2*r[x+1] + total - r[0];
            
            
            cout<<ans<<" ";
            
        }
        cout<<"n";
        
    }  
    
}

Second solution

#include <bits/stdc++.h>
#define MAX 1000005
#define lli long long

using namespace std;

int A[MAX];
lli BIT[MAX];
lli ans[MAX];

void update(int idx, int val)
{
    while ( idx <= MAX - 4 ) {
        BIT[idx] += val;
        idx += (idx & (-idx));
    }
}

int query(int idx)
{
    int ret = 0;
    while ( idx > 0 ) {
        ret += BIT[idx];
        idx -= (idx & (-idx));
    }
    return ret;
}
int main()
{
    int n, q, x,t;
    cin>>t;
    while(t--){
    
    lli inv = 0;
    cin >> n ;
    memset(BIT,0,sizeof(BIT));
    
    
    
    for ( int i = 1; i <= n; i++ ) {
        cin >> A[i];
        assert(A[i] >= 1 && A[i] <= 1000000);
    }
    
    for ( int i = n; i >= 1; i-- ) {
        inv += query(A[i] - 1);
        update(A[i], 1);
    }
    
    for ( int i = 1; i <= n; i++ ) {
        inv -= query(A[i] - 1);
        inv += query(MAX - 5) - query(A[i]);
        ans[i] = inv;
    }
    
    
    for(int i=1;i<=n;i++) {
        
        
        cout << ans[i] << " ";
    }
    cout<<endl;
    }
    
    
    return 0;
}

HackerEarth HP and Splitting of Array problem solution

HackerEarth HP and Splitting of Array problem solution.

Second solution

Leave a Reply

Pages

Practice