DSA sheet / Sorting and searching
Ferris Wheel
Do these first: Apartments
The problem in brief
There are n children (up to 200 000) with known weights, and every gondola carries at most two children whose weights sum to at most x. Each child weighs at most x. Print the minimum number of gondolas.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1090.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Which child is hardest to place? Think about who has the fewest partners they can share with.
-
Take the heaviest child. What would be the best possible partner for them, and what happens if even that partner does not fit?
-
If the heaviest and lightest can ride together, is it ever worse to send them together than to keep them apart?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Two-per-gondola problems are matchings on a line, and the winning move is usually “pair the extremes”. The heaviest child restricts the options most, so decide their fate first. If the lightest child cannot share with them, nobody can (everyone else is heavier), so the heaviest rides alone. If the lightest can share, do it: pairing the heaviest with the lightest uses up the lightest child, who was the easiest to place anyway, and the exchange argument shows any optimal solution can be rearranged to include this pair.
A brute force would try all pairings (exponential). The decision rule turns it into a single sorted sweep. The habit: order the items and always resolve the most constrained one first.
Intuition
Stand the children in order of weight with the heaviest at one end and the lightest at the other. The heaviest steps forward; if the lightest can squeeze into the same gondola, they both board, otherwise the heaviest goes alone. Repeat until nobody is left.
Approach
- Sort the weights.
- Two indices: lo = 0, hi = n - 1, and gondolas = 0.
- While lo <= hi: the heaviest remaining child (hi) boards. If lo < hi and w[lo] + w[hi] <= x, the lightest (lo) boards too, so lo += 1. Then hi -= 1, gondolas += 1.
- Print gondolas.
Edge cases: an odd number of children (the last one rides alone; the lo < hi guard prevents pairing a child with themselves), a single child, everyone exactly at the limit. Sums reach 2 * 10^9 which overflows a 32-bit int, so add in 64-bit.
Complexity
O(n log n) for the sort, then O(n) for the sweep; O(n) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
vector<long long> w(n);
for (auto &v : w) cin >> v;
sort(w.begin(), w.end());
int lo = 0, hi = n - 1, gondolas = 0;
while (lo <= hi) {
if (lo < hi && w[lo] + w[hi] <= x) lo++;
hi--;
gondolas++;
}
cout << gondolas << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, x = int(data[0]), int(data[1])
w = sorted(map(int, data[2:2 + n]))
lo, hi, gondolas = 0, n - 1, 0
while lo <= hi:
if lo < hi and w[lo] + w[hi] <= x:
lo += 1
hi -= 1
gondolas += 1
print(gondolas)
main()import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedInputStream(System.in));
st.nextToken();
int n = (int) st.nval;
st.nextToken();
long x = (long) st.nval;
long[] w = new long[n];
for (int i = 0; i < n; i++) {
st.nextToken();
w[i] = (long) st.nval;
}
Arrays.sort(w);
int lo = 0, hi = n - 1, gondolas = 0;
while (lo <= hi) {
if (lo < hi && w[lo] + w[hi] <= x) lo++;
hi--;
gondolas++;
}
System.out.println(gondolas);
}
}const data = require('fs').readFileSync(0, 'utf8').split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const x = data[1];
const w = Float64Array.from(data.slice(2, 2 + n)).sort();
let lo = 0;
let hi = n - 1;
let gondolas = 0;
while (lo <= hi) {
if (lo < hi && w[lo] + w[hi] <= x) lo++;
hi--;
gondolas++;
}
console.log(gondolas);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).