Alpha Score Problem

#1

Sir, Why am I getting TLE in 1 Test Case

Solution Link-https://ide.codingblocks.com/s/66016

#2

Hi,

You have incorrectly written the crosscount function.
They way you are counting cross count is wrong way. you doing this is complexity n^2 *(log n)

Please see inversion count again it is done in n*(long n)

Hit like if you get it!

#3

Solution Link- https://ide.codingblocks.com/s/66015
Sir Now i am using array which stores prefix sum then also gettint TLE in 1 test case.
Complexity now must be n*logn . How can i optimise my code further.

#4

You Cross cout fucntion should be like this

int merge(int arr[], int temp[], int left,
int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))  
{  
    if (arr[i] <= arr[j]) 
    {  
        temp[k++] = arr[i++];  
    }  
    else 
    {  
        temp[k++] = arr[j++];  

        /* this is tricky -- see above  
        explanation/diagram for merge()*/
        inv_count = inv_count + (mid - i);  
    }  
}  

/* Copy the remaining elements of left subarray

(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray

(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)  
    arr[i] = temp[i];  

return inv_count;

}

Try to this logic of code.
Hit like if you get it!

#5

Thanks for paying attention but I am not getting it

Problem Link-https://hack.codingblocks.com/submission/1893533

Code marked tricky is helpful if we have to find total pairs but actually i have to find sum of smaller numbers so i am using prefix sum ( which is O(1) operation). Your code is for inversion count basic problem, which I suppose is crystal clear to me. In Inversion count, array is sorted in increasing order where in ALPHA SCORE problem i have sorted array in descending order.

I am getting TLE in only 1 test case.