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 BoxSolved 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 AgainSolved 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[i1] + a[i] >= 0)
dp[i] = dp[i1] + a[i]
p[i] = p[i1] + 1
(If dp[i1] + 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  RailsSolved 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  KingSolved 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[k1] </> C
Now, to change the strict inequalities into nonstrict inequalities, note that, when working with integers:
a[k+h]  a[k1] < C
is the same as
a[k+h]  a[k1] <= C1
And in the same vein:
a[k+h]  a[k1] > C
is the same as
a[k1]  a[k+h] <= (C+1)
Now, all you have to do is create the graph, and run BellmanFord (or so) to detect a negative weight cycle. 
#516  Prime LandSolved 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 ProblemSolved 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 ShowdownSolved 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(nk, 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 (nr). 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 32bit 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 32bit 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  CompromiseSolved 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[i1][j] > dp[i][j1])
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 MasterSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  I'd rate the coding on this as easymedium... 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 movetoablefromthere 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 movetoablefromthere 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 breadthfirst search from the beginning, and print out the value in the exit cell afterwards, or "Trapped!" if it's 1. 
#534  FroggerSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry floyd warshall
 Solution Description:  This problem uses a slightly modified FloydWarshall 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 FloydWarshall 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 RecoverySolved 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 lefthand side, and EFG must be in the righthand 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 righthand 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 CatanSolved 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 depthfirst search from each node and see what the farthest depth you can go is. 
#540  Team QueueSolved 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 CorrectionSolved 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 '98Solved 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][j1] * [sum over all played teams, k] (p[k][j1]*w[i][k])
Output p[i][4] for each team. 
#543  Goldbach's ConjectureSolved 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 (np[i]) is in p[] as well. Then, output p[i] and (np[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 CargoSolved 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 FloydWarshall problem. Most of the work is in setting up the graph because of strings.
Once you have an adjacency matrix, run FloydWarshall 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 HandsSolved 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 easymedium 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  BurgerSolved 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 n2 burgers, and therefore the probability of the chain is (1/2)^(n2). 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 (n2) C (n/2  1). Therefore, the answer for a given n is:
1  [ ((n2) C (n/2  1)) * (1/2)^(n2) ]
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 miniDP 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[nk]). 
#558  WormholesSolved 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 negativeweight cycle. The usual choice is the BellmanFord algorithm, which runs in O(E*V).
Now, BellmanFord will only detect negative cycles from a given source, but we want to find negative cycles in the entire graph. Running BellmanFord 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 BellmanFord from this vertex. 
#562  Dividing coinsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:   Solution Description:  This can be formulated as a 01 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 01 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[i1][j] (if wi > j)
a[i][j] = max(a[i1][j], wi + a[i1][jwi]) (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  RiskSolved 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 nofrills FloydWarshall 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 FactsSolved 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 nonzero digits for each one. I don't really mean nonzero, 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  JugsSolved 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 DepositsSolved 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 SnailSolved 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 UpSolved 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 BinarySolved 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 ReviewSolved 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 inloop 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 nonvowel 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  ClockHandsSolved 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 (360rtn), otherwise, just return rtn. 
#580  Critical MassSolved 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 N1 and add an "L", or a stack of N2 and add "LU", or a stack of N3 and add "LUU". So, the number of safe stacks of size n is a[n] = a[n1] + a[n2] + a[n3].
Now, to find the number of unstable stacks of size n, just take 2^n  a[n]. 
#583  Prime FactorsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  As you might guess by the name, this is a straightup 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 runSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a sort of shortestpath 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 0index 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][j1] + p[c][i][j]
Obviously, this minimum is only across cities that have an outgoing flight to city i on day j.
Output a[n1][k] at the end. 
#591  Box of BricksSolved 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 (heightaverage) to a running sum. Output this sum at the end. 
#594  One Little, Two Little, Three Little EndiansSolved 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
