Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

bhayanak's blog

Help please!
By bhayanak, history, 9 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

»
9 years ago, hide # |
 
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
  • »
    »
    9 years ago, hide # ^ |
     
    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
    • »
      »
      »
      9 years ago, hide # ^ |
       
      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