Angry Battu
Problem:
practice
Tags: Divide and conquer.
Author: Shami.
The problem is just a paraphrase around computing inversions in an array. An inversion is a pair of elements in an array such that A[i] > A[j] when i < j.
The brute force way is to count all pairs. Complexity: O(N^2). This is not good enough for SubTask2.
Given that it requires comparing two elements, the lower bound will be same as lower bound for comparison sorting method i.e. Nlog(N).
Let’s break the array in two parts – left and right - and count the number of inversion in both. It still does not give us much information about number of inversions between left and right parts. However, if we sort both the parts, and then merge them, we can definitely tell the relative ordering between left and right. This algorithm works just like merge sort with an extra counter for inversions.