-2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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 at 18:02
  • $\begingroup$ If A knows B, does B know A? $\endgroup$
    – gnasher729
    May 22 at 22:55

1 Answer 1

Reset to default
2
$\begingroup$

Hint: It's actually quite simple.

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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The hint indeed helped me:) $\endgroup$
    – Dmitry
    May 22 at 23:17

Your Answer

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