INVYCNT Editorial

PROBLEM LINK:

Practice
Contest

Author & Editoralist: Jafar Badour
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

DIFFICULTY:

Easy

PREREQUISITES:

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)
    now your ans would be
    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.

Link please?
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

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.

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) {
// 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;

}