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. #10200  Prime TimeSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  First, we need to be able to check if numbers up to ~100,000,000 are prime. The memory limit prevents you from running the Sieve of Eratosthenes that high (in Java at least), so instead, run the Sieve for numbers up to 11,000 or so. Using these primes, we can perform prime factorization to see if a number is prime.
For i from 0 to 10,000, let b[i] be true if n^2 + n + 41 is prime, and false otherwise. Pregenerate this array before processing input. Now you can just read off the answers. However, this requires checking up to 10,000 entries per test case, and there are a lot of test cases.
We can use DP to speed up our answer retrieval. Let a[i] be the number of elements <= i for which b[i] is true. Now, for every input pair (lo, hi), return:
(a[hi]  a[lo1]) / (hi  lo + 1) 
#10205  Stack 'em UpSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Just simulate the shuffles and print the results out at the end. Note that you are given each shuffle as a sequence of 52 integers, but not necessarily over 2 lines. It could be over 1 line, or maybe 52 lines. Don't just naively grab 2 lines. 
#10209  Is This Integration ?Solved By:  peter  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  2D geometry math
 Solution Description:  It takes a bit of math... You have to be careful  I made a lot of mistakes and consequently had to work through them all.
Let's call the kinds of areas x, y, and z in order of biggest to smallest.
Imagine a line between the upper left corner of the square, and the tip of the bottom z area. This forms a right triange that you can calculate the area of with ease.
Then, our goal is obvious > calculate the area of the wedge of the circle belonging to the arc (that swings up from the bottom left corner) that is bounded by the hypoteneuse of the triangle we just formed.
Add the area of the wedge and the area of the triangle, and subtract that sum from half the area of the square. Multiply by 2 to get z.
y = area of the square  (area of a quarter circle radius a)  (z*2)
x = (a*a)  4*y = 4*z
output x, y*4, z*4 
Solved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  The four arcs intersect at four points. Call the top one (between D and C) E and the right one F. Call the center of the entire shape O.
AE and AF define a sector of a circle centered at A. Find the area of this sector, and then subtract the area of the triangles AEO and AFO. Multiply this by 4, and you have the area of the center piece: (a^2) * (pi/3  sqrt(3) + 1).
From this, it's fairly simple geometry to determine the size of the other two areas. 
#10212  The Last Nonzero Digit.Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Given the high time limit (10 seconds) and the moderate bound on N, it's OK to do this in O(N).
Multiply all numbers from N to NM+1 together to get N P M. Of course, this will be extremely large, so after every multiplication, keep taking % 10 while possible to remove trailing zeros, and then take % 1000000000 to keep only the necessary nonzero digits. You need to keep one more digit than the largest digit you multiply by to avoid losing information.
Use longs for all calculations. At the end, output the result % 10.
Watch out for M = 0. Output 1 in this case. 
#10213  How Many Pieces of Land ?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  This is a problem known as Moser's Circle. There's a closed form:
(n C 4) + (n C 2) + 1
Or without the combinatorics:
(n^4  6n^3 + 23n^2  18n + 24) / 24
Seeing as how n can be as large as 2^31, and you need to calculate n^4, you'll need to use BigInteger. 
#10219  Find the ways !Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Given that you'll be computing very large numbers, you'll need to work in logarithmic space.
n C k = n! / k!(nk)!
n! = n * (n1) * (n2) * ... * 1
log(n!) = log(n) + log(n1) + log(n2) + ... + log(1)
So to calculate log(n C k), just calculate:
[log(n) + ... + log(1)]  [log(k) + ... + log(1)]  [log(nk) + ... + log(1)]
What's really nice is that if you use base 10 logarithms, then the number of digits in n C k is just:
floor(log(n C k)) + 1
You can be a bit more efficient in your calculations by looking at which of k and (nk) is larger. An alternate definition for n C k is:
[n * (n1) * ... * (k+1)] / [(nk) * ... * 1]
OR
[n * (n1) * ... * (nk+1)] / [k * ... * 1]
If k is larger, use the first definition, and if nk is larger, use the second one. 
#10220  I Love Big Numbers !Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  brute force dynamic programming
 Solution Description:  Use a BigInteger to calculate the factorials going up through 1000 at O(n);
