Knapsack Collection

Introduction

Calculate the total number of time to take luggage off an airport baggage carousel. Once you grab a bag, the carousel rotates t "slots" before you can grab the next bag. You must grab the next bag that arrives. Return the min, max, and average time it takes across all starting locations.

Solutions

Brute Force Simulation

Idea

Start at all 10^7 slots and calculate the time it takes to remove all luggage. Compute required values;

Runtime

• s^2

Brute Force Simulation with binary search look-up of next bag

Idea

Start at all positions, but instead of iterating around the array until you find a bag (could be a long way away!), maintain an array of current bag positions, and perform binary search to find the next bag. Remove the index from the array once you've removed the last bag there (or don't...same runtime)

Runtime

• slots * bags * (binary search time + remove index time)
• s * log(n) * 2n ~= 4*10^10
• slots * bags * (binary search time + iterate to next bag) (if we don't remove, then we have to iterate through the bag array to find the next non-zero bag)
• s * log(n) * 2n

Brute Force Simulation with treeset

Idea

Treeset gives us log(n) lookup and removal. Use that instead of binary search over an array

Runtime

• slots * bags * lookup/removal time
• s * n * log(n) ~= 2*10^10

Only use bags as possible start locations

Idea

If we only simulate starting where there is already a bag, the answer for the rest of the slots is simply the time it takes to wait for the next bag plus the time starting from that bag. Use GCD formula to reduce the fractions.

• our final solution can't have bags * slots in the runtime
• the locations of the bags are the only "interesting points"

Runtime

• slots * lookup + bags * bags * lookup
• s * log(n) + n^2 * log(n) ~= 10^8 + 4*10^7 FAST ENOUGH

Gotchas

• Be sure to use a long when summing across all slots
• trying to reduce the fractions by hand is annoying, just use canned GCD formula (euclid preferred)

Code

Solution - Java

import java.util.*;
import java.awt.*;
public class k {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new k().go();
	}
	private void go() {
		int n=in.nextInt(),s=in.nextInt(),t=in.nextInt();
		int[] k=new int[n];
		long[] ans=new long[n];
		long max=0;
		long min=Long.MAX_VALUE;
		for(int i=0;i<n;i++)k[i]=in.nextInt();
		for(int i=0;i<n;i++){
			Point pos=new Point(k[i],-1);
			long time=0;
			TreeSet<Point>ts=new TreeSet<Point>(new Comparator<Point>(){
				public int compare(Point arg0, Point arg1) {
					if(arg0.x!=arg1.x)return arg0.x-arg1.x;
					return arg0.y-arg1.y;
				}
			});
			for(int j=0;j<n;j++)ts.add(new Point(k[j],j));
			while(!ts.isEmpty()){
				Point next=ts.higher(pos);
				if(next==null){
					time+=s-pos.x;
					pos.x=0;
					continue;
				}
				time+=next.x-pos.x;
				ts.remove(next);
				pos.x=(next.x+t)%s;
				time+=t;
			}
			ans[i]=time;
		}
		TreeSet<Point>ts=new TreeSet<Point>(new Comparator<Point>(){
			public int compare(Point arg0, Point arg1) {
				if(arg0.x!=arg1.x)return arg0.x-arg1.x;
				return arg0.y-arg1.y;
			}
		});
		long num=0;
		for(int j=0;j<n;j++)ts.add(new Point(k[j],j));
		for(int i=0;i<s;i++){
			Point on=ts.higher(new Point(i,-1));
			long time;
			if(on!=null)time=on.x-i+ans[on.y];
			else time=s-i+ts.first().x+ans[ts.first().y];
			max=Math.max(max, time);
			min=Math.min(min, time);
			num+=time;
		}
		long gcd=greatestCommonDenominator(num,s);
		System.out.printf("%d\n%d\n%d/%d\n", min,max,num/gcd,s/gcd);
	}
	long greatestCommonDenominator( long a, long b ){
		while( b != 0 ){
			long t = a%b;
			a = b;
			b = t;
		}
		return a;
	}
}