bhayanak's blog

Help please!
By bhayanak, history, 8 years ago, In English

Somebody please give some good approach.

https://www.codechef.com/JUNE17/problems/UNIONSET

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Take a 2D boolean array with 1st dimension for storing N or the set number. Use that particular array for marking 1 for various elements that occur.
  2. Traverse every possible pair and move from 1...K in each traversal so as to check for presence of element (B[i][k] || B[j][k])

Here is my implementation

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought of the same thing but did not do that during the contest and it's complexity is O(N*N*k),I wonder how did it pass the test cases? Correct me if I am wrong.

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

      The judge data was pretty weak you see, many people solved it with O(k*n^2) solutions with a few optimizations. I would really like to know how to solve it in a better complexity.

      → Reply