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.

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programming Solution Description: This is very similar to Matrix Chain Multiplication. Let dp[i][j] be a pair (max, min) that represents the maximum and minimum value you can get from bracketing the elements from i to j. dp[i][i] = (a[i], a[i]) dp[i][j] = ([max across all k from i to j] dp[i][k] OP dp[k+1][j], [min across all k from i to j] dp[i][k] OP dp[k+1][j]) Where OP is either + or * as required. See Also: Problem 348 (Optimal Array Multiplication Sequence)

# #10701 - Pre, in and post

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: recursionstrings Solution Description: This problem is identical to 536 (Tree Recovery). See the solution there. See Also: Probelm 536 (Tree Recovery)

# #10703 - Free spots

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: brute force Solution Description: make an array of booleans. with two nested for loops, you can visit each spot in the rectangle, and set it to true. if it was false, add to a counter output appropriately (w*h-count)

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute force Solution Description: Start with an array of booleans all set to false. For every pair of co-ordinates, set all booleans in that range to true. Make sure that x1 < x2 and y1 < y2 because they might not be. Afterwards, just output the number of falses.

# #10714 - Ants

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: greedysorting Solution Description: Take the input in with a buffered reader, and be careful because the ant positions will be given on different lines. Keep track of the farthest left and right ants, and the two ants which are closest to the middle of the stick. For your shortest time, output min(lenOfStick - closestToMiddle). For your longest, output max(len-farthestLeft, len-farthestRight). Make sure for your shortest, though, that if you're taking the closestToMiddle, you're getting the difference between him and his closest end of the stick.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: sorting Solution Description: Keep two variables, min and max, that'll be the eventual output. For each ant, find two distances, the distance to the nearer end, and the distance to the farther end. min = max(distance to near end, min) max = max(distance to far end, max) And what about the business of ants changing direction when they collide? Doesn't matter. Consider what it be like if they walked through each other. It would be exactly the same. Note that the numbers can be separated by newlines and tabs, not just spaces. In Java, you'll need to use BufferedReader and StringBuffer, so this can pose a bit of a problem. To resolve it, just grab the next line of input whenever your StringTokenizer runs out of tokens.

# #10717 - Mint

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute forcemath Solution Description: There are only (50 C 4) combinations of coin sizes, so this can be brute forced. For every set of 4 coin types, determine the LCM of their sizes. Note that the LCM of a set can be defined recursively, and that LCM can be implemented quickly with GCD: lcm(x1, x2, x3, x4) = lcm(x1, lcm(x2, lcm(x3,x4))) lcm(x1,x2) = (x1*x2) / gcd(x1,x2) Let h be the desired height. For each set of 4 coin types, determine the largest p and the smallest q such that: p*lcm <= h q*lcm >= h If h % lcm = 0, then p = q = (h/lcm). Otherwise, p = h div lcm, and q = p+1. Output p*lcm and q*lcm.

# #10739 - String to Palindrome

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: easy Algorithms Used: dynamic programmingstrings Solution Description: Let a[l][r] be the cost to convert the substring (l...r) into a palindrome. Let s[i] be the ith character in the string. a[l][r] = 0 if l >= r (1 character or the empty string is already a palindrome) a[l][r] = a[l+1][r-1] if s[i] == s[j] (Here we check the inner string because the outsides match) a[l][r] = 1 + min(a[l+1][r-1], a[l+1][r], a[l][r-1]) (We can choose to modify one of the outside characters so that they match, or delete one of the outside characters on either side) There is never any need to insert a character, because that only creates more work.

# #10763 - Foreign Exchange

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: sortingstrings Solution Description: With n = 500,000 you'll definitely need an O(n) solution. Hash table to the rescue! Create a hash table that takes a string and gives back an integer. The integer is the number of times that string has appeared unmatched. For each input string, look for it's partner. So, if you get "1 2" look for "2 1" in the hash table. If you have a copy of "2 1", that is, if h("2 1") > 0, then decrement h("2 1"). Otherwise, increment h("1 2"). Keep a running variable that counts how many items are in the hash table. Increment it when you add an item, decrement it when you remove an item. At the end, if this variable is 0, output "YES". Otherwise, output "NO".

# #10773 - Back to Intermediate Math

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: 2D geometrymath Solution Description: The fastest way to cross is to just aim for the other shore and not care about how far the river pushes you downstream. So the time for the fastest path is just d / u. The shortest way to cross is of course a straight line, so you must aim the boat upstream such that you exactly counteract the river's flow. The leftover power will get you across, so by Pythagoras, the time for the shortest path is d / sqrt(u^2 - v^2). As we can see from the above equations, if u == 0, or u < v, then you can't determine the difference because you have undefined or unreal results. Also, you cannot determine the difference if v == 0 because then the two paths would not be different, as the problem requires.

