2
$\begingroup$

I was solving this problem Ferris wheel

There are n children who want to go to a Ferris wheel, and your task is to find a gondola for each child.
Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed x. You know the weight of every child.
What is the minimum number of gondolas needed for the children?
Input
The first input line contains two integers n and x: the number of children and the maximum allowed weight.
The next line contains n integers p_1,p_2,...,p_n: the weight of each child.
Output
Print one integer: the minimum number of gondolas.
Constraints

1 <= n <= 2..10^5
1 <= x <= 10^9
1 <= p_i <= x

Example
Input:
4 10
7 2 3 9

Output:
3

Everywhere its solutions goes as follows:

  1. Sort the weights.
  2. Remove all weights over x.
  3. Put heaviest child in gondola.
  4. If lightest child can be put in the gondola, put him otherwise not
  5. Keep doing these steps from 3-4 and keep counting gondolas.

For example, if the max weight allowed in gondola is 10 and there are 7 children with weights 1, 2, 3, 4, 5, 6. First we put the 6th child (wt 6) in gondola and since we still have 4 units of space left, we put the first one (wt 1). Now here my question is that why are we putting the first one, wouldn't it be more optimal if we put the 4th one (wt 4).

So, I want to ask why selecting the heaviest and lightest is optimal and why we do not need to select heaviest and another which can just fit?

$\endgroup$
4
  • $\begingroup$ The intuition with their way is the lightest child has to sit somewhere and for efficiency she should sit with the heaviest child. Thus the remaining weight will be the least. Thing is we can't have the lightest child sit with more than two others. Another way of putting it is pick the lightest child. Give all children too big to sit with her their own gondula. Put her with the largest remaining. And repeat. $\endgroup$
    – fleablood
    Commented May 9 at 17:06
  • $\begingroup$ I think your way can be inductively shown to be equally efficient but no better. $\endgroup$
    – fleablood
    Commented May 9 at 17:09
  • 1
    $\begingroup$ Simplified. Suppose we have $a \le b \le c \le d$ and we have $d+b\le Limit$. You are claiming we can do $d+b \le Limit$ and $c+a\le d+b\le Limit$ will work at least as well as their idea of $a+d$ and $b+c$. In order for your idea to work better than theirs we need $d+b\le Limit$, $d+a\le Limit$ but $b+c>Limit$. Let $Limit =d+a+k=d+b+j;0\le j\le k$ so $b+c>Limit\implies c>Limit -b=d+j\ge d$ but that's a contradiction. So yours works as well theirs but not better. I think we can prove the other cases with induction. $\endgroup$
    – fleablood
    Commented May 9 at 17:39
  • $\begingroup$ @fleablood I also had the intuition but I wanted a formal proof which you gave. Thanks. You may write that as an answer and I'll accept that until someone comes with a better one. $\endgroup$ Commented May 9 at 17:58

1 Answer 1

1
$\begingroup$

I had the exact same question when solving this problem.

The basic intuition for solving this problem just comes from the observation that that the higher numbers are prioritized when making pairs. This is where the greediness part comes from. So at this point we know that we should pair the numbers in order from highest to lowest, but what should we pair those numbers with? It seems right somehow to maximize the sums in the pairs, so maybe we should try to pair each number with the highest one it can be paired with. It also seems right to pair the numbers with the lowest possible ones so that we don't waste the bigger numbers by pairing them together, and this also gives us any easy two pointers solution algorithm.

It turns out that it doesn't matter how we pair the numbers, we only have to greedily pair the numbers in order from highest to lowest. Let's formally describe a recursive algorithm that does this.

Let $a_1, a_2, \dots, a_n = A$ be an array of numbers in any order, and let $t$ be the target as described in the problem that we want the sums of our pairs to be smaller then. Our greedy algorithm $G$ maintains a set of pairs made and proceeds as follows:

If the length of $A$ is one or zero, then we return the set of pairs made.

Otherwise, we select $m = \max A$. If there exists a number $a$ distinct from $m$ such that $m + a \leq t$, then we add the pair $(m, a)$ to our set and recursively call the algorithm with the array $A$ without $m$ and $a$.

Claim. This algorithm maximizes the number of pairs made where each pair has a sum no greater than $t$.

Proof. By (strong) induction, we will prove that our algorithm produces the maximal number of pairs for any array of any length $n$.

(base case) When $n = 0, 1$, there are no pairs to be made, and our algorithm trivially returns the empty set.

(inductive step) Suppose that our algorithm produces the maximal number of pairs for any array of lengths $0, 1, 2, 3, \dots, n$. Consider an array $A$ of length $n + 1$. Further consider $m = \max A$.

  1. It may be that there exists no number besides $m$ in $A$ such that their sum is no greater than $t$, i.e., $m$ is not pair-able. In this case, an optimal pairing of $A$ does not include $m$, so it is an optimal pairing of the array $A$ without $m$, which is an array of length $n$, so we just use the inductive hypothesis here.

  2. Otherwise, $m$ is pairable with some $a$ in $A$.

For this second case, consider the array $A$ without the elements $m$ and $a$. Let us call this array $A^-$. By the (strong) induction hypothesis, our greedy algorithm produces the maximum number of pairs for this array of length $(n + 1) - 2 = n - 1$. Let us call this number of pairs $k$. Our algorithm applied to $A$ then outputs $k$ pairs plus $(m, a)$ for a total of $k + 1$ pairs. Therefore, we are tasked with showing that a set of pairs of $A$ with the maximum size has size $k + 1$.

First observe that if we have any set and add any two numbers to it to produce another set, we can make at most two more pairs. For a concrete example, let $t = 100$ and consider $\{98, 99\}$. We can add 1, 2 to create two more pairs, 99, 1 to create one more pair, and 99, 99 to create no pairs.

So what we will do is eliminate the possibility of adding $m$ and $a$ to $A^-$ to make two more pairs. First, if $n \leq 2$, then $A$ has at most 3 elements, so it can have at most one pair with sum no greater than $t$, while $A-$ has zero pairs.

Now whenever $n \geq 3$, we know that no unpaired element of $A^-$ can be paired with $m$, because if so then that number would have been pairable with another unpaired number in $A^-$ since $m$ is no less than any element of $A^-$ (notice that this is the only place in the proof where the maximality of $m$ comes into play and basically formalizes the intuition that we must pair the highest numbers before the lower ones since they can be paired with the least amount of numbers).

Therefore, it cannot be that both $m$ and $a$ are paired to unpaired elements of $A^-$ to produce $k + 2$ pairs. But since any maximal pairing of $A^-$ with $(m, a)$ included is a pairing of $A$ with $k + 1$ pairs and we just eliminated the $k + 2$ case, we may infer that $A$ has $k + 1$ pairs in any maximal pairing. This agrees with our algorithm, and so we conclude the induction.

(end of proof)

I feel like the proof was longer than I hoped for, and I'm still trying to find a more concise one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .