How to solve the "Permuatations and Inversions" from Hackerearth?

help
, , ,
1

I am trying to solve the Permutations and Inversions problem using BIT.

It is easy to find the total number of inversions in all the left shifts of the array.

But how to get the xor of all those inversion counts?

I would be happy if someone could provide some hints or explain this code of some coder submission.

AC Submission of some guy: Submission (26614478) for Permutation and Inversions | HackerEarth

Thank you :slight_smile:

2

It’s easy to find the number of inversions. Now when we put the last number x in the front, We remove n-x and add x-1 inversions. This is easy to see because there are n-x numbers greater than x, so those are now in front of x, and were before x, therefore we lose n-x inversions. There were x-1 numbers less than x which were before x, and are now after x, therefore the number of inversions increases by x-1.

Also why would you use fenwick tree over pbds to find inversions. The latter takes 4 lines to code.

My solution 
#include <iostream>
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define mp make_pair
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using indexed_set = tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update>;
void solve(){
    int n;
    cin>>n;
    vector<int> seq(n);
    for(auto &x : seq){
        cin>>x;
    }
    ll inv = 0;
    indexed_set curr;
    for(const auto &x : seq){
        inv+=curr.size() - curr.order_of_key(x);
        curr.insert(x);
    }
    ll ans = inv;
    for(int i=n-1;i>0;--i){
        inv-=n+1-2*seq[i];
        ans^=inv;
    }
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
2 Likes
3

I am not getting your idea. Could you please explain your idea with this arr = { 1, 5, 2, 4, 3 }. Thank you :slight_smile:

4

When you remove 3 from the back, you lose n-x = 2 inversions, \{5,3\}, \{4,3\}, and gain x-1 = 2 inversions, \{3,1\},\{3,2\}.

5

Yeah! I got it. I forgot to see that 1<=P<=N constraint, that’s why i didn’t understand that. I should have read the constraints properly. Thank you :slight_smile:

6

Yeah pdfs is preferrable but i just wanted to do it with BIT

7

Also, When we remove from the front we lose x-1inversions overall and adds n-x inversions overall, but the final answer would be the same. I mean xor as left and right shifts are analogous