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.

#10300 - Ecological Premium

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Write out the formula for calculating a premium, and you see that the number of animals is irrelevant.

For each farmer, add (area of farm * rate) to a running sum for the test case and output at the end.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Where a, b, and c are the given parameters for each farmer, the formula for the premium is (a/b) * c * b, or just a*c.

So sum up a*c for each farmer, and output the sum.


#10301 - Rings and Glue

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
other graph
Solution Description: Let i and j be two rings with center co-ordinates (x,y) and radius r. Let d be the distance between their centers. i and j overlap if:

abs(i.r - j.r) < d < (i.r + j.r)

So the rings must be touching, but one must not be entirely within the other.

Use union-find to join rings that are overlapping. At the end, determine which circle is the set leader of the most other circles. Output how many circles belong to that set. Make sure you say "ring" and not "rings" if there is only 1.


#10302 - Summation of Polynomials

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: I don't know what's with all the stuff in the description of this problem. I just know that they want, given n, the sum of a[i] from 1 to n, where a[i] is i^3.

Pregenerate it, keep it in an array, and output what you need. Be careful though, and use longs and not doubles. If you use doubles, the precision error will throw you a WA.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Ignore all but the last two lines of the problem description.

Pregenerate an array of longs where a[i] is the sum of the first i terms. So in general, a[i] = a[i-1] + (i^3). Make sure that i is also a long, or the multiplication will be integer multiplication.


#10303 - How Many Trees?

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Keep an array of BigIntegers, where a[i] is the number of trees you can make with i numbers. In general, to determine a[i], you can do this:

sum = 0
for(j from 1 to i)
{
sum += a[j-1]*a[i-j]
}
a[i] = sum

The intuition behind this can be shown in this example: Say i = 7. If we choose 3 as the root, then numbers 1 and 2 are in the left subtree and 4,5,6,7 are in the right subtree. Therefore, there are a[2] combinations for the left subtree, and a[4] combinations for the right subtree. The total number of combinations with 3 as the root is then a[2]*a[4].

The loop above determines the number of combinations for all possible roots. However, this implementation will not run in time in Java, and may not even in C++. If you determine the first few numbers though, it becomes apparent that they're the Catalan numbers.

a[i] is the the ith Catalan numbers. a[i] can be calculated by (2n)! / n!(n+1)!

So first, pregenerate an array with all factorials up to 2000. Then use these to pregenerate the original array, a[]. Finally, just print a[n] for any input n.


#10304 - Optimal Binary Search Tree

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a DP very similar to Matrix Chain Multiplication.

Let a[i][j] be the cost of the optimal binary search tree using elements {i...j}. Let f[i] be the frequency of element i.

a[i][i] = 0

a[i][j] = [min over all k from i to j] (a[i][k-1] + a[k+1][j] + SUM)

SUM = sum of f[x] for all x from i to j, not including k.

Naively, this algorithm runs in O(n^4). There are n^2 entries to fill in, n possible values of k for each entry, and you must add n numbers for each k. However, if you pregenerate cf[i][j], the cummulative frequency of f[x] from i to j, you don't need to add n numbers for each k, and the runtime becomes O(n^3). Just add cf[i][j] and subtract c[k].

See Also:
Problem 422 (Matrix Chain Multiplication)


#10305 - Ordering Tasks

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is just topological sort. Use an array of booleans for your graph. For every input pair i and j, make a directed edge from i to j. Then, run topological sort, and whenever you remove a node from the queue, append its name to an output string.


#10310 - Dog and Gopher

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: Take the dog(dx, dy) and gopher(gx, gy) coordinates in, and for each point (x, y) that you get:

if(sqrt((dx-x)^2 + (dy-y)^2)/2.0 >= sqrt((gx-x)^2 + (gy-y)^2))
output "he escapes"

otherwise, he doesn't.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:2D geometry
brute force
Solution Description: For each point, calculate the distance from the gopher to the point, and the dog to the point. If the gopher's distance is less than or equal to half of the dog's distance, then the gopher is safe.

Note that the problem description is not very clear on what happens when both animals reach the whole at the same time. The gopher is in fact safe, as implied above with the non-strict inequality.

Make sure that you print out the co-ordinates with exactly three decimal places.


