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$

2 Answers 2

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$
1
  • $\begingroup$ Having a processing time of O(NM) is pretty slow, is there a way to eliminate that preprocessing? $\endgroup$ Jun 7, 2019 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$
2
  • $\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$ Jun 7, 2019 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, 2019 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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