The Way Through The Forest

USACO Training: "Camelot" (This was a hard problem) Problem Analysis If the problem did not specify that the king needed to be picked up, this would be a simple all-pairs shortest pathes problem: find the point (r,c) such that sum(distance((r,c),(i-th knight row, i-th knight column))) is minimized. However, we need to take into account that the king needs to be picked up and ridden to (r,c) too! Our first discovery: The king can only take at most two steps. Why? We notice that for any sequence of three (non-undoing) steps the king makes, the knight can do it in three (or sometimes even two) steps, so it would be inconstructive for a king to move three steps when a knight carrying it can. We try this method: Choose an arbitrary point (i,j). Add up all the distances between each knight and (i,j) - if no shortest path exsists, (i,j) is invalid. For each position a king can be in with at most two moves (ki, kj) find i such that the value: max(abs(ki-kr), abs(kj-k...

USACO Training: "Feed Ratios" Problem Idea Given four triple ratios (i.e. 3:4:5) named a, b, c, and t, find the values x, y, z, and k such that xa+yb+zc = kt. For example, given the ratios 1:2:3, 3:7:1, 2:1:2, and 3:4:5, x, y, z, and k would be 8, 1, 5, and 7 respectively since 8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5) Notices This is not a unbounded exact knapsack problem. Ironically, DP would be too slow, since we'd need to check for all values of k (the knapsack is not fixed as t!) There is at most 100 of each feed bag, it is fast enough to enumerate through bag counts themselves. k can never be 0 (or else x, y, and z will all be 0, but then the goal ratio has to be 0:0:0) If there is multiple satisfying (x, y, z, k), we choose the one that has smallest value of x+y+z #4 leads to the possible optimization such that when enumerating, if x+y or x+y+z exceeds the current best value of x+y+z, we don't even need to check if a k exs...

USACO Training "Humble Numbers" Problem Statement In this problem we are asked to find the n-th "humble number" of a set of primes of length K <= 100. A humble number of a set is defined as a number whose prime factors are as subset of the set. We are asked to find the n-th humble number of a set, when considered from lowest to greatest. Notices Possibly most importantly, we notice that any humble number of a set can be created by multiplying elements of the set together. Clearly a recursive search (i.e. recursively multiplying elements by other elements) will take both too long (O(n^n)) and use too much memory (O(n!)). We try a DP approach. DP Approach We calculate the humble numbers in order (i.e. from the first to the Nth). For simplicity (and correctness), we assume that 1 is the 0th humble number. Once we have the first X humble numbers, we compute the X+1-th humble number as follows: Set best=0x7FFFFFFF (largest signed long int) and best...

USACO Training: Cow Tours Idea: Let us first initially use Floyd-Warshall's to calculate the all-pairs shortest paths. Afterwords, our first instinct would be to do the following: Select a node i, Select a node j, Create an edge between i and j, Do FW again, Loop through array to find the maximum edge. However, the problem is soon obvious: this runs in O(n&5) time: o(n) for selecting i, o(n)for selecting j, o(n^3) for doing the FW, and O(n&3) for looping though the array. How can we optimize this? Let us introduce a new measure, the longest possible (non-infinite) distance between a node X and any other node. Let it be stored in an array called "far". We notice that since we have already done Floyd-Warshalls on the grid, we can precalculate this array. Notice that now, we instantly reduce the time by a factor of O(n^4) - we can instantly, i.e. in O(1), calculate the diameter if we added an edge between I and J! However, we would need to calculat...