How did u come up with this formula? Especially the k(k-1)/2 part.
Edit: Got it. Its the total number of pairs possible with k as elements.
Sum from 1 to n is (n*(n+1))/2
1 Like
cook your dish here
t=int(input())
for i in range(t):
n,k=map(int,input().split())
s=list(map(int,input().split()))
s1=sorted(s)
inv=0
for j in range(n):
c=0
if(j>=1):
x=s.index(s1[j])
for l in range(x+1,n):
if(s[x]>s[l]):
c+=1
inv = inv + ((ck)+((jk*(k-1))//2))
print(inv)
Here is the link :
https://www.codechef.com/viewsolution/27610275
Can anyone tell me mistake in my code, it is running correct for given test cases but on submitting, it gives wrong answer.
Pls let me know the mistake in it.
cook your dish here
t=int(input())
for i in range(t):
n,k=map(int,input().split())
s=list(map(int,input().split()))
s1=sorted(s)
inv=0
for j in range(n):
c=0
if(j>=1):
x=s.index(s1[j])
for l in range(x+1,n):
if(s[x]>s[l]):
c+=1
inv = inv + ((ck)+((jk*(k-1))//2))
print(inv)
Here is the link to it :
https://www.codechef.com/viewsolution/27610275
what is the mistake in this code ?
When will DDQUERY editorial will be published??
yeah correct excluding the array it is present, for that i am calculating val2.
1 Like
i think you are not calculating val2, as i suggested kindly look at the solution approach i have shared.
What I did here was made 2 variables, one contained the count of number of cases where A[i] > A[j] for i > j for each element in small array but only for the elements ahead of it. The other array kept a count for the same but comparison was done elements before a particular element as well as after it. And then ran a for loop for k times where a variable summed up such occurrences for each element. Might be a naive approach but it may help a newbie.
My submission: My submission for AC
Here c variable is working like val2 …
Calm down please, I understand your point. It’s just that I found another question that is exactly same to this one that’s why I pointed it out, I’m not accusing anyone or calling anyone “Problem thief” and you’re acting as if I just destroyed your career for no reason. I personally don’t think that anyone gives a damn about so called “Reputation of problem setters or anyone in particular on Codechef discuss”. What people care about most is improving their problem solving skills.
4 Likes
what is error in this code all test cases are going right but submission shows wrong answer
#include <stdio.h>
int main(void) {
// your code goes here
long long k,count,c,d,t,n,i,j;
scanf("%lld",&t);
while(t--)
{ count=0;
scanf("%lld",&n);
scanf("%lld",&k);
unsigned long long ar[n];
for(j=0;j<n;j++)
scanf("%llu",&ar[j]);
for(j=0;j<n;j++)
for(i=j+1;i<n;i++)
if(ar[j]>ar[i])
count++;
c=n*k*(n-1)*(k-1);
d=count*k+c/4;
printf("%lld\n",d);
}
return 0;
}
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.
1 Like
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;