Because these are the part of all possible inversions when array is concatenated.
Please do tell me whatās wrong in my solution.
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.
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.
ohh fine, I must have looked closely into your solution. Kudos!
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!
hereās the solution : CodeChef: Practical coding for everyone
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;
}
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.
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;