4
$\begingroup$

I'm looking for an efficient way to assign n people to m rooms in a very specific way.

INPUT:

The program receives two sets of people (set of males and set of females), as well as a set of available rooms (rooms can have different sizes, ranging from 2 to 6).

ASSIGNMENT CONDITIONS:

The algorithm must assign people to the rooms in a way, that:

  • A room can be only occupied either by all males, or by all females
  • Noone can be alone
  • The algorithm must minimize the number of occupied rooms

We can assume that there are at least 2 representatives of each gender.

OUTPUT:

The algorithm must return the assignment.

I've tried to do it, but all of the sollutions I come up with are at least O(n^3). Does anyone know an efficient way to do this?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Can you post your $O(n^3)$ algorithm? There's an easy $O(n)$ algorithm for the single-gender case, but it's driving me up the wall trying to figure out even a subexponential algorithm that provably always works for the two-genders case. $\endgroup$ – Aaron Rotenberg Dec 7 '19 at 5:07
  • 1
    $\begingroup$ The best algorithm I have at this point is around $O(n^{10})$, by dynamic programming on the state vector $(p_2, ..., p_6, q_1, ..., q_5, n_m)$, where $p_k$ is the number of empty rooms with $k$ seats, $q_k$ is the number of male-occupied rooms with $k$ remaining seats, and $n_m$ is the number of unassigned males. It's almost like a more complicated change-making/Frobenius number problem. $\endgroup$ – Aaron Rotenberg Dec 7 '19 at 15:47
  • $\begingroup$ In the future, when you receive feedback, requests for clarification, suggestions for improvement, please edit the question to incorporate that into the question. Don't leave comments with clarifications -- edit the question. We want people to be able to understand what is being asked, without having to read the comments. I made that change for you this time so you can see an example of what I have in the mind. In the future, I encourage you to do it proactively yourself -- I think it might make it more likely you get helpful answers. Thank you! $\endgroup$ – D.W.♦ Dec 7 '19 at 21:51
  • $\begingroup$ A moderator deleted my answer to the original question. That's quite annoying, since it only needed some minor modifications. So I suppose it will have to go without an answer. @D.W. : Very annoyed. $\endgroup$ – gnasher729 Dec 7 '19 at 22:52
  • 2
    $\begingroup$ @gnasher729, as I understand it, your answer does not match the question -- see my edits to the question, specifically the constraint "A room can be only occupied either by all males, or by all females", which based on a comment from the original poster appears to be what they meant. If you think I have misunderstood your answer, I can certainly undelete it. Would you like me to do that? $\endgroup$ – D.W.♦ Dec 7 '19 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.