ENCDEC8- Editorial

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. :blush::blush::blush:

1 Like