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 programming
other 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 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 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 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 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: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 II

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

Solved 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 PHPGraphLib - Click For Official Site