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 Counting

Solved 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... easy-medium 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 += (i-2)/2
a[i] = a[i-1] + 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 Multiplication

Solved 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 64-bit 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 right-aligned

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 - Squares

Solved 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[i-s] + 1)

...where s is some square (1, 4, 9, 16, etc.)


#11412 - Dig the Holes

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

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

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a good medium-level 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 previously-top 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[i-1][j][0] + a[i-1][j+1][1]
a[i][j][1] = a[i-1][j-1][0] + a[i-1][j-1][1]

Pregenerate this entire array and output the values as necessary. You will need to use 64-bit integers to store many of the higher values.


#11428 - Cubes

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

Solved 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 point-slope 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 shopping

Solved 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[i-price[k]][j+1])
(So for each item, we try to buy it and now we've spent price[k], and we i-price[k] money left, and we have j+1 items purchased.)


#11452 - Dancing the Cheeky-Cheeky

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

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

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
Solution Description: We want to do a breadth-first 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 Numbers

Solved 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[i-1]+1;
else
----res[i] = res[i-1];

Then, given a and b, output res[a]-res[b-1].

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 - Commandos

Solved 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 PHPGraphLib - Click For Official Site