You are not logged in. Please login at www.codechef.com to post your questions!

×

Can any one help me find number of inversions in a 2D array?

I know how to do it using Fenwick tree on a 1D array. If the size of elements is large, I know how to use co-ordinate compression to bring it into workable range. But I am unable to understand how to do it for 2D array. I know about 2D fenwick tree, just not how to use it in this case.

I am referring this problem.

The solution converts the 2D array into 1D array. After that it uses sorting and then Fenwick tree. This is the part where I am lost. Why use sorting? When we sort, doesn't the relative order of the elements change?

Can someone explain this part with a simple example?

I am trying to follow anudeep2011's solution.

asked 07 Aug '16, 20:42

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%


Take a 2D BIT, and once the 2D array is converted to a 1D array and is sorted, for each element in the array, starting from the largest, add 1 to BIT [x][y], where x,y are the indices of the element in the original 2D array, after that you find the sum of the values in the BIT within the rectangle (0,0),(x,y), and add it to the answer. I'll tell you why this works, the conditions specified in the problem were :
1) x1 <= x2
2) y1<=y2
3) a[x2][y2] < a[x1][y1]
By adding the elements starting from the largest, you can say for sure, that any element whose coordinates have been recorded in the 2D BIT, is definitely larger than the current element that you have taken, that takes care of condition 3, and by taking the sum of the rectangle, you're making sure that the conditions 1 and 2 hold true.

link

answered 08 Aug '16, 00:50

hemanth_1's gravatar image

6★hemanth_1
1.4k11
accept rate: 28%

edited 08 Aug '16, 01:15

Thank you bro. After a lot of pen and paper trial and your help, I am finally able to understand. For 1D I always used online algorithm. Never knew it can be done offline like this (eliminates co-ordinate compression). Out of curiosity, can it be solved using online processing? I tried it (after compression), but couldn't solve.

Anyway, thanks a lot :)

(10 Aug '16, 22:22) dragonemperor3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×310
×14

question asked: 07 Aug '16, 20:42

question was seen: 1,423 times

last updated: 10 Aug '16, 22:22