1
$\begingroup$

We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there is at least one same number in those two ranges.

We don't need to answer the queries online, so we can sort them in different ways.

I tried different things with segment trees, but I don't have working ideas

$\endgroup$
1
$\begingroup$

You can get $\tilde{O}(NM)$ preprocessing time and $O(1)$ time per query.

Assume for simplicity that $N$ and $M$ are powers of $2$. For each index $i = 1, \dots, n$ and $h = 2^0, 2^1, \dots, 2^{\log N}$, let $A[i, h]$ be the set of the elements in positions from $i$ to $i + 2^h -1$ in $A$. Define $B[j, k]$ similarly.

Let $R[i, h, j, k]$ be true if $A[i,h] \cap B[j, k] \neq \emptyset$ and false otherwise. You can compute each $R[i, h, j, k]$ in constant time by exploiting the following relations: $$ R[i, h, j, k] = R[i, h-1, j, k] \vee R[i + 2^{h-1}, h-1, j, k] \quad \mbox{for }h>0 \\ R[i, h, j, k] = R[i, h, j, k-1] \vee R[i, h, j + 2^{k-1}, k-1] \quad \mbox{for }k>0$$

where $R[i, 0, j, 0]$ is true iff the i-th element of $A$ equals the $j$-th element of B.

There is an intersection between the elements of A in positions $i, i+1, \dots, i+\ell_A - 1$ and the elements of B in positions $j, j+1, \dots, j+ \ell_B - 1$ iff the following condition is true: $$ R[i, h, j, k] \vee R[i + h, h, j, k] \vee R[i, h, j + k, k] \vee R[i + h, h, j + k, k], $$ where $h = \lfloor \log \ell_A \rfloor$ and $k = \lfloor \log \ell_B \rfloor$.

$\endgroup$
  • $\begingroup$ Having a processing time of O(NM) is pretty slow, is there a way to eliminate that preprocessing? $\endgroup$ – someone12321 Jun 7 at 4:03
0
$\begingroup$

Either I'm misunderstanding something or you're severely overcomplicating the issue.

Memory: N+2M

Runtime: Q*range_A

A: plain old array

B: hashmap value => position

For slice of A: If B.get(a) within range_B return true

Else return false

$\endgroup$
  • $\begingroup$ What is the time complexity of this solution? It seems like O(QN) in total, however I'm looking for solutions in O(QlogN) or similar complexity $\endgroup$ – someone12321 Jun 7 at 4:00
  • $\begingroup$ @someone12321 Time complexity is sigma range_q_a in Q. If the ranges are trivially small, you can write it as O(Q) $\endgroup$ – guest Jun 7 at 16:54

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.