2
$\begingroup$

Recently, I encountered the following problem:

Given an array $A$ of length $n$ $(0\le n\le 2^{17})$. Let $f(l, r, x)$ denotes the number of occurrences of $x$ in the subarray $a[l\ldots r]$. Find the number of pairs $(i, j)$ such that $i<j$ and $f(1, i, a[i]) > f(j, n, a[j])$.

My idea is to mimic the divide and conquer algorithm used to count the number of inversions:

  • Split the array in to two equal halves.
  • Recursively calculate the number of count inversions in each half.
  • Somehow calculate the number of count inversions in with $i$ in the first half and $j$ in the second half (this is the merge step in the ordinary count inversion algorithm).

However, I'm stuck with the merge step. Anyone have any idea on how to overcome this step?

$\endgroup$
4
  • $\begingroup$ (If you "do a merge step like in merge-sort", what does the count of items taken from the second half before the first half is exhausted mean?) $\endgroup$
    – greybeard
    Jul 10 '21 at 8:13
  • $\begingroup$ (Darn. That's one very special case of divide and conquer. Oh bother.) $\endgroup$
    – greybeard
    Jul 10 '21 at 8:14
  • $\begingroup$ Does have to be Divide-And-Conquer? And are you allowed to use something like an ordered statistics tree (basically an avl tree which supports finding the index of a given element, in $O(\log n)$)? Using the later an $O(n \log(n))$ is possible. $\endgroup$
    – plshelp
    Jul 10 '21 at 15:14
  • $\begingroup$ Where did you encounter this? Please credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Jul 10 '21 at 16:03
2
$\begingroup$

I have an algorithm idea, however it relies on data structures.

First we pre-compute $L[i] = f(1,i,a[i])$ using a Hashmap.

H := Map()
for i = 1, ..., n:
    key := a[i]
    if key in H: 
        H[key] = 1
    else: 
        H[key] += 1
    L[i] = H[key]

In the same manner we pre-comupte $R[i] = f(i,n,a[i])$ (backwards ofc). Now we have to find the number of pairs $i<j$ such that $L[i]<R[j]$ This is possible with a modified sorted balanced binary search tree. This tree should support insert/remove but also the operation:

$rank(x)$ - find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree

Such a tree is called Ordered Statistics Tree(OST). (All of the above operations in $O(\log n)$ )

for i = 1, ..., n:
    tree.insert(R[i])

total = 0
for i = 1,...,n:
    total += n - tree.rank(L[i])
    tree.remove(R[i])

$total$ is the final result. Note that OST is implemented in the standard library of gcc, making it available in most CP scenarios. If you want to implement rank yourself without needing BBSTs, that is also possible using a combination of toggle-sum segment tree and binary search. Using a Fenwick-tree and binary search is for competitive programming purposes easiest to implement.

The runtime of the first part is $O(n)$ and for the second part $O(n\log n)$ (since we make $3n$ tree queries).

$\endgroup$
1
  • $\begingroup$ Since you are already spending time $O(n \log n)$ in the second part, you can replace the hashmap with a deterministic dictionary requiring time $O(\log n)$ per operation to improve the overall running time to $O(n \log n)$ in the worst case. $\endgroup$
    – Steven
    Jul 11 '21 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.