I solved it using the below code but I am getting WA. Please help if approach or code is wrong.
https://www.codechef.com/viewsolution/27576200
https://www.codechef.com/viewsolution/27577471
Failing test case:
2
3 3
1 1 1 3 3
1 1 2
Expected Output:
0
6
My solution:
ans = calculate_inversions(array)*k
sort(arr)
duplicates = n - length(set(arr))
if duplicates != n - 1:
ans += ((n*(n-1) // 2) - duplicates) * (k*(k-1) // 2)
print(ans)
1 Like
Can anyone please give any test case for which my solution is wrong ? I am getting WA and have checked all possible test cases as far as i could think.
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
int n;int l;
cin >> n >> l;
vector <int> v;
for (int i = 0;i < n;i++) {
int l;
cin >> l;
v.push_back(l);
}
int def = 0;
for (int i = 0;i < n;i++) {
for (int j = (i+1);j < n;j++) {
if (v.at(j) < v.at(i))
def++;
}
}
sort(v.begin(), v.end());
vector<int>::iterator lower;
int k = 0;
for (int i = 0;i < n;i++) {
lower = lower_bound(v.begin(), v.end(), v.at(i)) ;
k = k+(lower - v.begin());
}
int sum = 0;
def = def * l;
l--;
sum = (l * (l + 1) / 2);
sum = sum * k;
sum = sum + def;
cout <<sum<<endl;
}
}hey bro, can you please have a look at my code too ? I have checked the above test case which you gave for the OP. please.
https://www.codechef.com/viewsolution/27577362
Here is my solution if anyone want explaination , i will @vishalg8454
PS : Read from line 329 to 349
1 Like
Thank you , I will be waiting…
should i explain right now?
yes bro, but I will likely be unable to get good sleep if I am not able to find why i got WA ?
int main(){
fastIO
lli t=1;
cin>>t;
while(t--){
lli n,k;
cin>>n>>k;
lli a[n];
scanarr(a,n);
lli sum=0;
for(lli i=0;i<n;i++){
lli age=0,piche=0;
for(lli j=i-1;j>=0;j--){
if(a[i]>a[j])
piche++;
}
for(lli j=i+1;j<n;j++){
if(a[i]>a[j])
age++;
}
sum+=(age*((k*(k+1))/2))+(piche*((k*(k-1))/2));
}
cout<<sum<<endl;
}
The test case this fails for:
1
5 5
1 2 3 1 1
Expected output: 100
Your output: 90
Thank you, there can’t be any variable name self explanatory than this 
1 Like
Can you explain that formula which you have used to calculate the answer? I am not getting why that formula is used and why the inversions is calculated from both side. Please explain the solution in detail!
Ah, finally I could sleep. Thank you so much !
count for each element such that for how many values it is greater than previous one ( i called them " piche " ) , similarly , count for each element such that for how many values it is greater than next one ( i called them " aage " )
Now for next values count (aage walo ke liye) total values is age*((k*(k+1))/2)
and for prev values count (piche walo ke liye) total values is piche*((k-1)*(k)))/2)
@anon20971295
Ah, I figured out the pattern with copy and pen 
probably which would be difficult to explain for me as well. Also my solution is incorrect so need to work on it!
https://www.codechef.com/viewsolution/27594229
this is my solution and it fails the test case you have given but i want to know that how can i know that which test case my code is failing
Sorry bro, everything is correct. Actually I had the data type as int instead of long int so the problem! Thanks you guys for the help @ssrivastava990
here is my AC code
#include
#include<bits/stdc++.h>
#include
#include<math.h>
#define int long long
#define foi(n) for(int i=0;i<n;i++)
using namespace std;
//??UVAISH ZAFRI??******
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
cin>>test;
while(test–)
{
int n,k;
cin>>n>>k;
int a[n];
foi(n)
cin>>a[i];
int count=0;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
if(a[i%n]>a[j%n])
count+=1;
}
if(k==1)
cout<<count<<endl;
else{
//count for one
int b[n];
for(int i=0;i<n;i++){int tempcount=0;
for(int j=0;j<n;j++)
{
if(i!=j&&a[i]>a[j])
tempcount+=1;
}
b[i]=tempcount;
//cout<<b[i];
}
int tempcount=0;
tempcount=accumulate(b,b+n,0);
int res=count;
while(k>=2){res+=(count+(k-1)*tempcount);k–;}
cout<<res<<endl;
}
}
return 0;
}
What about this code? Please correct me if I have implemented your logic in a wrong way.
https://www.codechef.com/viewsolution/27595764
Here is my solution, You can extract logic by going through once.
https://www.codechef.com/viewsolution/27592531