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 Rectangles

Solved 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[i-1][j] + a[i][j-1] - a[i-1][j-1] + (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 Morphing

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

b-1 % 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 Game

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

Solved 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[lo-1].

It doesn't seem possible to do this problem in Java. Even with BufferedReader, you can't read the input in time.


#10534 - Wavio Sequence

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

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

Solved 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 negative-weight cycles. Therefore, Bellman-Ford 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 Bellman-Ford 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 negative-weight 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 Ladders

Solved 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 y-value of the intersection is greater than c, increase the width of the road. Otherwise, decrease it.


#10573 - Geometry Paradox

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

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

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
other graph
Solution Description: Use union-find 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 Number

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

Solved By:wesley
Theory Difficulty:hard
Coding Difficulty:medium
Algorithms Used:dijkstra
max flow
other graph
Solution Description: This is a minimum-cost maximum flow problem. Basically, it's the combination of shortest path and maximum flow. The general idea is not too difficult. You do Edmonds-Karp 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 Bellman-Ford, but unfortunately that's too slow for this problem (unless you're lucky in C perhaps). Luckily, there exists a compromise. You can run Bellman-Ford 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 Bellman-Ford at all, and you can use Dijkstra to initialize the graph, but it doesn't matter much runtime-wise.

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