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 Time

Solved 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[lo-1]) / (hi - lo + 1)


#10205 - Stack 'em Up

Solved 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 Non-zero 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 N-M+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 non-zero 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!(n-k)!

n! = n * (n-1) * (n-2) * ... * 1
log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(1)

So to calculate log(n C k), just calculate:

[log(n) + ... + log(1)] - [log(k) + ... + log(1)] - [log(n-k) + ... + 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 (n-k) is larger. An alternate definition for n C k is:

[n * (n-1) * ... * (k+1)] / [(n-k) * ... * 1]

OR

[n * (n-1) * ... * (n-k+1)] / [k * ... * 1]

If k is larger, use the first definition, and if n-k 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 - Satellites

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

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

Solved 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(n-1)] * [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(n-1))
F(2n-1) = F(n)^2 + F(n-1)^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 Emirp

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

Solved 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 i-x with j-1 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[i-1][j-1] + a[i-2][j-1] + ... + a[i-f][j-1]

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 Problem

Solved 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 non-decreasing x-coordinate. 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 x-direction 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 Trees

Solved 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 = (mx-x1)
Let dy = (my-y1)

The other two corners are (mx-dy, my+dx) and (mx+dy, my-dx).


#10252 - Common Permutation

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

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

Solved 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[Xi-1] != 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 - Suffidromes

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

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

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:dijkstra
floyd warshall
Solution Description: With Dijkstra, Floyd-Warshall, 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 all-pairs shortest path. Run Floyd-Warshall 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 Station

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

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

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

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

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
math
Solution Description: Consider the upper-right piece of the pentagon. Let A be the upper vertex, B be the right-most 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 Points

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

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