I’m trying to solve a question where I am given an array of n integers [a_1,\ldots,a_n], 1\le a_i\le n and multiple queries of the form i, j, k, l.
Each query wants the answer to the question:
Is the set of distinct elements in the subarray [a_i, \ldots, a_j] equal to the set of elements in [a_k,\ldots,a_l]
I want each query to be answered fast, in something like O(\log n), O(\log^2 n).
I have been trying a lot of different techniques, including segment trees, polynomial hashing but none of them are working for me.
Can anyone see a solution to this problem? The problem is the Subarray Set problem from here
EDIT: So I managed to get a solution using square root decomposition and hashing which answers each query in O(\sqrt{n}).
But I am still curious if this can be done faster…
It can’t be done using standard polynomial hashing as duplicates of a node would change the hash
E.g. for an array [1,2,1,3,1,2,3] and i, j, k, l = 0, 3, 4, 6 we would have the two subarrays [1, 2, 1, 3] and [1,2,3] which both have the same set \{1, 2, 3\}
That’s not a contest, that’s a question that was created by yourself on hackerrank! Please share the link to the original source where you found the question.
Yes, I know.
Because there is no original contest link.
I came up with this problem while discussing at university last week.
I created the problem on hackerrank to illustrate the problem.