CHEFINV - Editorial

chefinv
editorial
fenwick
inversions
medium
sept14

#1

Problem link : contest practice

Difficulty : Medium

Pre-requisites : Fenwick tree

Solution:

Unlike the version when we swap the elements permamently, this one has an O(M log N) solution. The simplest solution is the offline one. That means that we’ll first read all the queries at once, then we’ll do something and then we’ll output all the answers at once. The online solution is also possible, and it involves persistent data structures.

At first we need to calculate the number of inversions in the initial array.

Consider the situation when we have to swap two elements of the array, say the L-th and the R-th one. In order to deal with such a query, we will act in two steps:

  • First, we will decrease the number of inversions by the number of inversions that has the L-th element of the initial array. Then, we will decrease the number of inversions by the number of inversions that has the R-th element of the initial array. Note that if the pair (L, R) forms the inversion then it will be considered twice. So, we need to handle this case;
  • Second, we can swap the L-th and the R-th elements and then add the number of inversions that contain these elements.

So now, the problem is to count the number of inversions that contain some exact element. Let it be the X-th element. This number will be equal to the amount of the numbers that has indexes that are smaller than X but are greater than aX plus the amount of numbers that has indexes greater than X but are smaller than aX. Here we denote the X-th element of the array by aX.

How to do it quickly? We can reduce this problem to another one. Consider a set of N points on a plane. Let the coordinates of the i-th point be (i, ai). Then, the amount of
numbers that has smaller indexes than X and are greater than aX equals to the number of points in the axes-parallel rectangle with the following bottom-left and top-right corners: (1, aX+1) and (X-1, N). Similarly, the amount of numbers that has indexes that are greater than X and are smaller than aX is the amount of points in the axes-parallel rectangle with the following corner points: (X+1, 1) and (N, aX-1).

How to calculate the number of points inside of the rectangle fast?

Here is the offline approach key points:

  • The amount of points in the axes-parallel rectangle with the bottom-left and top-right points with the coordinates (x1, y1) and (x2, y2) respectively (let’s call it F(x1, y1, x2, y2)) equals to F(1, 1, x2, y2)-F(1, 1, x1-1, y2)-F(1, 1, x2, y1-1)+F(1, 1, x1-1, y1-1), so now we can operate only in rectangles that has (1, 1) as the bottom-left corner.
  • Since we always have the bottom-left corner equal to (1, 1), we can iterate through all the possible X-coordinates and add all the points that has the current X-coordinate - there will be only one point for each X-coordinate, in fact. By add we mean adding the point’s Y-coordinate in the Fenwick tree. Then, before we add the points with the greater X-coordinates, we can answer all the queries that has this X-coordinate and the X-coordinate of the top-right corner. For the reasons, similar to the described above, the answer will be equal to some prefix-sum in the fenwick tree.

The complexity of above solution is O(N log N).

But there is also an online solution that has the same complexity. The key idea is the same, but we count the amount of points inside the rectangles in the different way. Here you can find a very comprehensive tutorial, related to calculation the number of points inside axes-parallel rectangle in O(log N) time on-line.

Setter’s solution: link

Tester’s solution: link


#2

A better and shorter method to do it is using Fractional Cascading on Segment tree (to be precise merge sort tree).


#3

I solve it by segment tree but i got wrong answer i generate random test case upto 2*10^5 and check it file input output but i could not get any test case where i was wrong
Can you please help me where my code fail :frowning: :frowning:
http://www.codechef.com/viewsolution/4823968


#4

I used extended merge sort and segment tree for this where each of my query was logn^2 (4logn^2 to be precise). So overall solution was of MlgN^2 . This seems acceptable given 1 sec time limit. why I got tle???
http://www.codechef.com/viewsolution/4806941


#5

It was possible with a Fenwick tree I guess also. So you do two updates and get the new inversion count. Then discard the updates. Two updates would be to change A[x] to A[y] and A[y] to old A[x]. Then start fresh on new query.


#6

I have one (off topic) question.

To count the no. of inversion in array I am using BIT. This algorithm is well known and shown in this link

Suppose we have A={9,6,8,1000}. For this we need an array (say BIT) of length N, where N is the maximum number in array A (1000 here). But this algo requires the memory O(N). What what if A consist of very big number say 10^9. I am getting ‘java.lang.OutOfMemoryError’ while declaring BIT[10^9]. Is there any way to overcome with this?


#7

Can segment tree work…I got wa with segment tree…??


#8

Hi

I’m curious about one thing. What if the queries were permanent? As in the swaps were permanent and the subsequent queries should be answered accordingly. Can the same technique be used or some modifications are required?

Thanks :slight_smile:


#9

What is meant by the line :

By add we mean adding the point’s Y-coordinate in the Fenwick tree.

Also how is this link related to calculation of no of points inside an axis parallel rectangle??


#10

Because MlogN was expected. That is the very reason why I used fractional cascading along with merge sort tree. Mergesort tree alone wouldnt do…


#11

what will be the complexity for that? and space requirements?


#12

map these to shorter range i.e. A= {9,6,8,1000} can be mapped to B={3,1,2,4}.
What you can do is sort A to get intermediate array = {6,8,9,1000} then map 6 to 1, 8 to 2, 9 to 3 and 1000 to 4 and then use this map and A to get B


#13

@ajaytank try for compression thing try to compress the values in range of 2*10^5


#14

@adijimmy I would be thankful to you if you post any link related to compress the values :slight_smile:


#15

@ajaytank http://pavelsimo.blogspot.in/2012/09/counting-inversions-in-array-using-BIT.html
compression is explained in this link


#16

Fenwick Tree or Binary Indexed Tree are more useful in such cases and require less memory.They are easy to understand nad learn than segment tree also.


#17

How much did you take for each query ?
I guess (might be wrong) I implemented a stupid cascading which gave 8*logn per query, if it was correct. But that solution timed out.


#18

Did the same but probably that is why M, N = 2 * 10 ^ 5 because I tested it and it runs in appr. 1.6 s on my laptop, but 10^5 runs fine


#19

I guess lower_bound and upper_bound are implemented as binary search algorithms. (important for maintaining complexity) You can at least decrease the factor of your queries by decreasing the size of your interval each time you search. Your algorithm fully binary searches the entire range 4 times, no matter what. But when you know a < b for example, the lower_bound of b can be found in the range[upper_bound(a),end]. The rest of your code looks pretty similar to mine. I wonder if that’s the only reason that yours TLE’d. I’m not using c++ very often so I guess the try is yours.


#20

Then, the amount of numbers that has smaller indexes than X and are greater than aX equals to the number of points in the axes-parallel rectangle with the following bottom-left and top-right corners: (1, aX+1) and (X-1, N).

Shouldn’t the top right corner be (X-1,max(ai))