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.

#501 - Black Box

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Use a dynamic array (ArrayList is perfect in Java) to store the numbers as they get entered into the database. Keep the list sorted as you enter elements, so you can binary search for where to insert the next one. In this way, insertion is O(log n), and retrieval is O(1).


#507 - Jill Rides Again

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a largest submatrix DP. Let a[] be the array of input, p[] be the length of the current path, and dp[] be the DP array. The DP runs in O(n) with the following recurrence:

(Base case)
dp[0] = max(0, a[0])
p[0] = 1 (if a[0] > 0)
p[0] = 0 (if a[0] < 0)

(If dp[i-1] + a[i] >= 0)
dp[i] = dp[i-1] + a[i]
p[i] = p[i-1] + 1

(If dp[i-1] + a[i] < 0)
dp[i] = 0
p[i] = 0
(If this street makes the niceness negative, it may as well just not be used)

Keep track of the best dp[i] you've found as you iterate through, and at the end, use p[i] to determine how long the path is.

In Java you'll need to use BufferedReader.


#514 - Rails

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
Solution Description: Keep a stack of integers that represents the station, and a list of integers that has all the trains in order on side A.

Iterate through the input. For each train, if it's on top of the stack, then pop it off, and if it's somewhere in the list, the push all the trains in front of it onto the stack, then discard the train. If the train isn't in either location, then it must be buried in the stack and is therefore unreachable, so the arrangement can't be made.


#515 - King

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:math
other graph
Solution Description: This is a constraint satisfaction problem that can be solved with negative cycle detection.

A system of difference constraints is a series of constraints of the form:

x1 - x2 <= C

These systems can be solved by creating a graph with a vertex for each variable, and an edge from x2 to x1 with weight C for each constraint. There exists a solution that satisfies all of the constraints iff the graph does not contain a negative weight cycle.

However, the constraints given in this problem are not of this form. They contain multiple variables, are sums rather than additions, and have strict inequalities. Luckily, we can convert them.

Let a[i] be the sum of the first i variables in the sequence (a[0] = 0). Since all of the constraints relate contiguous subsequences, we can rewrite the constraint

x_k + x_k+1 + ... + x_k+h </> C

as

a[k+h] - a[k-1] </> C

Now, to change the strict inequalities into non-strict inequalities, note that, when working with integers:

a[k+h] - a[k-1] < C

is the same as

a[k+h] - a[k-1] <= C-1

And in the same vein:

a[k+h] - a[k-1] > C

is the same as

a[k-1] - a[k+h] <= -(C+1)

Now, all you have to do is create the graph, and run Bellman-Ford (or so) to detect a negative weight cycle.


#516 - Prime Land

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: First, generate all the primes up to 32767.

At the beginning of each line, set num to 1. For each pair of integers in the input (p,k), multiply num by p^k. At the end, decrement num by 1. This is the number that needs to be factored.

Iterate through your primes array from right to left, checking if num % p[i] = 0. For each p[i] that stasifies this, continue dividing by p[i] until you can't any more. Output p[i], and how many times you divided by p[i].


#524 - Prime Ring Problem

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
recursion
Solution Description: This is a fairly simple backtracking problem. 15! is too large to compute brute force, but pruning reduces this greatly.

Try all different combinations of numbers (with 1 first, of course) brute force, but don't follow branches where there is not a prime sum. So for instance, n = 4:

1 2

1+2 is prime, so continue

1 2 3

2+3 is prime, so coninue

1 2 3 4

3+4 is prime, and 1+4 is prime, so this is a good sequence.

Now back track to...

1 3

1+3 isn't prime, so backtrack

1 4

1+4 is prime, so continue

1 4 2

Backtrack

1 4 3

Continue

1 4 3 2

Output

And now we've exhausted everything, so stop.


#530 - Binomial Showdown

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Factor out the larger factorial on the bottom of your nCk formula by looping from n to max(n-k, k).

Use doubles for all internal calculations, and manually calculate the remaining factorial on the bottom and divide what's left by it.

Output.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The "proper" way to do this problem is something like this:

For example, recognize that 8C6 is:

8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
-----------------------------
(6 * 5 * 4 * 3 * 2 * 1) * (2 * 1)

So, find the maximum of r and (n-r). Take the factors between n and this maximum. So, 8 and 7 in this case. Now, go through the rest of the factors in the other factorial in the denominator (2 and 1 here) and divide them into the numerator factors whenever you can. So:

(8 * 7) / (2 * 1) = (4 * 7)

