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  BeeSolved 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(year1)
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[i1] + f[i1], and f[i] = f[i1] + f[i2].
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  BoxesSolved 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 BaseSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Just convert the given number into all bases from 2 to 36 and return the base(s) with the lowest cost. 
#11015  052 RendezvousSolved 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 FloydWarshall 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 designingSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  greedy sorting
 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 programming sorting
 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 wallSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math sorting
 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 NessySolved 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 (n2)*(m2) area. Each sonar controls a 3x3 area, so the answer is ceil((n2)/3) * ceil((m2)/3). 
#11045  My Tshirt suits meSolved 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 tshirt size, a node for each volunteer, a source, and a sink.
Draw an edge from the source to each tshirt with capacity n/6 (as that's how many tshirts there are of each size). Draw an edge from each volunteer to the sink with capacity 1. Draw an edge from between a tshirt size and a volunteer with capacity 1 if that volunteer will take that size of tshirt.
Run max flow on this graph. If the maximum flow is equal to the number of volunteers, print "YES". Otherwise, print "NO". 
#11057  Exact SumSolved 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[Mi] > 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. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
