-synx-'s blog

Similar to Number of Inversions — Can it be solved using 3D BIT?
By -synx-, 6 years ago, In English

So the problem goes, like,
We are given a list of three parameters A[i], B[i], C[i].
Now, we need to count for each index i, number of indices j for which A[j] > A[i] and B[j] > B[i] and C[j] > C[i].
Constraints on N <  = 105, A[i], B[i], C[i]<=10^5.
Now the main issue with using 3D BIT is the memory consumption (even if we replace array with map).
How can it be solved?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I've seen this problem before, with lower limits though. The most important part is just sorting all triplets by A[i], and then using only a 2D BIT. This works because you're already processing triples in order of A[i], so you just need to check the "largest" triplet that's less than B[i] and C[i]. With a hashmash, this should probably pass.

If you want O(N) memory, you can implement some O(N*sqrt(N*logN)) solution, where for each normalized B[i] you use buckets of sqrt(N) sorted by C[i]. It might run faster just because the constant is better. :)

→ Reply