At the end, multiply your factors together to get your answer.

This may seem like it would take far too long to run, because of cases like C(1,000,000,000, 500,000,000), but of course, that won't fit into a 32-bit integer. It's not too hard to show that you'll only have about 20 factors remaining at most after you factor out everything in common. If you have more than that, the number won't fit into a 32-bit integer, and therefore it won't show up in the input :)

There also exists a hacky, less thoughtful solution: Do the first step , as before, of eliminating common factors from top and bottom. Then, multiply all the factors in the numerator into a double, and the same for the denominator, and output round(num/den). This works for *this* problem, but in general you should avoid this strategy, because of rounding errors.


#531 - Compromise

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
strings
Solution Description: This is an extended version of Longest Common Subsequence where you have to actually return the LCS, and not just its length.

Let a[] and b[] be arrays of strings that hold the two sequences, of length an and bn respectively. Let dp[][] be the completed LCS DP array. This is how to get the LCS from the array:

i = an
j = bn

while(dp[i][j] > 0)
{
if(a[i] == b[j])
--append a[i] to front of output string
--decrement i and j
else if(dp[i-1][j] > dp[i][j-1])
--decrement i
else
--decrement j
}

Whenever the strings match, they must be part of the LCS, so add one to the output string. Whenever the string don't match, move the array cursor in the direction that has the highest number.


#532 - Dungeon Master

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: I'd rate the coding on this as easy-medium... just because my program hit 100 lines (including blank lines and bracket lines, though) and it takes a little extra work to do the array traversal... anyways

It's BFS (breadth first search). Start at S, add all move-to-able-from-there squares to a queue. Set each of their 'distance' values to 1. Repeat, but this time setting 'distance' values equal to the distance value of the square they came from + 1 - and add their move-to-able-from-there squares if they have not already been given a distance.

If you reach E, output. If not, output failure.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: You can use one array to hold the map and distance information at once. I use -1 for untraversed, and -2 for walls. Anything >= 0 is the distance to that cell. Just do a breadth-first search from the beginning, and print out the value in the exit cell afterwards, or "Trapped!" if it's -1.


#534 - Frogger

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
floyd warshall
Solution Description: This problem uses a slightly modified Floyd-Warshall algorithm (the minimax variant). First, set up the adjacency matrix with the distance between two rocks, that is, a[i][j] is the distance between rocks i and j.

Run Floyd-Warshall with this line:

a[i][j] = min(a[i][j], max(a[i][k],a[k][j]))

For every midpoint, we have the option of not using it, or using it if both the path into and out of the midpoint are shorter than the direct route.

Try Problem 544 (Heavy Cargo) for something similar.


#536 - Tree Recovery

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:recursion
Solution Description: You can build the tree recursively, and then do a postorder traversal. Here's how:

Preorder: DBACEGF
Inorder: ABCDEFG

The first element in the preorder traversal must be the root, so D is the root. Then, ABC must be in the left-hand side, and EFG must be in the right-hand side, as per the inorder traversal, so recursively build the left subtree with "BAC" as the preorder, and "ABC" as the inorder. Do similarly for the right-hand side.


#537 - Artificial Intelligence?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Keep three variables, P, U, I, all set to -1. Search for the first equals sign and store its index. Read the character before it to see what variable you should modify. Then, find the index of the units letter. Check the charater before it to see if there's a prefix. Then, parse the real number between the first index and the second index. Apply the prefix if necessary.

At the end, the variable that is still -1 is the one that needs to be calculate it, so calculate it, round it, and print it. Make sure you have a blank line after *every* case.


#539 - The Settlers of Catan

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
other graph
Solution Description: With the small quantity of edges, you can just do a depth-first search from each node and see what the farthest depth you can go is.


#540 - Team Queue

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: This is a fun problem because you get to make your own data structure :)

