Блог пользователя YouKn0wWho

Автор YouKn0wWho, история, 6 лет назад, По-английски

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.

Теги set
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
»
6 лет назад, # |
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. :/

»
6 лет назад, # |
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.