INVYCNT October Lunchtime Help

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 ?:sob:

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 :joy::+1::+1:

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)
@deepak_2431

Ah, I figured out the pattern with copy and pen :sweat_smile: 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!:sweat_smile: 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