Our current solutions to the problems in this volume are below. If a problem is not shown here, then we have not posted a solution yet.

# #11000 - Bee

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: math Solution Description: They're Fibonacci numbers. The number of females after year i is fib(i) (indexed at zero). The number of males is equal to the sum of all fib numbers up to and including fib(year-1) output (sum(n), (sum(n)+fib(n))

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: Pregenerate two arrays, where m[i] = number of male bees after i years, and f[i] is the same for females. In general, m[i] = m[i-1] + f[i-1], and f[i] = f[i-1] + f[i-2]. You don't need to pregenerate more than 100 cells for either array. Now, just print out m[i] and (m[i]+f[i]). Note that the bounds are 2^32, so use longs or unsigned ints.

# #11003 - Boxes

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: dynamic programming Solution Description: We have to use the boxes in the order they're given, from bottom to top. Let a[i] be the most capacity that we have remaining on a stack of height i. Initially, a[0] = infinity, and a[i] = -1 for i != 0. Let Wi and Ci be the weight and capacity of the ith box. We get: a[j+1] = max(a[j+1], min(a[j]-Wi, Ci)) for all j <= i. a[j]-Wi is how much capacity would remain if we put box i on top of the stack of height j. But, if Ci is smaller, then that becomes the new limit. And then, we take the maximum of using this box, or not using it. Process the different j's in descending order, or you'll get an error where you try to use the same box multiple times.

# #11005 - Cheapest Base

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute forcemath Solution Description: Just convert the given number into all bases from 2 to 36 and return the base(s) with the lowest cost.

# #11015 - 05-2 Rendezvous

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: floyd warshall Solution Description: Wow, this problem took much longer for me than it should have. The problem specification is wrong. The value of M CAN be 0 - in which case you output the first name that you're given. I don't know if this is necessary, but try to accomodate names with spaces in them. Make an adjacency matrix, with array[i][j] = 0 (when i == j). Use Floyd Warshall on the matrix, and then iterate through the whole array once more to find the node with the smallest sum of distances to all the others (that comes earliest in the input).

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: floyd warshall Solution Description: Run Floyd-Warshall to get the shortest path across all pairs. Then, for each node i, sum up the distances from i to all other nodes j. Output the name associated with the node with the lowest sum.

# #11039 - Building designing

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: greedysorting Solution Description: At first this may seem like a Longest Increasing Subsequence DP, however it's much simpler - and if you TRY to do the DP you'll get a TLE. Just sort the input and iterate up through it. If at any point the current item is a different color from the one before it, add one to a counter. Output the counter. You can use a HashMap to store all the red numbers, 'cause then you'll get constant time contains functions. I'd say this is on the upper bound of trivial problems.

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programmingsorting Solution Description: Sort the data by decreasing absolute value. Then, run a really tiny DP: Let P be the highest building so far with a positive number on the bottom, and let N be the highest building so far with a negative number on the bottom. For each floor i, if it is negative, then N = P + 1. If it's positive, then P = N + 1. At the end, output the max of P and N.

# #11040 - Add bricks in the wall

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: mathsorting Solution Description: There's enough information to build the pyramid from the bottom up. Consider this mini pyramid, where we don't know X, Y, or Z: 8 X Y 1 Z 3 X = 1 + Z Y = 3 + Z 8 = X + Y = (1+Z) + (3+Z) = 4 + 2Z So, Z = (8 - 1 - 3)/2. The general form of Top = (Bottom Right + Bottom Left) / 2 works everywhere, so use that to fill in the odd rows. It's simple enough to fill in an even row once you have the row below it, of course.

# #11044 - Searching for Nessy

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: math Solution Description: We don't care about the borders, so we need to fill in an (n-2)*(m-2) area. Each sonar controls a 3x3 area, so the answer is ceil((n-2)/3) * ceil((m-2)/3).

# #11045 - My T-shirt suits me

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: medium Algorithms Used: max flow Solution Description: This is a fairly straightfoward bipartite matching problem. Create a node for each t-shirt size, a node for each volunteer, a source, and a sink. Draw an edge from the source to each t-shirt with capacity n/6 (as that's how many t-shirts there are of each size). Draw an edge from each volunteer to the sink with capacity 1. Draw an edge from between a t-shirt size and a volunteer with capacity 1 if that volunteer will take that size of t-shirt. Run max flow on this graph. If the maximum flow is equal to the number of volunteers, print "YES". Otherwise, print "NO".

# #11057 - Exact Sum

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: searching Solution Description: Keep an array of 1,000,000 integers where a[i] is the number of books with price i. Search this array for all i from M/2 back to 0. Find an i such that a[i] > 0 and a[M-i] > 0. The one caveat is if i == M. In this case, a[i] must be >= 2. If you search from M/2 down to 0, then the first answer you hit will be the one to display.