YouKn0wWho's blog

An Interesting Problem?
By YouKn0wWho, history, 6 years ago, In English

I need to solve this following problem as a subproblem of another problem:

Statement:

You are given n sets S[1], S[2], S[3], ..., S[n] each having some distinct elements (Note that 2 different sets have common elements but each set have distinct elements).

Given q queries of type (i,j) you need to find if there is any common element in set S[i] and S[j]. Output YES/NO.

Constraints:

1<= n,size of S[i],elements of S[i],q <=100000

1<= sum of sizes of all sets <=100000

Thanks for reading the problem. It will be great if you can give me a solution.

Tags set
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

This is called the set intersection oracle problem.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Something like this? Maybe? Divide the sets into two groups one having less than 300 elements and others having more. Preprocess heavy sets and brute force light sets. In other case use binary search. Well, I did't analysed time limit. :/

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It will work within the given time limit. Thanks for your reply.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Iterate over all elements of the sets and check for intersection. Runs comfortably in quadratic time. If time limit is at least 16 minutes, it should be OK.

→ Reply