HackerEarth Jiraiya and Rasengan Attacks problem solution

In this HackerEarth Jiraiya and Rasengan Attacks problem solution, Naruto has started training from Jiraiya to develop the most powerful Rasengan attack. Jiraiya as always uses weird training exercises. Jiraiya has brought a permutation P of 1,2..N integers. He tells Naruto to sort the permutation using minimum number of Rasengan attacks. In one Rasengan attack Naruto can choose any pair of consecutive elements of the permutation and swap it.

To make the task a little difficult, he chooses a subsegment of the permutation uniformly at random PL, PL+1,..,PR (L ≤ R) and reverses it to make P1,P2,..,PL-1,PR,..,PL+1,PL,PR+1,..,PN. Now he asks Naruto to tell the expected number of Rasengan attacks he need to sort the permutation.

HackerEarth Jiraiya and Rasengan Attacks problem solution.

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define MOD 1000000007
#define LL signed long long int
#define MAX_N 100000
LL freq[MAX_N+5], A[MAX_N+1], sp[MAX_N+5];
LL read(LL *bit,int idx){
    LL sum = 0;
    if(idx==0)
        return 0;
    while (idx > 0){
        sum += bit[idx];
        sum %= MOD;
        idx -= (idx & -idx);
    }
    return sum;
}
void update(LL *bit,int idx ,int val){
    while (idx <= MAX_N){
        bit[idx] += val;
        bit[idx] %= MOD;
        idx += (idx & -idx);
    }
}
LL pow(LL base, LL exponent,LL modulus){
    LL result = 1;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
            result = (result * base) % modulus;
        exponent = exponent >> 1;
        base = (base * base) % modulus;
    }
    return result;
}
LL rangeQuery(LL *bit,int i,int j){
    return (read(bit,j) - read(bit,i-1) + MOD) %MOD;
}

int main(){
    int N;
    cin >> N;
    LL smallSum,largeFreq, largeSum, num = 0, inv = 0, total = N*1LL*(N+1)/2 % MOD;
    for(int i=1;i<=N; ++i) cin >> A[i];
    for(int i=1; i<=N; ++i){
        largeFreq = rangeQuery(freq,A[i],N);
        smallSum = rangeQuery(sp,1,A[i]) * (N-i+1) % MOD;
        largeSum = (total * largeFreq - rangeQuery(sp,A[i]+1,N) * (N-i+1)) % MOD + MOD;
        num = (num + largeSum + smallSum) % MOD;
        update(freq,A[i],1);
        update(sp,A[i],i);
    }
    cout<<(num * pow(total,MOD-2,MOD) %MOD);
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int MOD=1000000007;
int N;
int A[100001];

struct BIT
{
    long long bit[100001];
    void add(int x, long long v)
    {
        for(; x<=N; x+=x&-x)
            bit[x]+=v;
    }
    long long sum(int x)
    {
        long long ret=0;
        for(; x>0; x-=x&-x)
            ret+=bit[x];
        return ret;
    }
} b1, b2, b3;

int powmod(int a, int b)
{
    int ret=1;
    for(; b>0; b/=2)
    {
        if(b&1)
            ret=1LL*ret*a%MOD;
        a=1LL*a*a%MOD;
    }
    return ret;
}

int main()
{
    scanf("%d", &N);
    assert(2<=N && N<=100000);
    for(int i=1; i<=N; i++)
        scanf("%d", A+i);
    long long ans=0;
    for(int i=1; i<=N; i++)
    {
        long long x=b1.sum(A[i]);
        ans+=1LL*x*(N-i+1);
        ans%=MOD;
        b1.add(A[i], i);
    }
    long long ways=1LL*N*(N-1)/2+N;
    for(int i=N; i>=1; i--)
    {
        long long x=b2.sum(A[i]);
        long long t=b3.sum(A[i]);
        ans+=t*ways-1LL*x*i;
        ans%=MOD;
        b2.add(A[i], N-i+1);
        b3.add(A[i], 1);
    }
    printf("%lldn", ans*powmod(ways%MOD, MOD-2)%MOD);
    sort(A+1, A+1+N);
    for(int i=1; i<=N; i++)
        assert(A[i]==i);
    return 0;
}

coding problems solutions