# INVYCNT Editorial

Tester: Teja Reddy

### PROBLEM EXPLANATION

Almir had a small sequence A_1, A_2, \ldots, A_N. He decided to make K copies of this sequence and concatenate them, forming a sequence X_1, X_2, \ldots, X_{NK}; for each valid i and j (0 \le j \lt K) :: X_{j \cdot N + i} = A_i.

For example, if A = (1, 2, 3) and K = 4, the final sequence is X = (1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3).

A pair (i, j), where 1 \le i \lt j \le N, is an inversion if X_i \gt X_j. Find the number of inversions in the final sequence X.

1 \leq N \leq 100

Easy

None

### EXPLANATION:

Find inversions count in our starting array A. This can be done in O(N^2) easily with 2 loops and letâ€™s denote this count with P.
Clearly, since we are gonna repeat the same array K times, we would have P*K inversions.
What else should we consider?
We should consider inversions resulting from two elements with indices a,b belonging to 2 different pieces (by piece we mean one of the concatenated arrays).
The number of inversions resulting from concatenating A with itself (once) is equal to the number of pairs of different numbers in a single copy of A. Letâ€™s denote this count with Q.
When appending the i_{th} copy of A to our final array X our answer would increase by (i-1)*Q

ans = P*K + \sum_{i=1}^{i=K-1} Q

ans = P*K+K*(K-1)/2*Q

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int T , n , K;
int arr[200];
int main(){
cin>>T;
while(T--){
cin>>n>>K;
int a = 0 , b = 0;
for(int j = 1 ; j <= n ; j++){
cin>>arr[j];
for(int i = 1 ; i < j ; i++){
if(arr[i] != arr[j]) ++a;
if(arr[i] > arr[j]) ++b;
}
}
cout<<1ll * K * b + 1ll * a * K * (K - 1) / 2<<endl;
}
}


Iâ€™m trying to understand the explination to this question, but I canâ€™t understand the meaning of "The number of inversions resulting from concatenating A with itself (once) is equal to the number of pairs of different numbers in a single copy of A. ".

Why are we intrested in finding -> if(arr[i] != arr[j]) ++a; ?

3 Likes

hey, letâ€™s take it simple.
for our original array letâ€™s find 2 things.

1. for every index i, number of integers which are less than array[i].(val1)
2. for every index number of integers that are less than array[i] and also their index greater than i.(val2)
for every index from 1 to n
ans+=((val1*(k) (k-1))/2+kval2.)
if you dry run it. you will know how this formula is working.
3 Likes

This question has been taken from an Atcoder challenge in the past.

Thanks

1 Like

pls provide the link to the question, if u are sure

There you goâ€¦

3 Likes

I am so surprised by this fact. Personally I donâ€™t have an atcoder account. and I donâ€™t know every problem in the world to avoid such thing. This problem difficulty is div2a in codeforces, so take it easy, I wouldnâ€™t be surprised if you find something similar somewhere else.

I have enough skill to create an easy task suitable for 2/7 in codechef in short time (or you can prove me wrong if you can) rather than copying such an easy task and putting myself into such awkward position. So if thereâ€™s another problem asking for sorting and dividing array into 4 parts itâ€™s also copying the easiest task? I believe there are tons of questions that ask for something close or even same.

When 2 hard tasks are similar you can accuse of copying, because itâ€™s hard to match with details of hard question. During preparation, easy tasks were missing, and I tried to tweak INVZCNT and somehow I had this idea of concatenating arrays.

I hope this makes it clear. Honestly I tried to google with few keywords like â€śinversions,concatenating,concatenationâ€ť and I couldnâ€™t come up with such question.

People get better in problem solving by solving a lot, and they tend to solve easy tasks because they encountered the same idea before and before. Personally I solved ~3000 problems in my life, so the chances of me finding a repeated task are not so low. When I do, I donâ€™t accuse people of stealing the easy task. Especially when other questions in the contest are much much harder to come up with (why would they copy!).

You shouldnâ€™t accuse people of stealing like this, you are showing no respect to them. I donâ€™t want to justify anymore. Such situation happened a lot before even in big contests (codejam world finals, ICPC finals, codeforces div1E) and it was never like â€śoh look this guy is a problem thief,letâ€™s ruin his reputationâ€ť. This was in very very hard competitions. I donâ€™t think itâ€™s wise to say that for such an easy task.

7 Likes

OMG, Thank you.

1 Like

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

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)

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.

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.

3 Likes

what is error in this code all test cases are going right but submission shows wrong answer

#include <stdio.h>

int main(void) {

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;


}