### YouKn0wWho's blog

By YouKn0wWho, history, 11 months ago, ,

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.

• +9

 » 11 months ago, # |   +18
•  » » 11 months ago, # ^ |   +6 Thanks for your reply. It helped a lot.
 » 11 months ago, # | ← Rev. 2 →   +9 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. :/
•  » » 11 months ago, # ^ |   +3 It will work within the given time limit. Thanks for your reply.
 » 11 months ago, # | ← Rev. 2 →   +16 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.
•  » » 11 months ago, # ^ |   +16 Great solution. Enjoy TLE at the end. xD
 » 11 months ago, # | ← Rev. 2 →   0 edit. misread the problem.