1 tc giving TLE in Alpha Score problem

#1

my sol : https://ide.codingblocks.com/s/245423

ques : https://hack.codingblocks.com/app/contests/1463/965/problem

i m not able to think how to further optimize my code.

Pls help me optimize my code !!.

#2

hello @saarthakseth
logic is similar to inversion count.
To solve this problem in a best-optimized way need to think something better than O(n*n). Here we will apply the concept of merge sort problem.
In merge sort, we divide the array into subarrays recursively until there are just 2 elements in a subarray. We then arrange the subarray in sorted order and merge it with other subarrays.

Consider 2 subarrays arr[l…mid-1] and arr[mid…r] in the merge function which are sorted seperately and are ready to merge

i varies from l to mid-1

j varies from mid to r

i<j always

Let sum be the variable which holds the sum of all the numbers previously seen on the stairs which are smaller than the present number.

if(arr[i]<arr[j])

arr[i] comes before arr[j] in the input array and arr[i] is less than arr[j]. So we have to add arr[i] to sum.

Since arr[i]<arr[j], arr[i]<(arr[j+1], arr[j+2],….,arr[r]) because the subarrays to be merged are sorted.

So on the whole (r-j+1) times of arr[i] is added to the sum.

code -> https://ide.codingblocks.com/s/245435

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.