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

Help please!
Автор bhayanak, история, 7 лет назад, По-английски

Somebody please give some good approach.

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

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить