CSES - Ferris Wheel

Authors: Danh Ta Chi Thanh, Kenny Cho, Nathan Gong

Edit This Page

Unofficial Editorial

Since each gondola can contain either 1 or 2 children, for each gondola, we can do one of two things:

  1. Pair the lightest child with the heaviest child possible without exceeding the weight limit.
  2. If the pairing isn't possible, we only include the lightest child.

Those left unpaired each get their own gondola. The implementation below uses the above method.

Alternatively, for each gondola, we can also

  1. Pair the heaviest child with the lightest child if possible.
  2. Otherwise, only include the heaviest child.

Both pairing methods can be achieved in O(n)\mathcal{O}(n) time using two pointers, and sorting brings the overall time complexity to O(nlog⁡n)\mathcal{O}(n\log n).

Implementation

Time Complexity: O(nlog⁡n)\mathcal{O}(n\log n)

C++

#include <bits/stdc++.h>


using namespace std;


const int maxn = 2e5 + 10;


// Variables used for the current problem
int n, x, p[maxn], i, j, ans;
// Keeps track of the number of children who have had their own gondola
bool have_gondola_yet[maxn];

Java

import java.util.*;


public class FerrisWheel {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);


		int n = sc.nextInt();
		int x = sc.nextInt();
		sc.nextLine();

Python

_, max_weight = map(int, input().split())
weights = sorted(map(int, input().split()))


light_ptr = 0
heavy_ptr = len(weights) - 1
gondola_total = 0
while light_ptr <= heavy_ptr:
	# Pair the heaviest child with the lightest child if possible
	if weights[light_ptr] + weights[heavy_ptr] <= max_weight:
		light_ptr += 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum