You want to organize a party and invite as many of your N friends as possible so that the following condition is met: at a party, everyone invited must know at least three other guests and must not be familiar with at least three other guests. The input to the problem is number N and the list of pairs (i, j) where i and j know each other. What would be an efficient algorithm that implements the above mentioned and what's the complexity? Could I use some greedy approach?

  • 1
    $\begingroup$ We're not particularly looking for posts that are just the statement of an exercise-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Typically, there are only a few sensible greedy algorithms worth considering; have you tried checking whether any of them work, using cs.stackexchange.com/q/59964/755? Why do you think an efficient algorithm exists? $\endgroup$
    – D.W.
    May 22, 2023 at 18:02
  • $\begingroup$ If A knows B, does B know A? $\endgroup$
    – gnasher729
    May 22, 2023 at 22:55

1 Answer 1


Hint: It's actually quite simple.

(Yes, that's all the hint you need).

  • 2
    $\begingroup$ The hint indeed helped me:) $\endgroup$
    – Dmitry
    May 22, 2023 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.