As you go, store the sums of the digits of each in a result array and output when needed.
You NEED to pregenerate for this problem. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Create an array of BigIntegers and use it to pregenerate i! up to i = 1000. Then just print the sum of the digits for any given index. 
#10221  SatellitesSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  Use the Cosine Law to get the chord distance, and use a*(s+r) to get the arc distance (a must be expressed in radians).
Watch out for a >= 180 degrees. 
#10222  Decode the Mad manSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Hint: the only characters that will appear are (after decoding) the standard lower case letters.
just make two strings, norm and repl.
norm: ertyuiop[]dfghjkl;'cvbnm,.
repl: qwertyuiopasdfghjklzxcvbnm
and, for every character that you get, just output the repl.charAt(norm.indexOf(currentchar))
be careful to handle spaces too 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  simulation strings
 Solution Description:  Hardcode an array of charaters where a[i] is what the character i should be converted to. Make sure that a[' '] = ' ', for convenience.
Iterate through every line, converting every character, and outputting the converted line. Convert each line to lower case as case doesn't matter. This reduces the amount of hardcoding you'll need to do.
You aren't responsible for any character that requires Shift (:"!@#$%^&*() etc.) except for uppercase letters. Here are a few tricky ones that may not match your keyboard:
\ > ;
a > [
s > ]
z > '
x > \
And of course it doesn't help that the problem itself appears to have been written by a mad man. 
#10223  How many nodes ?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  This sequence is the Catalan numbers: 1, 2, 5, 14, 42 ...
Let C(n) be the nth Catalan number. Basically, given k, return n such that C(n) = k.
All you need to do is store the first 30 or so Catalan numbers (use longs of course) in an array, and then for any input k, search the array for k, and return the index of where you found it. 
#10229  Modular FibonacciSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  math matrices
 Solution Description:  This problem requires an O(log n) method to calculate an arbitrary Fibonacci number. The algorithm works off of the idea that you can do the following matrix multiplication (MATLAB notation):
[F(n+1) F(n) ; F(n) F(n1)] * [1 1 ; 1 0]
...and you will get the next set of Fibonacci numbers. Thus, we can derive:
F(2n) = F(n) * (F(n) + 2*F(n1))
F(2n1) = F(n)^2 + F(n1)^2
...depending on whether the number is even or odd. We can use these formulas along with an algorithm that does O(log n) exponentiation to come up with the answer. Take mod m after every addition and multiplication to keep the numbers small, and use longs because you may need to square numbers as large as 2^20, and 2^40 won't fit in an int.

#10235  Simply EmirpSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Use the Sieve of Eratosthenes to generate the primes up to 1,000,000. For each input n, check whether n is prime, and if so, if reverse(n) is prime. Remember that n is only emirp if n != reverse(n). 
#10238  Throw the DiceSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  Let a[i][j] be the number of ways you can sum to i with j dice. You can throw one die to get x, and see how many ways it's possible to get ix with j1 dice. That gives us the following recurrence:
Base Cases:
a[i][1] = 1 if 1 <= f <= i, or 0 otherwise.
a[i][j] = 0 if i < j or i > j*f
Recursion:
a[i][j] = a[i1][j1] + a[i2][j1] + ... + a[if][j1]
a[][] should be an array of BigIntegers. 
#10242  Fourth Point !!Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  2D geometry math
 Solution Description:  Let AB and BC be the two line segments you're given. D is then:
Dx = Cx  (Bx  Ax)
Dy = Cy  (By  Ay)
There are a few different equivalent formulas.
Note that the overlapping endpoints need not be the middle two in the input. Make sure you check which endpoints actually overlap. 
#10245  The Closest Pair ProblemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry sorting
 Solution Description:  An O(n^2) brute force is going to be too slow. It's fairly easy to implement an O(n log n) line sweep algorithm instead.
Firstly, sort the points by nondecreasing xcoordinate. Then, for each point, compare it to all the points to the right, stopping when you come across a point that is farther away in the xdirection than the smallest distance you've found so far.
Now, technically this *isn't* O(n log n), because there are a few cases (like all the points on the same vertical line) where you'll get O(n^2) performance. However, this is definitely sufficient for this problem.
Although not strictly necessary, I'd recommend using BufferedReader and StringTokenizer if you're doing this in Java.
Also, don't square root the distances you find until the very end. sqrt() is a reasonably expensive operation. 
#10250  The Other Two TreesSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  With a bit of math, you can prove that the four trees are the vertices of a square, and the two trees you're given are from opposite corners. So the problem is to find the other two corners.
I'm not the most elegant with geometry in general, but I think this method is pretty good.
Let (mx,my) be the midpoint of the line connecting (x1,y1) and (x2,y2).
Let dx = (mxx1)
Let dy = (myy1)
The other two corners are (mxdy, my+dx) and (mx+dy, mydx). 
#10252  Common PermutationSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting strings
 Solution Description:  Take your strings in and enter them into two character arrays.
