A tricky twist on the classic find#inversions in array problem
The problem I have is an an admittedly difficult spin on the classic count number of inversions in an array problem. Essentially, you are given an array with 1<=n<=10^5 elements, with each element being in the range 1<=n<=10^5. For every i=0, 1...n-1, you must calculate the number of inversions in the array given that all elements greater than i are reduced to i.
Example:
Array {3, 1, 2, 5, 4}
i=0: 0 0 0 0 0 -> 0
i=1: 1 1 1 1 1 -> 0
i=2: 2 1 2 2 2 -> 1
i=3: 3 1 2 3 3 -> .....
i=....
If we were to use a binary indexed tree or merge sort to calculate the number of inversions, we would already be at nlogn, and since we must calculate the number of inversions for N such arrays, this would yield n^2logn, which is already too much. I noticed through small casework that many times, the number of inversions for a range of i's is the same, so maybe we can exploit some kind of monotonicity to select which i's to actually calculate. I tried seeing if the relationship between one element and the next dictated anything (if it was less or more), but if we try to filter what cases to calculate based on that, we leave out many cases, maybe if the term to the right is zero it may be the key, but I don't know how to implement that properly.
Example:
Array {3, 1, 2, 5, 4}
i=0: 0 0 0 0 0 -> 0
i=1: 1 1 1 1 1 -> 0
i=2: 2 1 2 2 2 -> 1
i=3: 3 1 2 3 3 -> .....
i=....
If we were to use a binary indexed tree or merge sort to calculate the number of inversions, we would already be at nlogn, and since we must calculate the number of inversions for N such arrays, this would yield n^2logn, which is already too much. I noticed through small casework that many times, the number of inversions for a range of i's is the same, so maybe we can exploit some kind of monotonicity to select which i's to actually calculate. I tried seeing if the relationship between one element and the next dictated anything (if it was less or more), but if we try to filter what cases to calculate based on that, we leave out many cases, maybe if the term to the right is zero it may be the key, but I don't know how to implement that properly.
Topic archived. No new replies allowed.