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 euclidean algorithm to calculate GCD to reduce the fractions.

KEY THOUGHT: our final solution can't have bags * slots in the runtime KEY THOUGHT: 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

Code

Solution - Java

import java.util.*;
public class j {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new j().go();
	}
	private void go() {
		int n=in.nextInt();
		HashMap<String,Integer> dom=new HashMap<String,Integer>();
		HashMap<String, Integer> kat=new HashMap<String,Integer>();
		for(int i=0;i<n;i++){
			String s=in.next();
			if(!dom.containsKey(s))dom.put(s, 0);
			dom.put(s, dom.get(s)+1);
		}
		for(int i=0;i<n;i++){
			String s=in.next();
			if(!kat.containsKey(s))kat.put(s, 0);
			kat.put(s, kat.get(s)+1);
		}
		int ans=0;
		for(String s:dom.keySet())if(kat.containsKey(s))ans+=Math.min(dom.get(s), kat.get(s));
				System.out.println(ans);
	}
}

Sorting

Idea

Sort the two lists. Start at the head of each list. If the two match, increment the total match count. If they don't, increment the index of the list with the word that appears first alphabetically.

Runtime

n*log(n)