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. #820  Internet BandwidthSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  max flow
 Solution Description:  This is a basic maximum flow problem. Just use EdmondsKarp to get the maximum flow from from the graph. The only thing to watch out for is that there can be multiple connections between any two nodes. In this case, just add the connections together. Having a pipe of capacity 10 and a pipe of capacity 20 is the same as having just one pipe of capacity 30.
Don't forget that you need a blank line after *every* case, not just between cases. 
#821  Page HoppingSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall
 Solution Description:  For each case, set up a 100 x 100 adjacency matrix where a[i][j] = infinity, and a[i][i] = 0. Afterwards, for each pair of given integers i and j, a[i][j] = 1.
Run FloydWarshall on the matrix. Iterate through all cells and sum up all entries a[i][j] where a[i][j] is not infinity. Then, determine how many nodes were used, and call this n. Output (sum / n*(n1)).

#825  Walking on the Safe SideSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming other graph
 Solution Description:  Just do a breadthfirst search from the upper left to the lowerright. For each new cell you visit, sum together the number of paths from all 4 directions that are of minimal distance.
Initialize a[0][0] to 1, as there's one way to get to (0,0).
Note that if (0,0) is blocked with an underground passage, then there are 0 ways to get to the station. 
#834  Continued FractionsSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  keep n and d variables. Enter a while(true) loop.
keep an index variable that is incremented each loop, so you know what to output and when:
number = n / d
if index = 0 then "[" + number
if index = 1 then ";" + number
else "," + number
n = (d*number);
swap n and d
if(d == 0)
break

Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  In general, where the two numbers in the input are a and b:
while(a%b > 0)
{
print(a%b)
a = (a/b)*b //integer divison
swap(a,b)
} 
#836  Largest SubmatrixSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force
 Solution Description:  There might be a DP solution to this, but given the small bounds (n = 25), an O(n^6) brute force is just fine.
Iterate through all pairs of vertices (x1,y1) and (x2,y2). For each pair, iterate through every cell in the bounding box between those vertices and check if they're all 1's. If they are, and the area of the bounding box is the largest you've found so far, update your answer. 
#843  Crypt KickerSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  brute force recursion sorting strings
 Solution Description:  Use backtracking to map encoded characters to decoded characters. Compare each dictionary word with the current encoded word to see if it's a possible match, and recurse further if it works.
In general, this strategy takes too long, but you can save a lot of time by trying to match larger words first, as they will determine more information for you.
Note that your mapping must be onetoone. This isn't explicitly stated in the problem. 
#846  StepsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc math
 Solution Description:  If we plot out the first few series of steps, we can see a pattern:
1 *
11 *
111
121 *
1211
1221 *
12121
12221
12321 *
The starred sequences are the ones that cannot be expanded without adding anoter character. Look at them separately:
1 (sum = 1)
11 (sum = 2)
121 (sum = 4)
1221 (sum = 6)
12321 (sum = 9)
Let a[i] be the furthest distance you can go with i steps. Assuming i is 0indexed:
a[0] = 0
a[i] = a[i1] + (i+1)/2
For each input, take the difference between the two points, binary search a[] for this difference, and return the index of the smallest element that is greater than or equal to the difference. 
#847  Multiplication GameSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math sorting
 Solution Description:  Clearly, Stan can win trivially with n between 2 and 9. If the number is between 10 and 18, then even if Stan picks 2, Ollie will win. For numbers between 19 and 162, Stan can pick a number low enough that Ollie can't win, bt high enough that he can win when Ollie only picks 2. From this, a pattern arises.
If n <= 9, Stan wins
Else If n <= 9*2 Ollie wins
Else If n <= 9*2*9 Stan wins
Else If n <= 9*2*9*2, Ollie wins
...etc... 
#850  Crypt Kicker IISolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force strings
 Solution Description:  Look for lines that have the same length as "the quick brown fox jumps over the lazy dog", with spaces in the same places. Then, make sure that that line can be correctly decoded. If it can, use it as your key. 
#872  OrderingSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph recursion
 Solution Description:  This problem is pretty well identical to problem 124...even the sample case is the same. However, you now need to print "NO" if there are no acceptable orderings, and the input/output formatting has changed quite a bit.
See Also:
Problem 124 (Following Orders) 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