# #10783 - Odd Sum

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: math Solution Description: You can do a closed form, but it might even be faster just to do the one for loop and counter needed to pull this one off. I feel bad giving a solution for this, and I don't think it'll be needed, but: Iterate from a or a+1 if its even, adding two each time, and adding the current # to a counter. Output the counter.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: math Solution Description: Don't bother with any closed forms. With the small bounds, just iterate from a to b and add up all the odd numbers.

# #10784 - Diagonal

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: First, we need to know how many diagonals an n-gon has. Each vertex connects to every other vertex except itself and its neighbours. Also, each diagonal is shared between two vertices. Putting it together, the number of diagonals in an n-gon is n(n-3)/2. Given N = n(n-3)/2, we can rearrange it into quadratic form: n^2 - 3n - 2N = 0 Solving the quadratic equation: n = (sqrt(8N + 9) + 3) / 2 We only take the positive root because the negative one always gives us a negative answer, which we obviously can't use. The final answer is the ceiling of the above formula, because it might not be integral.

# #10789 - Prime Frequency

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hocmath Solution Description: Use the Sieve of Eratosthenes to generate the primes up to 2001. Let a[i] be the number of times the character with ASCII value i appears in the input. Go through all i from 0 to 255 and output character i if a[i] is prime.

# #10790 - How Many Points Of Intersection?

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: To get a feel for how the pattern in this problem works, take the example of four dots in the bottom row, and one dot on top. Let the dots in the bottom be B1...B4, and the dot on top be A1. There are no points of intersection. If we add another dot on top (A2), then the line A2-B1 crosses 3 lines, A2-B2 crosses 2 lines, A2-B3 crosses 1 line, and A2-B4 crosses 0. If we add A3, then we get 6 intersections, then 4, then 2. Adding A4 gives us 9, then 6, then 3. Look at this pattern: 0 3 + 2 + 1 6 + 4 + 2 9 + 6 + 3 ... Or more explicitly: 0 1 * (3 + 2 + 1) 2 * (3 + 2 + 1) 3 * (3 + 2 + 1) Note that there is a triangular number sequence going horizontally, and a triangular number sequence going vertically. This gives us the final result of: tri(A) * tri(B) = A(A-1)/2 * B(B-1)/2

# #10791 - Minimum Sum LCM

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: easy Algorithms Used: math Solution Description: This is a prime factorization problem with a lot of picky cases. The first thing to see is that the prim factorization of a number is almost the minimum sum LCM set. I say almost because you have to keep copies of the same factor multipled together. For example, say N = 36. The prime factorization is 2^2 * 3^2. Obviously the minimum set isn't {2,2,3,3} because this would have an LCM of 6. The set is actually {2^2,3^2} or {4,9}. So, for *most* cases, just find the prime factorization, keep copies of the same term together, and return the sum of the products (so 4 + 9 = 13 in the above example). However, there are some issues. First there's N = 1, and N = 2^31 - 1. For N = 1, you must output 2. This is a little bit counterituitive, because the set {1,1} contains two of the same number, and therefore, isn't truly a set. However, by the problem definition you must have at least two numbers in your set. For N = 2^31 - 1, you must output 2^31. This is a problem if you're using unsigned integers, of course. But I wouldn't bother changing to signed integers or longs. Just hardcode this case. The other issue involves numbers that are powers of a single factor. So for instance 5^1, or 2^10. You can't just give {5} or {1024} as your sets, because these have only one number. Instead, you need to add 1 (so {5,1} = 6 and {1024, 1} = 1025). As far as prime factorization goes, here's how you can do it. We know our limit is 2^31, so we can generate all the primes up to sqrt(2^31) ~= 2^16 using the Sieve of Eratosthenes, and use these to factor N. Scan through the list of primes from 2 to sqrt(N), and divide N by each prime that it's divisible by (as many times as you can). Keep track of these primes as they are (obviously) factors of N. Once you've gone through all the primes <= sqrt(N), there will be one of two cases. Either N = 1, in which case you're done, or N > 1, in which case N now equals the last factor of (the original) N. This is because you can have no more than one prime factor greater than the square root of the number. So if N > 1, record N as another factor.

# #10798 - Be wary of Roses

Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By 