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 Bandwidth

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: medium Algorithms Used: max flow Solution Description: This is a basic maximum flow problem. Just use Edmonds-Karp 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 Hopping

 Solved 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 Floyd-Warshall 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*(n-1)).

# #825 - Walking on the Safe Side

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programmingother graph Solution Description: Just do a breadth-first search from the upper left to the lower-right. 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 Fractions

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

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

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: medium Algorithms Used: brute forcerecursionsortingstrings 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 one-to-one. This isn't explicitly stated in the problem.

# #846 - Steps

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hocmath 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 0-indexed: a[0] = 0 a[i] = a[i-1] + (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 Game

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: mathsorting 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 II

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute forcestrings 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 - Ordering

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: other graphrecursion 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)