#10315 - Poker Hands

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:hard
Algorithms Used:ad hoc
Solution Description: This is the first problem I've rated as Hard coding in almost 300 problems, and I think it deserves it. I'm quite pleased that I kept it under 400 lines (I've got about 360). You'd be hard pressed to do this is under 200 lines for sure.

It would be tedious to go through the entire process, so here're some guidlelines:

- Sort both players' hands. It'll make the comparisons a lot easier

- Check for hands by decreasing value, i.e. straight flush, then four of a kind, etc. all the way down to high card. Checking four four of a kind, then three, then two, is a lot easier than the other way around

After that, just be really careful.


#10323 - Factorial! You Must be Kidding!!!

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Wow, stupid problem.

You only need to precalc n! up to 13!.
If 0 <= n <= 7 then underflow
If 8 <= n <= 13 then output n!
If 14 <= n then output overflow
If n < 0 && n is even output underflow
If n < 0 && n is odd output overflow

Thanks to Steven Halim for the last part! Annoying - what a headache.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: You can quickly check that the only valid factorials are those between 8 and 13 inclusive. For any input n:

(0 <= n < 8) - Underflow
(8 <= n <= 13) - n!
(13 < n) - Overflow

If n is negative, then output Underflow if it's even, or Overflow if it's odd. I really don't know why there are negative numbers, let alone why this is what you have to do.


#10324 - Zeros and Ones

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: Create an array where a[i] is the sum of the all characters from index 0 to index i.

For each pair of input (x,y) where x <= y, print yes if a[y] - a[x-1] = 0 or (y-x)+1. These correspond to the cases of all 0's and all 1's respectively. Make sure to leave off the a[x-1] term if x = 0.


#10327 - Flip Sort

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:sorting
Solution Description: Keep a counter.

Keep running through the list, switching elements when array[j] > array[j+1}, and incrementing the counter.

Break the loop when you don't switch anything, and output the counter.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: This problem is indentical to Problem 299 (Train Swapping).

Use a dynamic array to hold the numbers. While the array still has numbers in it, find the smallest one, add its index to a running count (assuming a 0-indexed list), and remove it from the list. At the end, the running count is the necessary number of flips.


#10330 - Power Transmission

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:max flow
Solution Description: This is a max flow problem with a slight modification: the vertices have capacities as well as the edges.

Luckily, this isn't too hard to deal with. For each regulator, set up a pair of vertices rather than a single one, and connect them with an edge that has the regulator's capacity. So for the first sample case, you have the following edges (Let X' be the new node for regulator X):

1 1' 10
2 2' 20
3 3' 30
4 4' 40

1' 2 5
1' 3 10
1' 4 13
2' 3 5
2' 4 7
3' 4 20

s 1 infinity
s 2 infinity
s 3 infinity
4 t infinity

s and t are, of course, the source and sink.

Run max flow on this new graph, and you'll get the answer.



#10334 - Ray Through Glasses

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: This is fib sequence. Pregenerate and output.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: If you experiment with a few more terms beyond what you're given, you'll see that it's just the Fibonacci sequence. Pregenerate an array of Fibonacci numbers, and for every input n, just output f[n]. You'll need to use BigInteger.


#10336 - Rank the Languages

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: create the grid

iterate through, and whenever you encounter a grid tile that's not a ' ', flood fill from that area with ' ', and add one to a counter for that character.

output the number of counters for each character according to the specs given.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Hold the input in an array of characters, a[][]. Keep an array of integers (or sortable objects) where n[i] is the number of times the language denoted by letter i has appeared.

Iterate through the character array. Whenever you encounter a letter, i, increment n[i] and floodfill all the cells with the same letter with some null character, like a space or period. At the end, sort n[] and output it all elements where n[i] > 0.


#10338 - Mischievous Children

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The number of ways you can rearrange the letters in a word, given that n is the length of the word is n!.

However, if there are duplicate letters, you must divide that by m! for each unique letter in the word, where m is the number of instances of that letter in the word. For example, HAPPY is:

5! / 2! (don't count the 1!'s!)

You need to use BigIntegers to precalc factorials up to 20!.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The number of ways to arrange a sequence of length l is:

l! / (nA! * nB! * nC! * ...)

Where nX is the number of times the letter X appears in the sequence.

Pregenerate an array of BigIntegers to hold the factorials from 0! to 20!, and then use BigIntegers to do the calculation.


#10340 - All in All

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Iterate through t, with an index variable starting at 0.

For each character in t, if t == s.charAt(index), then index++

if at any point index = a.length(), output yes

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Keep a variable i, initially set to 0. This is the index of s that you're searching for in t. Iterate through t. Whenever the current character in t matches the ith character in s, increment s. At the end, if i is equal to the length of s, then you've gone through the string and have found all the characters. Otherwise, s is not a subsequence of t.


#10346 - Peter's Smoke

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:simulation
Solution Description: Given c = cigs he has
b = butts he has
k = given

while(true)
{
output += c;
b += c;
c = 0;
c = b/k;
b -= c*k;
if(c == 0 && b < k)
break;
}

print output.


Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
simulation
Solution Description: Let rtn be an output variable, and let b be the number of butts Peter currently has, initially 0. Then, just simulate the process:

while(n > 0)
{
rtn += n (smoke all the cigarettes)
b += n (add them to the butt count)
n = b / k (make new cigarettes)
b = b % k (decrement them from the butt count)
}

Output rtn at the end. The input and output will fit into signed ints.


#10347 - Medians

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:2D geometry
math
Solution Description: It's a bit tricky to derive the formula for this problem. Basically, you can prove that the area of the triangle formed by the medians is 3/4 of the area of the original triangle. Then, you can use Heron's formula to get the area of the median triangle, and multiply by 4/3. So in all:

A = (4/3) * sqrt(s(s-m1)(s-m2)(s-m3))

Where m1, m2, and m3 are the median lengths, and s is the semiperimeter of the median triangle:

s = (m1 + m2 + m3) / 2

There are some tricky things to watch out for:

1) The inputs can be real numbers, they need not be integers

2) Output -1 as -1.000