All we're looking for is the set of letters that occur in both strings  in proportion. So, if there are two b's in a and two b's in b, then two b's should be in the output.
After we find that common set, just sort it and output it.
To find the common set, just iterate at n^2 through both, and whenever you find a match, add that character to an arraylist that you can later sort, and make those elements = '*'. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  We want to use all letters that appear in both strings, and as many times as possible. Keep two arrays of integers where a[i] is the number of occurences of the letter i in the first string, and b[i] is the same for the second string.
Then, let r[i] = min(a[i], b[i]) for all i. This is how many times we can use the letter i in our output. Iterate through r[] and append the ith letter r[i] times to an output string. Then, just print the string. 
#10258  Contest ScoreboardSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation sorting
 Solution Description:  Keep an array of team (contestant) objects. Each team has an integer array where p[i] is the number of penalty minutes accrued for problem i, and a boolean array where b[i] is true if problem i has been solved. Each team also needs a boolean that is true if they've made a submission, and two ints representing their current number of problems solved and penalty minutes.
For each line in the input, set the given team's active boolean regardless of what the letter is. Then, if the letter is I, add 20 to that teams p[i]. If the letter is C and b[i] is false, make b[i] true, add time+p[i] to their total penalty minutes, and increment their number of problems solved.
At the end, sort the teams by problems descending, then penalty minutes ascending, then team number ascending. Print out all active teams in the order they now appear in the array. 
#10260  SoundexSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  create an array 26 long that holds the soundex values for each character. loop through the input char by char, and output the value if it is > 0 and different from the one to its left. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  strings
 Solution Description:  Hardcode an array where a[i] is the Soundex code for the letter i. Let 0 be the default for all letters that have no code.
For each letter Xi in the input string, if (a[Xi] > 0 && (i = 0  a[Xi1] != a[Xi])) then append a[Xi] to an output string.
If none of the letters in the string have a Soundex code, then just output a blank line. 
#10262  SuffidromesSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  brute force strings
 Solution Description:  Try all reversed prefixes of each string as possible suffixes, in order of increasing length, and lexicographic earliness. So, for the input:
andrew
wesley
Try "", "a", "w", "ew", "na", "dna", "sew", etc.
For each suffix, try appending it to both strings. If it turns only one into a palindrome, then that's your answer.
If at the end you find no solution, there's one more step to try. We may have a case like:
a
<blank line>
In this case, the solution is "b". Or we might have:
a
aa
In this case, "ba" is the correct suffix.
Let S1 be the smaller string, and S2 be the larger string. If both are the same length, then it doesn't matter which you pick. Try 26 more suffixes, "a"+rev(S1) through "z"+rev(S1), where rev(S1) is S1 reversed.
If there are still no solutions after this step, then print "No solution." 
#10267  Graphical EditorSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  simulation
 Solution Description:  Keep an array of characters that represents the current state of the editor. Then, just simulate the process. All of the commands are pretty trivial except for the F (fill) command. This isn't much more difficult though. It's just a basic floodfill. Before doing it though, check if the current colour is the same as the colour you're filling with. If so, don't do the floodfill. You might run into problems if you do. I don't know if the input contains a case like that or not.
Note that when they say "M x N" they mean M columns and N rows, against the normal matrix convention.
In Java, use StringBuffer for your output as there's a lot of it. 
#10269  Adventure of Super MarioSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dijkstra floyd warshall
 Solution Description:  With Dijkstra, FloydWarshall, and Mario, this is one of the most entertaining graph problems :)
