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.
This is called the set intersection oracle problem.
Thanks for your reply. It helped a lot.
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. :/
It will work within the given time limit. Thanks for your reply.
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.
Great solution. Enjoy TLE at the end. xD