YouKn0wWho's blog

By YouKn0wWho, history, 2 months 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  

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it
»
2 months 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. :/

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
2 months 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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

edit. misread the problem.