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. #10502  Counting RectanglesSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  brute force dynamic programming
 Solution Description:  Apparently the brute force actually runs in time, at least for C++ users, but in general an O(n^6) algorithm with n = 100 is extremely unwise. So instead, an O(n^4) solution:
Pregenerate an array where a[i][j] = the sum of all cells from (0,0) to (i,j). This can be done in O(n^2) if you use a simple inclusion/exclusion DP. In general:
a[i][j] = a[i1][j] + a[i][j1]  a[i1][j1] + (value of (i,j))
...but be careful around edges.
Once you have the array filled, run a brute force through all pairs, and calculate the sum of all cells between (x1,y1) and (x2,y2) using the array. The general formula is the same as before, again being careful around the edges.
If the sum of the rectangle is equal to the size of the rectangle, then all the cells in that rectangle are "1" and it must be valid. Keep a running total of how many you find. 
#10508  Word MorphingSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  Keep an array of strings, and an array of booleans where u[i] = true means that the ith string has been used already. Set the first string as the current one.
Print out the current string and mark it as being used. Search through all other strings to find one that differs in only one character. Make this the new current string. Repeat this until you've gone through all strings.
You can use Scanner in Java, but time is tight. 
#10509  R U Kidding Mr. Feynman?Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  So we want to solve the given formula for n^3:
n^(1/3) = a + dx
n = (a + dx)^3
n = (a^2 + 2*a*dx + dx^2)(a + dx)
n = (a^3 + 2*a^2*dx + a*dx^2 + a^2*dx + 2*a*dx^2 + dx^3)
n = (a^3 + 2*a^2*dx + a^2*dx) [Dropping higher order dx terms]
n = (a^3) + 3*a^2*dx)
dx = (n  a^3) / (3*a^2)
Let a be the largest integer such that a^3 <= n. Then, solve for dx and add it to a. 
#10515  Powers Et Al.Solved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Make an arraylist to hold integers.
Essentially, you start with a (just the very last digit of m).
You then record in the arraylist the last digits of a, a^2, a^3, a^4, until you get a repetition (don't include that one).
You return the entry in position:
b1 % arraylist.size();
This is because the last digit follows a pattern, and since there are only 10 digits to choose from, the pattern isn't going to be very long without repetitions. You just write down the pattern, and mod the exponent to get the approprite one. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  This is a bit of a number theory problem. First, recognize that we only need the last digit of m. When every you multiply m by itself, only the last digit has any effect on what the last digit of the result will be. Next, notice that there's a cycle in what the last digit will be when you keep multiplying it by itself:
0  0
1  1
2  2 4 8 6
3  3 9 7 1
4  4 6
5  5
6  6
7  7 9 3 1
8  8 4 2 6
9  9 1
So, depending on what n % 4 or n % 2 is, we can determine what element in the cycle should be outputted. Determining n % 4 or n % 2 is problematic though if n is so large. However, if we take just the last two digits of n, we can determine both of these quantities!
So take the last digit of m, and the last two digits of n, and use the cycles above to determine what the final digit should be.
Don't forget the special case of n = 0. 
#10530  Guessing GameSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force greedy
 Solution Description:  For each transcript,
create a high and a low array.
for each number that is said to be high or low, put it into the corresponding array.
when you get the 'right on' number, check each array to ensure that all the low numbers are lower than it, and the highs are higher than it. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Keep two arrays of 10 booleans, high and low. Whenever you read a number i and it says "too high", set high[i] to true. Do likewise for "too low".
When you encounter "right on" with the number x, check that for all i set to true in high, i > x. Check also that for all i set to true in low, i < x. If either of these condidtions are violated, Stan is being dishonest. 
#10533  Digit PrimesSolved 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, and then make an array, a[], where a[i] is the number of digit primes from 0 to i. For each given range (lo,hi) output a[hi]  a[lo1].
It doesn't seem possible to do this problem in Java. Even with BufferedReader, you can't read the input in time. 
#10534  Wavio SequenceSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dynamic programming
 Solution Description:  This is a Longest Increasing Subsequence (LIS) problem, but you need to run LIS twice. Also, it must be the O(n log n) version of LIS, and not the O(n^2) version. Check Wikipedia for the algorithm description.
Take the case 1 4 2 3 2 4 1 as an example. We run LIS twice:
Forwards:
1 2 2 3 2 4 1
Backwards:
1 4 2 3 2 2 1
Let f[i] be the ith element of the forwards LIS, and b[i] be the ith element of the backwards LIS.
Find i such that min(f[i], b[i]) is maximized. This will be the center of the largest Wavio sequence. Output (min(f[i],b[i])*2  1). 
#10550  Combination LockSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  simulation
 Solution Description:  Just simulate the process. Each number is 9 degrees, of course (360/40 = 9). Make sure you don't accidentally go around a whole turn when you don't need to.
For instance, if the input is 40 40 40 40, the answer should be 1080. 
#10557  XYZZYSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  Firstly, change all positive energies into negative, and negative energies into positive. Now the energies are more intuitively like costs. Positive is bad, negative is good.
Clearly we're trying to find the shortest path to the end, and we may have negativeweight cycles. Therefore, BellmanFord will be the algorithm of choice.
Now, just because we have a shortest path with cost < 100, that doesn't mean we can actually *use* that path. The net cost may be < 100, but there may be a section that takes more than 100 energy to traverse. So we need to modify BellmanFord a bit. Every time you relax an edge, if the resulting relaxed distance is >= 100, don't relax it, because we can't actually use it.
If you find a negativeweight cycle, don't just output "winnable" right away. Make sure that you can actually reach the cycle from the start, and make sure that you can actually reach the end from the cycle. 
#10566  Crossed LaddersSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry searching
 Solution Description:  Binary search on the width of the road. The initial bounds are 0 and min(x,y).
Given the width of the road, and the length of the ladders, you can find the intersection of the two lines. If the yvalue of the intersection is greater than c, increase the width of the road. Otherwise, decrease it. 
#10573  Geometry ParadoxSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  2D geometry
 Solution Description:  There are no impossible cases in this problem. If you're given r1 and r2, then the outer circle must have radius (r1+r2). If you're given t, then assume that t is the radius of the outer circle, and that the inner circles have radius (t/4) each.
Now, just calculate the area of the large circle and subtract the areas of the smaller circles. 
#10579  Fibonacci NumbersSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Use BigIntegers to pregenerate the Fibonacci numbers up to 1000 digits long (this is a bit fewer than 5000 numbers). Then, just output the ones asked for. 
#10583  Ubiquitous ReligionsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc other graph
 Solution Description:  Use unionfind to join together people who have the same religions. Then, iterate through all the students to see how many set leaders there are. You'll need to search through in O(n), so use a hashset or a boolean array rather than some O(n^2) comparison. 
#10591  Happy NumberSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc dynamic programming
 Solution Description:  We can use memoization to calculate answers very quickly. Keep an array, a[], where a[i] is 1 if i is happy, 1 if i is unhappy, and 0 if we don't know. The size of this array is 9 * (9^2) because the largest value is 999,999,999, so the sum of squares cannot exceed 9 * (9^2). Set a[1] to 1, because we know 1 is happy.
For each number, keep cycling through the sequence until you hit a number you've already seen, either in the current sequence, or in the array. If it's in the array, then set every number in you found in the sequence to whatever that array element is. If you find a cycle of numbers that are all not in the array, then they are unhappy. 
#10594  Data FlowSolved By:  wesley  Theory Difficulty:  hard  Coding Difficulty:  medium  Algorithms Used:  dijkstra max flow other graph
 Solution Description:  This is a minimumcost maximum flow problem. Basically, it's the combination of shortest path and maximum flow. The general idea is not too difficult. You do EdmondsKarp to get the maximum flow, but you replace the BFS with a weighted shortest path algorithm.
Dijkstra is the best choice, except that the graph will have negative costs after you reverse edges. You can do BellmanFord, but unfortunately that's too slow for this problem (unless you're lucky in C perhaps). Luckily, there exists a compromise. You can run BellmanFord once at the beginning of the algorithm to set the graph up in such a way that Dijkstra will work from that point on. In this problem, because there are no negative costs to begin with, you don't need BellmanFord at all, and you can use Dijkstra to initialize the graph, but it doesn't matter much runtimewise.
I suggest reading the following to understand how this "graph initialization" part works. Read the subsection "Successive Shortest Path Algorithm":
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
