In this HackerEarth Vanya and Array problem solution Let's define 2 functions a function F(i) and Val(i,j) for an Array A of size N as follows:

 F(i) = Sigma(j=i+1, N) Val(i,j)

 Val(i,j) = 1 ,if A[i] < A[j], else, Val(i,j) = 0.

Now, Vanya has been given one such array A of size N and an integer K. She needs to find the number of Distinct Unordered Pairs of elements (a,b) in array A such that F(a) + F(b) >= K.


HackerEarth Vanya and Array problem solution


HackerEarth Vanya and Array problem solution.

import java.io.*;
import java.util.*;
public final class vanya_and_array
{
static long[] bit;
static int maxn=1000015;
static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out=new PrintWriter(System.out);

static void update(int idx)
{
while(idx<maxn)
{
bit[idx]++;
idx+=idx&-idx;
}
}

static long query(int idx)
{
long sum=0;
while(idx>0)
{
sum=sum+bit[idx];
idx-=idx&-idx;
}
return sum;
}

public static void main(String args[]) throws Exception
{
int n=sc.nextInt(),k=sc.nextInt();
int[] a=new int[n],b=new int[n];bit=new long[maxn];
for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();
b[i]=a[i];
}
Arrays.sort(b);
for(int i=0;i<n;i++)
{
a[i]=Arrays.binarySearch(b,a[i])+1;
}
long[] val=new long[n];
for(int i=n-1;i>=0;i--)
{
val[i]=query(maxn-1)-query(a[i]);
update(a[i]);
}
Arrays.sort(val);
long res=0;
for(int i=n-1;i>0;i--)
{
int low=1,high=i;
while(low<high)
{
int mid=(low+high+1)>>1;
if(val[i]+val[i-mid]>=k)
{
low=mid;
}
else
{
high=mid-1;
}
}
if(val[i]+val[i-low]>=k)
{
res=res+((i-1)-(i-low)+1);
}
}
out.println(res);
out.close();
}
}
class FastScanner
{
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int getSum(int BITree[], int index)
{
int sum = 0;
while (index > 0)
{
sum += BITree[index];
index -= index & (-index);
}
return sum;
}
void updateBIT(int BITree[], int n, int index, int val)
{
while (index <= n)
{
BITree[index] += val;
index += index & (-index);
}
}
void convert(int arr[], int n)
{
int temp[n];
for (int i=0; i<n; i++)
temp[i] = arr[i];
sort(temp, temp+n);int i;
for (i=0; i<n; i++)
{
arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
arr[i]=n-arr[i]+1; //changing largest element as smallest and so on, later we need to apply simple inversion count
}
}
int f[1000005];
void getInvCount(int arr[], int n)
{
int invcount = 0;
convert(arr, n);
int BIT[n+1];
for (int i=1; i<=n; i++)
BIT[i] = 0;
for (int i=n-1; i>=0; i--)
{

f[i]= getSum(BIT, arr[i]-1);
updateBIT(BIT, n, arr[i], 1);
}
}
int main()
{
int n,k,i,a[1000005];
scanf("%d%d",&n,&k);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
getInvCount(a,n);
sort(f,f+n);long long count=0;
vector<int>v(f,f+n);
for(i=n-1;i>=0;i--)
{
int j=lower_bound(v.begin(),v.end(),k-v[i])-v.begin();
if(j!=n && j<i)
count+=i-j;
}
printf("%lld\n",count);
return 0;
}