EURON - Editorial

PROBLEM LINK:

Euron Problem

Practice
Contest

Author: Bhaumik Choksi
Tester: Dipen Ved
Editorialist: Bhaumik Choksi

Under KJSCE CODECELL

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Divide and Conquer

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.

1 Like

The Problem is same as: INVERSE_COUNT of SPOJ.

1 Like

I used the same approach. I get correct answer on the testcases and I also tried some test cases of my own . I get the correct answer in them also. Can someone have a look and point out what the error is?
https://www.codechef.com/viewsolution/32523149