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.

#10700 - Camel trading

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:recursion
strings
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:greedy
sorting
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 force
math
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 programming
strings
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:sorting
strings
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 geometry
math
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 hoc
math
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

Solved By:wesley
Theory Difficulty:hard
Coding Difficulty:medium
Algorithms Used:dijkstra
Solution Description: Keep four grids of booleans, where a[i][j] is true if there is a rose at (i,j). Each of these grids is a different rotation of the given grid. So, 0, 90, 180, and 270 degrees rotated.

Use Dijkstra's algorithm to find the shortest path, but for every cell you visit, the cost is now a quadruplet of costs, (N, E, S, W), that represents how many roses you will trample if you try to get to that cell with your starting direction being N, E, S, or W. An example:

.....
.....
..PRR
.....
.....

We treat all co-ordinates as though you were facing North originally. The quadruplet of distances for the cell (2,2) is (0, 0, 0, 0) of course, because you trample no roses to get to your starting location.

The cell (2,3) however has the quadruplet (1, 0, 0, 0). If we begin by facing north, then cell (2,3) represents a move to the right. If we being by facing east, cell (2,3) represents a move downwards, and there is no rose there.

The problem is that there may be many ways to get to a cell that are not strictly better than any other. So, a cell can contain *multiple* quadruplets. There may be a way to get to a cell with quadruplets (2, 1, 0, 0), (1, 1, 1, 1), (2, 0, 1, 1) for instance.

To make this run in time, you want to 1) keep as few quadruplets as possible, and 2) only expand paths that still have a chance at improving your solution:

1) Whenever you are going to add a new quadruplet to a cell, make sure that there are no other quadruplets that are strictly better. Strictly better here means that at least one number is lower, and no number is higher. If nothing is strictly better, add your quadruplet and then remove any quadruplets that are strictly worse than the one you added. Also, don't add a quadruplet to a list if it already exists. That just means that you found a different path to the same cell, and there's no need to search both.

2) Whenever you reach an edge, take the maximum value of the four numbers in your quadruplet. This is the highest number of roses you may trample to get to that point. Always keep track of the lowest maximum that you've found so far, and do not expand any path whose maximum is >= the best you've found. This path can clearly never lead to any improvement.

Be wary of the case N = 1.





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