PROBLEM LINK:
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;
}
}