Make Everyone Souper Happy!

Today I was at my university dining hall, looking at the options for soup.

The dining hall has 2 types of soup at any given time, but they rotate these soups out with several other soups daily. Let's say there are 6 in total.

I am happy to eat some of the soups, but there are also many soups which I do not like to eat. For example, while I like the Italian meatball soup, I don't like the buttermilk squash. Unfortunately, on this day, they did not have a soup that I wanted, but rather just buttermilk squash and garden vegetable mix. "At least the people who like buttermilk squash or garden vegetable mix are happy", I reasoned. But these two soups seem to me like soups that not many people like in general. Therefore, it makes sense to say that they should not be put out together.

Let's now assume a few things. Say that we somehow know which soups each of the N students who eat at the cafeteria like, and which they do not like (there is no in-between). Let's also say that the cafeteria wants to establish a M-day rotation where each soup is used exactly once. The cafeteria wants to make it so that, on the worst day in the rotation, the maximal amount of people are happy. To further generalize, let's say that they have exactly K slots for soup.

Given all the data, what is the best algorithm you can develop for solving this?

Example: Let's use the dining hall I've described. Say there are 4 students, so N = 4, M = 3, and K = 2. Then, let's list out all of the students by their preferences, with a 1 for 'like' or 0 for 'dislike'. The first number in the line will represent if they like the first soup, the second the second soup, and so on.

4 3 2

1 1 0 0 0 0

1 0 1 1 0 0

1 0 0 0 1 1

0 0 1 1 0 1

A possible answer:

Day 1 : The first and fifth soup (only the 4th student is sad)

Day 2 : The second and third soup (only the 3rd student is sad)

Day 3 : The fourth and sixth soup (only the 1st student is sad)

With this answer, on each day (and therefore the worst day), exactly 1 student does not have a good soup. This is the optimal answer because it is impossible that each student is happy every day. One way to prove this is to notice that the first student only likes soups 1 and 2, so there is no way to make him happy for 3 days.

Note: I made up this question while thinking about soup and thought it interesting, it is not guaranteed to have an easy or nice answer. Therefore, you may use your creativity! If you can't come up with a fast optimal solution, try a fast solution that gives 'good' results, or try fixing one of the variables, for example, solving the problem only for K=2.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Make Everyone Souper Happy!

Comments