Ferris Wheel Solution

15 September 2021

Statement

( The original statement can be found here )

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 p1,p2,…,pn: the weight of each child.

Output
Print one integer: the minimum number of gondolas.

Constraints
1 ≤ n ≤ \(2 \times 10^5\)
1 ≤ x ≤ \(10^9\)
1 ≤ \(p_i\) ≤ x
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
4 10
7 2 3 9

Output :
3

Solution

What is the optimal way of matching weights so that we minimize the number of gondolas? An intuitive way to figure this out is to ask ourselves who best matches the heaviest children. It has to be the lightest. It's easy to match two light children but it's much harder to match two heavy children. Therefore, it is optimal to try to match a light children with a heavy children.

This is a classic two pointers technique problem. That is, given the sorted list of weights, we can have one pointer at position \(0\) and a second pointer at position \(N-1\), hence the name of the technique.

We start by sorting the array of weights, because otherwise this technique will not work. The trick is to move these pointers according to the current situation. Let us call the first and second pointers \(p_{begin}\) and \(p_{end}\) respectively.

If \(weights[p_{begin}] \: + weights[p_{end}] \: \leq x\), we just found a match, we should increment \(p_{begin}\) by 1 and subtract one from \(p_{end}\).

If not there is only one thing we can do and that is subtract 1 from \(p_{end}\). Note that the sum only gets larger if we increment one of the pointers.

We repeat this process until the pointers meet.

You will notice that in the following code, every time a match is found, \(N\) is decreased by 1 and we end up outputting \(N\). This works because if we assume that the solution is initially \(N\), each match decreases the number of gondolas needed by 1.

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, x;
    cin >> n >> x;
    int p_begin = 0, p_end = n - 1;
    vector<long long> weights(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    sort(weights.begin(), weights.end());
    while (p_begin < p_end) {
        if (weights[p_begin] + weights[p_end] <= x) {
            n--, p_begin++, p_end--;
        } else {
            p_end--;
        }
    }
    cout << n << endl;
}

Since we need to sort the list of weights the time complexity for this solution is \(O(n \times log(n))\) while the space complexity is \(O(n)\).