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. #11401  Triangle CountingSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  dynamic programming math
 Solution Description:  pregenerate your values. keep a res array, and set res[3] = 0.
remember: a triangle can be formed by any two sides whos length sum is strictly greater than the length of the third.
with this, you can see that if you have 3 lines (res[3]), adding one more possible line to use will make res[n+1] = res[n] + x. we need to know x.
it turns out that x is 1 for res[4], 2 for res[5], 4 for res[6], 6 for res[7], 9 for res[8], etc etc. So keep a variable for 'toadd', and keep a variable for 'toadd_to_toadd', and increment your toadd_to_toadd variable every two iterations, and add it to toadd every iteration.
Or, you could do the better thing and define some closed form.
I rate this as... easymedium theory...? 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry math
 Solution Description:  First, pregenerate an array where a[i] is the number of triangles you can make with i rods. Here's how:
Calculate a[n] for the first few values of n. Remember that a triangle is legitimate if and only if the largest side is strictly smaller than the sum of the other two sides.
You should notice that you can add 2 more triangles, then 2 more triangles, then 3, then 3, then 4, then 4, etc.
So keep one variable, k, that tracks the number of triangles you added on the last iteration. Then, the recurrence is this:
k += (i2)/2
a[i] = a[i1] + k
You will need to use longs to hold the sequence.
This problem is identical to Problem 11554 (Hapless Hedonism). See my solution for that one for an alternative way of thinking about the pattern. 
#11403  Binary MultiplicationSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  sorting strings
 Solution Description:  The calculations necessary for this problem are very easy. In Java, you can use Long.parseLong(str,2) to convert a binary string into a base 10 number automatically, though it's not hard to do by hand.
Make sure you use 64bit integers, because you have strings of length 30, and 2^30 * 2^30 is obviously larger than 2^32.
Of course, it's important to watch your formatting. Two things to watch out for that aren't explicitly stated:
 Don't put trailing whitespace at the end of lines
 The final answer should be rightaligned
On top of this, there are two severe mistakes in the problem description. Firstly, you must have a blank line after *every* case, not just between cases. Secondly, the input does not actually end on a "0 0", but rather at EOF. 
#11407  SquaresSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  This is a fairly simple DP problem. A greedy solution looks plausible, but isn't correct.
Build the solutions for each number from 1 to 10,000 in sequence. We know that a[1] is 1, so use that as a base case. For each new number, i, find the following minimum:
Min across all s of (a[is] + 1)
...where s is some square (1, 4, 9, 16, etc.) 
#11412  Dig the HolesSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force sorting
 Solution Description:  With only 6!/2! = 360 possible combinations, you can just brute force every possible setting and see if at least one of them is consistent with both guesses. 
#11417  GCDSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  They give you the solution in the problem statement. Copy the algorithm almost verbatim, and write a recursive GCD function.
If you do not already have one:
int gcd(b, a)
{
if(a == 0)
return b;
return gcd(a, b%a);
}

Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  You can actually copy and paste the code given, and then just write a GCD function (use the Euclidean algorithm). 
#11420  Chest of DrawersSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a good mediumlevel DP problem. Just a little more difficult than some of the more straightforward 2D DP problems.
To see how this works, take the example of 3 drawers. Here are all the possible drawer setups, from bottom to top:
UUU  0 secure
LUU  0 secure
ULU  0 secure
LLU  1 secure

UUL  1 secure
LUL  1 secure
ULL  2 secure
LLL  3 secure
Note that I've separated the ones with a locked drawer on top from the ones with an unlocked drawer on top.
Now consider adding another drawer:
 If we add an unlocked drawer to a stack with an unlocked drawer on top, the number of secure drawers doesn't change.
 If we add an unlocked drawer to a stack with a locked drawer on top, the number of secure drawers decreases by 1, as the previouslytop drawer is now insecure.
 If we add a locked drawer to a stack with an unlocked OR locked drawer on top, the number of secure drawers increases by 1.
This gives us the following recurrence. Let a[i][j][k] be the number of ways to have i drawers with j secure and the top drawer unlocked if k=0, or locked if k=1.
a[i][j][0] = a[i1][j][0] + a[i1][j+1][1]
a[i][j][1] = a[i1][j1][0] + a[i1][j1][1]
Pregenerate this entire array and output the values as necessary. You will need to use 64bit integers to store many of the higher values. 
#11428  CubesSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Generate cubes up to about 60^3 and just try all combinations. Make sure you use increasing values for y so that the first combination you come across is the correct answer. 
#11437  Triangle FunSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry
 Solution Description:  Determine D, E, and F. Then, find the intersections between AD, BE, and CF. They're guaranteed to intersect, so just solve the system of equations between any two lines to get the intersection point (use pointslope form for ease). Once you have P, Q, and R, use Heron's formula to get the area of the triangle. 
#11448  Who said crisis?Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Just use BigIntegers and output A  B. 
#11450  Wedding shoppingSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  Let a[i][j] be the maximum money you can spend if you have i money, and you've bought j items so far. We want to find the value a[m][0].
a[i][j] = 10000 if i < 0
(This means we've run out of money, which is an invalid solution)
a[i][n] = 0
(We can't spend any more money if we've bought all the items)
a[i][j] = max[over all k items in the jth class] (price[k] + a[iprice[k]][j+1])
(So for each item, we try to buy it and now we've spent price[k], and we iprice[k] money left, and we have j+1 items purchased.) 
#11452  Dancing the CheekyCheekySolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force sorting strings
 Solution Description:  Knowing that you're given somewhere between 2 and 3 times the dance, the dance must have no fewer than (length/3+1) steps. Start with this value and see if it works. If not, keep increasing the length until you find the right answer. For example:
Input: 123124123124
The smallest amount of steps possible is 5, so we try that:
12312 41231 24
This isn't correct, so we try 6:
123124 123124
And this is correct. 
#11455  Behold my quadrangleSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  Sort the input numbers. If they're all equal, then you have a square. If the first and second are equal, and the third and fourth are equal, then it's a rectangle. If the sum of the lowest three numbers are strictly greater than the fourth number, it can be a quadrangle. Otherwise, it's a banana. 
#11458  Hot SpotSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  other graph
 Solution Description:  We want to do a breadthfirst search through the game space until we find a state with an 'R' in the upper right corner.
Strings are a pretty natural representation of the gamestate, so I'd recommend encoding the state:
.GR.
....
....
....
as the string ".GR............."
Use a HashMap of String > Integer to map states to the distance they are from the starting configuration.
There isn't much to do here except brute force through all the possible moves. I generate all possible jumps, and then check each one to make sure that it doesn't put a blue robot in an illegal position, and then check that I haven't visited that state before. 
#11461  Square NumbersSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  dynamic programming math
 Solution Description:  Create an array up to 10001 that holds the number of square #'s up to and including i. You can populate it with a for loop and one simple if statement:
if(Math.pow((int)Math.sqrt(i), 2) == i)
res[i] = res[i1]+1;
else
res[i] = res[i1];
Then, given a and b, output res[a]res[b1]. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  brute force math
 Solution Description:  For each a and b, just run through all squares from 1^2 to 316^2 and count how many lie between a and b. 
#11463  CommandosSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall
 Solution Description:  With infinite soldiers, you may as well send each one out to a different building. Let s and t be the start and end locations. Let d[i][j] be the distance between i and j. This ith soldier needs d[s][i] + d[i][t] time to complete his mission.
So, the answer is the maximum across all 0 <= i < n of d[s][i] + d[i][t]. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