Make a Node object that holds an integer (the Node's number), and a pointer to the Node behind it in the queue.

Keep an array of pointers to the "leaders" of each team. The leader of a team is the person in that team who is farthest back in the queue. Also, keep a pointer to the head and the tail of the queue.

Dequeueing a person is fairly simple. If they are the team leader, then that means that nobody else from their team is in the queue, so set the leader of that team to null. Then, set the head of the queue to the person behind the person you dequeued. Set the tail to null if they were the last person in the queue.

Enqueueing is a little bit more involved. First, determine if the person you're adding has teammates in the queue. If they do, put them at the end of that team, and make them the new team leader.

If the person has no teammates, just put them at the end of the queue, but still make them the new team leader.

Use a HashMap to map people to their teams so that you can get constant time access.


#541 - Error Correction

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:searching
Solution Description: Keep to arrays, r[] and c[] where r[i] is the sum of row i, and c[i] is the sum of column i. You can fill these in as you take in the input. It isn't necessary to store the actual matrix.

Search through each array and look for cells with odd sums. If no cells have odd sums, then the matrix is OK. If one row and one column are odd, then output "Change bit (row,column)". Otherwise, the matrix is corrupt.


#542 - France '98

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: Let p[i][j] be the probability the team i makes it to round j (0 = first round, 4 = wins championship). Let w[i][j] be the probability that team i wins against team j.

p[i][0] = 1.00 for all i, because each team gets to the first round.

p[i][j] = p[i][j-1] * [sum over all played teams, k] (p[k][j-1]*w[i][k])

Output p[i][4] for each team.


#543 - Goldbach's Conjecture

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
searching
Solution Description: Use the Sieve of Eratosthenes to generate the primes up to 1,000,000 into an array p[] where p[i] is the ith prime. Then for each input n, search through your primes array to find an i such that (n-p[i]) is in p[] as well. Then, output p[i] and (n-p[i]) as the two primes.

Also, watch out for an error in the problem description: It says "odd primes" but 2 should also be included.


#544 - Heavy Cargo

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: Create an arraylist for mapping, so that as you're taking the adjacencies in, you can just use arraylist.indexOf(x) to get the appropriate index you'll use for the adjacency matrix. In this process, if the arraylist does not contain the city already, just add it. The result is, you can just do:

int input = scan.nextInt();
dist[arraylist.indexOf(a)][arraylist.indexOf(b)] = input;
dist[arraylist.indexOf(b)][arraylist.indexOf(a)] = input;

Then, run floyd warshall on the adjacency matrix with one modification - instead of taking the min(dist[i][j], dist[i][k]+dist[k][j]), you have to take max(min(dist[i][k], dist[j][k]), dist[i][j])

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: This is a maximin Floyd-Warshall problem. Most of the work is in setting up the graph because of strings.

Once you have an adjacency matrix, run Floyd-Warshall with this line:

a[i][j] = max(a[i][j], min(a[i][k], a[k][j]))

Try Problem 534 (Frogger) for something similar.


#555 - Bridge Hands

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Use a comparator and 4 arraylists to hold the hands and sort them.

After that, just output. However, make sure that you use a stringbuffer for your output, as it will TLE if you don't.

This problem takes a *little* bit of coding to do... so I'd rate it as easy-medium ish.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
strings
Solution Description: Just make an array of Card objects for each person, take in the input, and sort it. There isn't anything really tricky here except making sure that the cards are dealt to the right people.

In Java, use StringBuffer for your output.


#557 - Burger

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: Let's say that A is a cheeseburger, and B is a hamburger. We want to know the ratio of strings that end in ...AA or ...BB to the number of all strings.

However, this is rather hard to compute. Instead, we can take 1 - P(...AB OR ...BA). If a string ends in AB or BA, then we know that a coin was flipped for each of the previous n-2 burgers, and therefore the probability of the chain is (1/2)^(n-2). The question then is how many of these strings exist.

We have (n/2 - 1) A's, and (n/2 - 1) B's to permute. So, the number of different strings is (n-2) C (n/2 - 1). Therefore, the answer for a given n is:

1 - [ ((n-2) C (n/2 - 1)) * (1/2)^(n-2) ]

There's a problem however. The intermediate calculations of the first term can be very large, and the second term can be extremely small. Thus, we need to work in logarithm space to do these calculations.

Also, there is a lot of input for this problem, so you must be able to calculate (n C k) very quickly. You can do a mini-DP like this:

Let a[i] be the sum of log(k) from k = 1 to i. Now, to calculate (n C k), just take e^(a[n] - a[k] - a[n-k]).


#558 - Wormholes

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: All we need to do in this problem is find a negative-weight cycle. The usual choice is the Bellman-Ford algorithm, which runs in O(E*V).

Now, Bellman-Ford will only detect negative cycles from a given source, but we want to find negative cycles in the entire graph. Running Bellman-Ford V times (once from each vertex) isn't acceptable, so we need a better method.

Make a new dummy vertex that has an edge to every other vertex with weight 0, and run Bellman-Ford from this vertex.


#562 - Dividing coins

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: This can be formulated as a 0-1 knapsack problem. You want to split the coins as evenly as possible, so consider a knapsack of size sum/2 where sum is the sum of all coins.

Consider each coin to be of equal weight and value. The 0-1 knapsack recurrence is:

a[i][j] = highest value with weight j, using items up to i

a[i][0] = 0 for all i
a[0][j] = 0 for all j

a[i][j] = a[i-1][j] (if wi > j)
a[i][j] = max(a[i-1][j], wi + a[i-1][j-wi]) (if wi <= j)

a[n][sum/2] will be the amount of money the first person gets. Return the difference of this and (sum - this).


#567 - Risk

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: Run Floyd Warshall on a graph with edge lengths 1. Output dist[i][j], since it's just shortest path.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: This is a no-frills Floyd-Warshall problem. In Java you'll need to use BufferedReader and StringBuffer. Don't forget to put a blank line after *every* case.


#568 - Just the Facts

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: Pregenerate your answers in the following way:

Generate the factorials from 0 to 10000, but only keep the last 8 digits of the factorial, and remove any trailing zeros BEFORE doing so.

Keep a res[] array, and for each element just take the last digit of whatever you've currently got for that factorial, where res[i] = last digit of your i! (which is really only the last 8 digits of i!)

I suppose technically this is a really really really simple DP, so I'll mark it as such.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Pregenerate all the factorials from 1 to 10000, but only store the last 6 non-zero digits for each one. I don't really mean non-zero, but the last 6 digits that aren't part of the string of zeroes at the end of the number. Some of these may indeed be 0 and that's fine.

By only keeping the last 6 digits, you can use an array of longs instead of an array of BigIntegers. You'll want longs even though it's only 6 digits as 6 digits times 4 or 5 digits will exceed an int for some of the larger factorials.

For every input number, just print out the last of the digits that you have stored for that number (use mod 10).


#571 - Jugs

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:other graph
Solution Description: This problem can be formulated as BFS on a graph where each node is a different pair of jug volumes. So for instance, the node (4,8) represents the state where jug A has 4 gallons of water, and jug B has 8 gallons of water.

Starting from (0,0), run BFS on this graph. The edges from each node are the 6 operations you can perform. When you a hit a node where jug B has the necessary amount of water, stop.

Along the way, keep an array the points to the predecessor node, and an array that keeps track of the actions taken. For example, p[i][j] is the predecessor of node (i,j), and a[i][j] is a string stating the action taken to move from p[i][j] to (i,j).

At the end, you can use a stack to trace your route back from the goal.

See Also:
Problem 10603 (Fill)


#572 - Oil Deposits

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Setup the array, and iterate through it using flood fill whenever you find an oil patch. For each flood fill, fill with '*' so that you don't double count an oil deposit, and add one to a counter.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: A simple floodfill problem. Iterate through your input array, and whenever you encounter an '@', BFS from that point and change all adjacent @'s to asterixes.


#573 - The Snail

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
simulation
Solution Description: Run the simulation, and if the snail's position drops below 0 or above H at any time, output as appropriate. Make sure that you check for the snail being above H before sliding him back for the night.

There's almost definately a closed form for this, but it's just easier to run the simulation.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
simulation
Solution Description: Just simulate the process. Remember that a snail cannot climb a negative distance. Also, make sure that you check for the snail leaving the well *before* he slides back down. And it isn't exactly clear in the problem, but "sliding back to the bottom" means sliding *below* height 0.


#574 - Sum It Up

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
sorting
Solution Description: With only 2^12 subsets, you can easily brute force the solution. First, sort the numbers. Then, try all possible subsets (bitshifting is the nicest way). When you find a subset with the requested sum, make a string out of it, like "50+23+5", and add it to an output array. Make sure you have no duplicates in the output array.

At the end, sort the output array descending and print it out. Luckily, '+' is lexicographically before '0', so it suffices to just sort the strings and print them out.


#575 - Skew Binary

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Keep a counter.

Loop through each character of your number, and add to your counter:

ans += (Math.pow(2, a.length()-i) - 1) * (a.charAt(i)-'0');


Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: For the ith character from the right in the input string, add (character) * (pow(2,i+1)-1) to an output variable. While the answer *should* fit in a signed int, it's easier just to use an unsigned int or a long.


#576 - Haiku Review

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Iterate through the line, with a stage variable and a stagecount variable. You'll also need a justHadVowel variable.

Whenever you encounter a vowel, if you didn't justHadVowel, add to the stagecount and set justHadVowel.

Whenever you encounter a '/', check that stagecount is either 5 or 7 depending on the stage, and either output the line number if its not, or clear stagecount, increment stage, and !!make sure to set justHadVowel to false!!.

At the end of iterating, check the last stage's count, since there won't have been a '/' to trigger the in-loop stagecount check.

Output Y if you never found a problem.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Keep three variables, l (the line number), v (a boolean for variables), and c (number of syllables found so far). At the beginning, l = 1, v = false, c = 0.

Iterate through the string. When you encounter a vowel and v is false, set v to true and increment c. When you encounter a non-vowel letter or space, set v to false. When you encounter a slash or the end of string, check that the number of syllables is correct for the current line number. If it is, then increment the line number. If it isn't, then output the line number. If the line number is 4 at the end of the string, then output "Y".


#579 - ClockHands

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Get percentage values for the hours and minutes values and multiply them both by 360.0. Take the absolute value of the difference between the two, and if it's over 180.0, take 360.0 - it.

Output using System.out.printf to make the formatting easy.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
Solution Description: Let h and m be the hours and minutes respectively. If h = 12, then set h to 0.

The angle from 12 o'clock to the hour hand is (h*30) + (m/2). The angle to the minute hand is (m*6). Take the absolute value of the difference of these quantities, call it rtn. If it's greater than 180, return (360-rtn), otherwise, just return rtn.


#580 - Critical Mass

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: It's easier to determine the number of safe arrangements rather than the number of unstable ones.

Say we want to make a safe stack of n blocks. We can take a stack of N-1 and add an "L", or a stack of N-2 and add "LU", or a stack of N-3 and add "LUU". So, the number of safe stacks of size n is a[n] = a[n-1] + a[n-2] + a[n-3].

Now, to find the number of unstable stacks of size n, just take 2^n - a[n].


#583 - Prime Factors

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: As you might guess by the name, this is a straight-up prime factorization problem. Use the Sieve of Eratosthenes to generate all the primes up to sqrt(2^31) or, very approximately, 100,000.

Prime factorization is as simple as searching through all the primes in increasing order and dividing the input number by each prime that evenly divides it. You only need to search up to sqrt(n) for any input number n, as only one prime factor of n can be greater than sqrt(n). (Quick proof: if more than one prime factor is greater than root n, then their product is greater than n, so they can't both be prime factors of n)

Once you've searched all the primes up to sqrt(n), if you have some amount left over greater than 1, then that is the last factor. For example:

78 has three prime factors, 2, 3, and 13.

- Divide by 2, we have 39 left over.
- Divide by 3, we have 13 left over.
- Can't divide by 5.
- Can't divide by 7.
- 11 is greater than sqrt(78), so we stop. We still have 13 left over, so 13 must be the last factor.

There's a lot of I/O in this problem, so use StringBuffer and BufferedReader in Java.


#587 - There's treasure everywhere!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
math
Solution Description: The only part that's at all tricky here is parsing the input. Keep track of the x and y location as you parse each instruction. For diagonal directions (NW, NE, SW, SE), just multiply by 1/sqrt(2) before adding to x and y.


#590 - Always on the run

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a sort of shortest-path problem, but with a simple DP solution. Let a[i][j] be the minimum cost to get to city i after j days. Let p[i][j][k] be the price of flying from i to j on day k.

Initially, a[0][0] = 0 (I 0-index my cities), and every other cell is infinity. (Normally I would use 1 billion to represent infinity, but here you might be adding up to 1000 infinities, so it's best to use something like -1 and manually check for it rather than just add blindly.)

a[i][j] = Min across all previous cities, c, of: a[c][j-1] + p[c][i][j]

Obviously, this minimum is only across cities that have an outgoing flight to city i on day j.

Output a[n-1][k] at the end.


#591 - Box of Bricks

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Take in the integer n.

Sum all the heights given.

sum /= n;

sum up the total difference between each stack and the new value of sum.

output this count / 2.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:greedy
math
Solution Description: Store all the input numbers into an array, and find the average height of each stack. Then, iterate through your array. For every stack that's higher than the average, add (height-average) to a running sum. Output this sum at the end.


#594 - One Little, Two Little, Three Little Endians

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: Note that the order of the bytes is reversed, but not the order of the bits. This is a common problem that seems to trip people up. So, for example:

11111111 00010001 10001000 00000000

becomes

00000000 10001000 00010001 11111111

You can just use bit shifting to create the new number.





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