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 PremiumSolved 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 GlueSolved 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 coordinates (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 unionfind 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 PolynomialsSolved 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[i1] + (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[j1]*a[ij]
}
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 TreeSolved 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][k1] + 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 TasksSolved 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 GopherSolved 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((dxx)^2 + (dyy)^2)/2.0 >= sqrt((gxx)^2 + (gyy)^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 nonstrict inequality.
Make sure that you print out the coordinates with exactly three decimal places. 
#10315  Poker HandsSolved 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 OnesSolved 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[x1] = 0 or (yx)+1. These correspond to the cases of all 0's and all 1's respectively. Make sure to leave off the a[x1] term if x = 0. 
#10327  Flip SortSolved 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 0indexed list), and remove it from the list. At the end, the running count is the necessary number of flips. 
#10330  Power TransmissionSolved 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 GlassesSolved 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 LanguagesSolved 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 ChildrenSolved 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 AllSolved 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 SmokeSolved 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  MediansSolved 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(sm1)(sm2)(sm3))
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. roundhalfup)
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 PoetrySolved 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 NetworkSolved 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[s1] where s is the number of satellite connections. 
#10370  Above AverageSolved 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 divideSolved 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!(pq)!) / (r! / s!(rs)!)
= p!s!(rs)! / r!q!(pq)!
So, the first list contains the numbers 1 to p, 1 to s, and 1 to (rs). The second list contains the numbers 1 to r, 1 to q, and 1 to pq.
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 NumbersSolved 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 PrimesSolved 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 CampusSolved 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 unionfindbased 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
