Hi everyone,
I am working as software developer with 4+ years of experience, I’m very new to competitive programming. But doing it whenever i get time…
Coming to the question, today i participated in October Lunchtime, so i started with this problem . I could be able to do the brute force, but didn’t get any thought to optimize it.
Then, after the contest i went through the submissions and found this code.
I have gone through the code, traced it on the paper to get the intuition or logic behind it, but sadly i couldn’t understand the logic.
Can someone please explain the intuition behind this ??
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll i,j,k,m,n;
ll a,b,c,t;
cin>>t;
while(t--)
{
cin>>n>>k;
ll ar[n];
for(i=0;i<n;i++)
cin>>ar[i];
ll ctr=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(ar[i]>ar[j])
ctr++;
}
ll ans=ctr*(k*(k-1))/2;
ctr=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
if(ar[i]>ar[j])
ctr++;
}
cout<<ctr*k+ans<<endl;
}
}