1
$\begingroup$

This is a task I saw in a programming competition.

So, you're given a list of guests. Each $i$th guest wants to have $l_i$ free spots to his left and $r_i$ free spots to his right, because they are shy.

You need to seat guests in circles of chairs, such that the number of chairs is minimal. You can have as many chair circles as you want.

For example, suppose you have $3$ guests: $\{\langle1,6\rangle, \langle5,3\rangle, \langle6,7\rangle\}$ (first one wants $1$ free seat to his left and $6$ to his right, etc...).

The answer is $19$, because you can seat the first $2$ guests in one $11$ chair circle and the third guest in another $8$ chair circle.

I was told that in order to solve this you have to independently sort the rhs and lhs values, and the for each pair choose the bigger value rhs or lhs, and then sum all such values and also add $n$ to that in the end.

So, we take $\{\langle1,6\rangle, \langle5,3\rangle, \langle6,7\rangle\}$, sort rhs and lhs values and get $\{\langle1,3\rangle, \langle5,6\rangle, \langle6,7\rangle\}$.

For each pair choose the biggest value and get $\{3,6,7\}$, add these up to get $16$ and also add the number of guests $n$ to that and get $16+3=19$.

How this works: for each $i$th minimal lhs, we find the $i$th minimal rhs, such that one can absorb the other. For example, imagine you have 2 guests $\{\langle2,3\rangle,\langle6,1\rangle\}$. We match $2$ with $1$ and $6$ with $3$, and the $2$ can absorb $1$, and $6$ can absorb $3$. This is obviously more optimal that having $3$ absort $2$ and $6$ absorb $1$.

Can somebody write a formal proof explaining why this works? I believe that it does, but for some reason I cannot convince myself...

I tried this:

Suppose we have $k$th minimal lhs and $k$th minimal rhs. It's optimal for one to absorb the other, because if we choose some $(k-j)$th rhs instead, it's the same as swapping $k$th rhs element with $(k-j)$th, but in that case we might get into situation, where we had $\{\langle2,1\rangle,\langle6,3\rangle\}$ and got $\{\langle2,3\rangle,\langle6,1\rangle\}$, (if $k=2$ and $j=1$) which is undesirable. Is this good enough? Or do I have to explore all the possibilities of what might happen?

$\endgroup$
0
$\begingroup$

The prove will contains two parts:

Prove that the solution exist.

The sorted pair represent the solution, every pair ${\{P^l_i,P^r_j\}}$ indicate that people ${P_i}$ is sitting to the right of people ${P_j}$. So the solution exists.

Prove that the solution is optimized, aka no better solution exist.

And the optimized solution is finding the sequence ${\{x_i,y_i\}, x_i\in P^l, y_i \in P^r }$ with minimize value of ${NumberOfChairs = \sum_i max(x_i, y_i)}$

Use induction from here, n is number of people:

  1. If n = 1, trivial case.
  2. If n > 1, the last element must be ${\{max(P^l), max(P^r)\}}$, it is also pretty easy, I'll leave it to you to prove.
$\endgroup$
  • $\begingroup$ I don't understand anything you wrote... Sorry. It seems that you are arbitrarily saying "If n > 1, the last element must be {max(Pl),max(Pr)}", without any proof. Or maybe I'm missing something... $\endgroup$ – Coder-Man Oct 5 '18 at 16:53
  • $\begingroup$ And why are you only talking about the last element? What about the elements before that? $\endgroup$ – Coder-Man Oct 5 '18 at 17:02
  • $\begingroup$ Can you understand that while keeping one side (left or right) in the series of pairs fixed, then any permutation of other side representing one arrangement of people and chairs $\endgroup$ – Zang MingJie Oct 5 '18 at 23:38
  • $\begingroup$ Yes, I do, but how does this help? Sorry. $\endgroup$ – Coder-Man Oct 6 '18 at 12:08
  • $\begingroup$ Then consider which number should be paired with the largest number $\endgroup$ – Zang MingJie Oct 6 '18 at 15:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.