PROBLEM LINK:
Practice
Encoding December 2020
Author: Akash Kumar Bhagat
Tester: Arnab Chanda
Editorialist: Akash Kumar Bhagat
DIFFICULTY:
Medium
PREREQUISITES:
Maths, Divide and Conquer
PROBLEM:
You are given an array of numbers A of length N containing distinct integers from the range [1, N]. If we have 2 different sets of N numbers and we connect the i^{th} number from the first to the number i in another set, then count the number of intersections.
EXPLANATION:
This is the typical question of divide and conquer algorithm which is also referred to as the Inversion Problem. One of the way to solve os using merge sort approach and repeatedly divide the array in half until the base case is reached
We can create a function that counts the number of inversions when two halves of the array are merged, create two indices i and j, i is the index for the first half and j is an index of the second half. if a[i] is greater than a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
Create a recursive function to divide the array into halves and find the answer by summing the number of inversions is the first half, number of inversion in the second half and the number of inversions by merging the two. The base case of recursion is when there is only one element in the given half.
You can refer to this article
TIME COMPLEXITY: O(n \log_2 n)
SOLUTIONS:
Python 3.7
def Sort_n_Count(arr):
n=len(arr)
if(n==1):
return arr,0
count=0
temp1,x=Sort_n_Count(arr[:n//2])
temp2,y=Sort_n_Count(arr[n//2:])
count+=x+y
i,j=0,0
len1=n//2;len2=n-n//2
sorted_array=[]
while(i!=len1 and j!=len2):
if(temp1[i]<=temp2[j]):
sorted_array.append(temp1[i])
i+=1
else:
sorted_array.append(temp2[j])
j+=1
count+=len1-i
while(i!=len1):
sorted_array.append(temp1[i])
i+=1
while(j!=len2):
sorted_array.append(temp2[j])
j+=1
return sorted_array,count
for i in range(int(input())):
n,x=map(int,input().split())
a=[int(i) for i in input().split()]
print(2*x*Sort_n_Count(a)[1])
CPP
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define F(i,a,n) for(long long int i=a;i<n;i++)
#define FO(i,a,n) for(long long int i=n-1;i>=a;i--)
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define M 998244353
#define pb(i) push_back(i)
#define len(s) s.length()
#define mp make_pair
#define ss second
#define ff first
#define vll vector<long long int>
#define vpair vector<pair<long long int,long long int>>
#define MAX 100000
#define tolernace 1e-10
using namespace std;
//*******************************************************************
void input()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
ll power(ll a, ll b)
{
ll ans = 1;
while (b > 0)
{
if (b & 1)
{
ans = ans * a;
}
a = a * a;
b >>= 1;
}
return ans;
}
ll gcd(ll a, ll b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
//********************************************************************
ll merge(ll arr[], ll temp[], ll left, ll mid, ll right)
{
ll inv_count = 0;
ll i = left; /* i is index for left subarray*/
ll j = mid; /* i is index for right subarray*/
ll k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
/* this is tricky -- see above explanation/
diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
ll _mergeSort(ll arr[], ll temp[], ll left, ll right)
{
ll mid, inv_count = 0;
if (right > left)
{
mid = (right + left) / 2;
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid + 1, right);
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}
ll countSwaps(ll arr[], ll n)
{
ll temp[n];
return _mergeSort(arr, temp, 0, n - 1);
}
void solve()
{
ll n, k = 1, x;
cin >> n >> x;
ll a[n];
F(i, 0, n)
{
cin >> a[i];
}
cout << countSwaps(a, n) * 2 * x;
}
//*******************************************************************
int main()
{
fast()
input();
// ll x = 1;
int t = 1, i = 1;
cin >> t;
while (t--)
{
solve();
cout << endl;
}
}
//*******************************************************************
Fenwick tree
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define INF 2000000000000000000
#define popcount(x) __builtin_popcountll(x)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define ld long double
const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);
template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p)
{
return os<<'('<<p.F<< ","<<p.S<<')';
}
const int N = 100005;
template<typename T=long long>
struct fenwick {
T a[N],bit[N];
int n;
fenwick()
{
for(int i=1;i<=N-2;++i)
a[i] = T(0),bit[i] = T(0);
}
void build(int n_)
{
n = n_;
for(int i=1;i<=n;++i)
bit[i] = 0;
}
void update(int j,T val)
{
for(;j<=n;j+=j&-j)
bit[j] += val;
}
T get(int r)
{
T u = 0;
for(;r;r-=r&-r)
u += bit[r];
return u;
}
T query(int l, int r)
{
return get(r)-get(l-1);
}
};
fenwick<ll> fenw;
// call fenw.build(n);
int _runtimeTerror_()
{
int n;
ll x;
ll ans = 0;
cin>>n>>x;
fenw.build(n);
for(int i=1;i<=n;++i)
{
int x;
cin>>x;
ans += fenw.query(x+1,n);
fenw.update(x,1);
}
ans *= 2*x;
cout<<ans<<"\n";
return 0;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef runSieve
sieve();
#endif
#ifdef NCR
initialize();
#endif
int TESTS=1;
cin>>TESTS;
while(TESTS--)
_runtimeTerror_();
return 0;
}
SOLUTION CREDIT
CPP → @horcrux903
Fenwick Tree → @anshugarg12
Hope you have enjoyed Encoding December 2020, we are eager to know your approach to the problem. 