So, Mario can essentially warp between any two points provided they aren't too far away, and there are no castles in between. This calls for allpairs shortest path. Run FloydWarshall on the graph, but do not consider castles as midpoints. That is, run it like this:
for k from 1 to A
for i from 1 to A+B
for j from 1 to A+B
<update>
Now, run Dijkstra, but use a two dimensional distance matrix, d[][], where d[i][j] is the minimum distance to node i with j boot uses remaining. At every step, look at where you can warp to (taking away a use of the boots), and look at all the places you can walk to (without using the boots of course).
At the end, output the minimum distance across all a[0][i] for i from 0 to K. 
#10276  Hanoi Tower Troubles Again!Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Run the simulation, and if the number of balls you put on ever reaches Integer.MAX_VALUE, then output 1.
When running the simulation, just setup a one dimensional array that holds the tops of each pole, and try adding each ball by first seeing if there's another ball you can stack on top of. If there isn't, put it onto a free pole. If there isn't one, you're reached the end of the game and you can output count. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math searching sorting
 Solution Description:  At first glance this looks like backtracking, but luckily it has a greedy solution:
For each ball that you want to place, put it on the leftmost peg that it can go on (or on a new peg if the occupied ones are all invalid options).
Pregenerate the solutions for up to 50 pegs, and then print them off as they're asked for.
As you might imagine, there is never a situation where you can place an infinite quantity of balls. 
#10278  Fire StationSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  brute force dijkstra
 Solution Description:  First, run Dijkstra with all of the fire stations as sources. That is, put every fire station intersection into the queue with distance 0 and run Dijkstra with all of them at once.
Now, we'll try to place a new fire station at each vertex. For each vertex, run Dijkstra with that vertex as the source. Use the distance array we got from the first step though, so that the algorithm will terminate when no more improvements can be made.
After each of these Dijkstra runs, determine the maximum distance from a fire station for each house. Keep track of the best one and output it at the end. 
#10281  Average SpeedSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math sorting
 Solution Description:  Keep track of your current speed, the time at which the last speed change took place (in seconds), and how far you had gone when the speed changed. All these variables will be 0 initially.
At every speed change, calculate the difference in time between this speed change and the last one, and update the total distance, time of speed change, and speed accordingly.
At every query, calculate the difference in time between the query and the last speed change, and use this to determine how much farther you've gone since the last speed change. Don't update any of the three variables though. 
#10282  BabelfishSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  Use a HashMap to map the definitions to their words, and use a stringbuffer to output.
I didn't use a bufferedreader, and just barely ran in time with 2.90 seconds. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  searching sorting strings
 Solution Description:  Store the dictionary as a hash table where the foreign word is the key, and then read the requested words out of the hash table.
You can likely use binary search on a sorted array as well, but hashing is a bit simpler.
In Java, use BufferedReader and StringBuffer. 
#10285  Longest Run on a SnowboardSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  dynamic programming recursion sorting
 Solution Description:  My solution for this problem is probably a bit unorthodox.
Let d[i][j] be the length of the longest run that ends at cell (i,j). Initially, d[i][j] = 0 for all (i,j).
Sort the cells by decreasing height, and iterate through them. For each cell, find the maximum d[][] amongst its four neighbours and set d[i][j] to max+1.
At the end, output the maximum value for d[i][j] across all (i,j).
This problem can also be solved by backtracking, as the bounds are quite small. 
#10286  Trouble with a PentagonSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry math
 Solution Description:  Consider the upperright piece of the pentagon. Let A be the upper vertex, B be the rightmost vertex, and C be the point where the square touches the right wall of the pentagon. Let O be the center of the pentagon.
 The line OC is a diagonal of the square, so, the angle ACO must be 45 degrees.
 The line OC is paralell to the bottom of the pentagon, so the angle OCB must be 108 degrees (the interior angle in a regular pentagon).
 This means that the angle ACB must be 63 degrees (108  45).
 Knowing this, and knowing that angle ABC is also 108 degrees, we can use the sine law to get our final answer:
square length = pentagon length * (sin 108 / sin 63) 
#10295  Hay PointsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  ad hoc
 Solution Description:  Use a hash table to map words to their values, and then just check each word in the descriptions to see if it's in your hash table. If it is, add its value to a running total. 
#10297  BeavergnawSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  3D geometry math
 Solution Description:  Let CYL be the volume of the cylinder of diameter D and height D. Let CON be the volume of a cone of diameter D and height D/2. Let cyl be the volume of the inner cylinder of diameter d and height d. Let con be the volume of a cone of diameter d and height d/2. Then we get:
V = CYL  2*CON + 2*con  cyl
pi*r^2*h is the volume of a cylinder, and pi*r^2*h*(1/3) is the volume of a cone, so substitute those in as needed, and solve for d.
At the end, we get:
d = ((pi*D^3  6V) / pi)^(1/3) 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