3) The problem is unfortunately worded when it says "The areas should be rounded up". They really mean normal rounding (i.e. round-half-up)

4) Output -1 if a median length is less than or equal to 0, if the area is less than or equal to 0, or if you'd end up with a negative square root.


#10361 - Automatic Poetry

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: There's not much to stay about this one. Just parse this pieces and print them out. Make sure you handle all the edge cases (empty strings). Parsing the string into s1, s2, s3, s4, and s5 makes the output easy to code.


#10369 - Arctic Network

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:greedy
other graph
Solution Description: This is a Minimum Spanning Tree problem, but with a slight modification. You don't return the minimum total weight, but rather the weight of the largest edge in the minimum spanning tree.

Only, that's not quite it either. Each satellite connection (beyond the first) allows you to remove an edge from the spanning tree. So, if e[] is the array of edges in the minimum spanning tree, sorted from largest to smallest, you should output e[s-1] where s is the number of satellite connections.


#10370 - Above Average

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Sum the scores, average them, and loop through an array of them counting which are higher.

Use System.out.printf to format your output.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Store the input into an array, tallying the sum of the scores as you take them in. Calculate the average, and then iterate through the array counting the number of students that are above average. Output this as a percentage.


#10375 - Choose and divide

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Obviously some of these numbers are far too large to calculate, like 10,000! ... But with the guarantee that the answer will be small at the end, we can keep our answer small while we compute it.

Create two lists of numbers. The first is the factors of all the numbers in the numerator, and the second is the factors of all the numbers in the denominator. More explicitly, the value we want is:

(p! / q!(p-q)!) / (r! / s!(r-s)!)

= p!s!(r-s)! / r!q!(p-q)!

So, the first list contains the numbers 1 to p, 1 to s, and 1 to (r-s). The second list contains the numbers 1 to r, 1 to q, and 1 to p-q.

Start with 1.0. We need to multiply by all of the numerator factors, and divide by all of the denominator factors. So, keep multiplying until the number exceeds a certain safe value (say 10,000), and then start dividing until it comes back under that value. In this way, we ensure that the answer never gets too large (overflow) or too small (loss of precision).


#10392 - Factoring Large Numbers

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Given the guarantee that no factor is larger than 1,000,000, we can factor all of these numbers by generating the primes up to 1,000,000 and using just those.

To factor a number given a set of primes, just keep dividing the number by increasing primes until you get 1, or run out of primes. If the latter case, then the remainder will be the final factor.


#10394 - Twin 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 20,000,000 (you actually only need about 18,500,000).

Look through all of the primes to find prime pairs, and store them in some table. For each input, just read the pair from the table.


#10397 - Connect the Campus

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:greedy
other graph
Solution Description: This is a fairly straightforward Minimum Spanning Tree problem. I generate all possible edges, and then use a union-find-based implementation of Kruskal's algorithm.

Union together the nodes that have cables between them, and then run Kruskal on the rest of the graph. I don't even bother filtering out the edges that are unnecessary (because of cables) beforehand.





Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site