PROBLEM LINK:
Euron Problem
Author: Bhaumik Choksi
Tester: Dipen Ved
Editorialist: Bhaumik Choksi
Under KJSCE CODECELL
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
PROBLEM:
Euron loves to arrange things in order. Euron sticks to his “Golden rule” that every set of numbers must be in ascending order. Unfortunately, that is not always the case. Euron defines a “violation” as a situation when a smaller number comes after a larger number in the set, which violates the ascending order.
Given a set of integers, Euron needs to find out the total number of such violations.
QUICK EXPLANATION:
The problem can be solved by using a modified Merge-Sort algorithm, that counts the number of inversions while merging the sub-arrays, in addition to sorting the array.
EXPLANATION:
The merge-sort algorithm involves successively dividing an array into sub-arrays and merging them in a bottom-up manner, while sorting elements of each sub-array into place in the new combined array.
To solve this problem, we modify this algorithm to count the number of inversions at every merge step. Since sub-arrays are assumed to be already sorted, no inversion exist before the merge operation. The sum total of the inversions at each merge step gives the total number of inversion in the array.
//Modified Merge method.
static long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0;
long count = 0; //Initialize
while (i < left.length || j < right.length) {
//Loop till all elements in both subarrays are taken
if (i == left.length) {
arr[i+j] = right[j];
j++; //Left subarray was fully traversed
} else if (j == right.length) {
arr[i+j] = left[i];
i++; //Right subarray was fully traversed
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++; //Left element is less than Right element
//Hence, no inversion. No count increment.
} else {
arr[i+j] = right[j];
count += left.length-i;
//Increment count with the number of inversions
j++;
}
}
return count; }
AUTHOR’S AND TESTER’S SOLUTIONS:
Solution can be found here.