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 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 - 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: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 wall

Solved 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 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.





Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site