Two problem related to sequence of sets
Given a sequence of sets with a total of elements. Partition , such that if is in the same partition class, then .
Solve the problem by building a trie over the lexicographic ordering of the elements in the set. Since the alphabet has size , it has running time . One can get better running time using integer data structures, say using van Emde Boas tree.
time is actually possible. For each , we build the set (as a list). We define equivalent relation as if . If we have equivalent class of , we can obtain the equivalent class of in time. Hence together the running time is .
Given a sequence of sets containing a total of integers, and a integer . Decide if there exists and such that and .
We assume the elements in the sets are in . Let .
For , we can solve it in time: Decide if any element appears more than once in the sets.
For larger , we shall compute for every pair and . To do this, we start with an all zero matrix . At the end of the algorithm, for all . For each element , we find . This takes time. We increment for all . We claim this algorithm have running time . Indeed, for each , we spend time in incrementing where . Hence the running time is bounded by . We know and . We see the worst case is when and . In that case, we have running time .
Since we just want to find a pair where . We can stop the algorithm as soon as for some and . This means we can increment at most times.
Together, the running time become .
For . One can improve the running time when is large by reduce it to a problem similar to finding rectangles or finding a in the incident graph. Let be , we can obtain a more refined bound. Together, the final running time for is . Here is the degeneracy of the incident graph of the sets and the elements, which is bounded above by the maximum degree.
Recently, I had some result for , where the running time improves to .