INVYCNT Editorial

editorial
,
22

Because these are the part of all possible inversions when array is concatenated.

23

Please do tell me whatā€™s wrong in my solution.

25

hey,
you have to calculate p and q separately for every index, not overall.
have a look at my approach again, itā€™s mentioned to calculate for every index.

26

Bro I rectified my code. I ran all the possible test cases and matched my answer with the setterā€™s code and they were correct. Then I checked for the last test case. I took extreme cases and saw my answer didnā€™t match. Then I changed data type from int to long long int. Then my code got accepted. But thanks bud. I went with my approach only.

1 Like
27

ohh fine, I must have looked closely into your solution. Kudos!

28

My solution:

example : if N = 3 and A[] = {1, 2, 3} and K = 4 then,
we donā€™t need to make a repeated array of K times.
we will just assume K=2 and build the array of 2 * N size.
then array will be A = {1, 2, 3, 1 ,2, 3}
will will count if A[i] > A[j] and for every i we will take there count value
in an another array A_2.

then we will apply arithmetic series formulas toh find the Kth value of an element a_nth = a1 + (n-1) * d and then sum of series sum = ((a_1 + a_nth) * n) / 2 in array A_2. the total sum for every element in A_2 will be the answer!
Thanks! :slightly_smiling_face:

hereā€™s the solution : CodeChef: Practical coding for everyone

29

Can anyone explain where my code is failing?

#include <bits/stdc++.h>
#define si(t) scanf("%d",&t)
#define sl(t) scanf("%lld",&t)
#define sll(t,w) scanf("%lld %lld",&t,&w)
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long int
#define MOD 1000000007
using namespace std;

long long int inversion_count(long long int[], int);
long long int count_pairs(long long int[], int);

int main() {
    SPEED;
	int t, n, k, i, inv_count;
	long long int ans;
	long long int arr[100] = {0};
	cin>>t;
	while(t--){
	    cin>>n>>k;
	    for(i=0;i<n;i++) {
	        cin>>arr[i];
	    }
	    inv_count = inversion_count(arr, n);
	    // cout<<"Inv Count: "<<inv_count<<'\n';
	    // ans = inv_count + (k-1)*k*n/2;
	    ans = k*inv_count + k*(k-1)*n*(n-1)/4;
	    cout<<ans<<'\n';
	}
	return 0;
}

long long int inversion_count(long long int arr[], int n) {
    long long int count = 0;
    int i, j;
    for(i=0;i<n;i++) {
        for(j=i+1;j<n;j++) {
            if (arr[i] > arr[j]) {
            	// cout<<arr[i]<<' '<<arr[j]<<'\n';
            	++count;
            }
        }
    }
    
    return count;
}

long long int count_pairs(long long int arr[], int n) {
	long long int count = 0;
	int i, j;
	for(i=0;i<n;i++) {
		for(j=0;j<n;j++) {
			++count;
			if (arr[i] == arr[j])
				--count;
		}
	}
	
	return count;
}
30

i didnā€™t understand this part of the question??? what is the meaning?

A pair (i, j), where 1 <= i<=j<=n, is an inversion if X_i > x_j . Find the number of inversions in the final sequence X.

31

another Q when i use mod to solve the question(cause i thought it would over flow it showed WA but removing mod it gave correct answer)

ll ans = (count1 *k)+ count2*(k*(k-1)/2);

above one gave correct
while below one gave wrong
where my mod is

const unsigned int mod = 1e9+7;

ll ans = (count1 *k) % mod+ count2*(k*(k-1)/2) % mod;