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.

# #601 - The PATH

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: medium Algorithms Used: other graph Solution Description: This is a floodfill problem that is simple to understand, but takes a lot of work. Run floodfill 4 times: white from the left, white from the right, black from the top, black from the bottom. If white can reach the right side from the left, white wins. If black can reach the bottom from the top, black wins. If there is an unfilled cell adjacent to a cell that white can reach from the left, and adjacent to another cell that white can reach from the right, then white can win in one move. Same thing goes for black, but top to bottom. Also, if there is an unfilled cell on the right adjacent to a cell that white can reach from the left, white can win in one move. Same thing goes for black, but on the bottom, from the top. And if none of these conditions hold, there is no winning path. Watch out for the special case of a 1x1 matrix with an unfilled square.

# #602 - What Day Is It?

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hoc Solution Description: This is a simple, but fairly tedious problem... but luckily, Java has a GregorianCalendar class that can handle all of the operations for you! All you need to do is throw out the invalid dates, and GregorianCalendar can handle the rest.

# #608 - Counterfeit Dollar

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hocbrute force Solution Description: With only 12 coins, you can just test whether the three weighings are consistent with each coin being heavy or light. So for instance, if a coin is heavy, then it must push the scale down on whatever side it's on, and it must not be present if the scales are even.

# #612 - DNA Sorting

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: brute force Solution Description: Make sure you only put a blank line BETWEEN cases. Essentially, you just brute force through the string, when for each character, you iterate through each character after that one and check if it's less - then add to a counter if it is. I kept an array of Strings and an array of two dimensional variables (like a Point object), where the first dimension is the index in the String array for that entry's DNA string, and the second being the count for that string. You can then write a custom comparator to sort by the second dimension first, and then first dimension, and output using the entries in the string array.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: strings Solution Description: Keep an array of strings, and an array of sortedness. Calculate the sortedness for each string, and then just output the strings in order of sortedness. Don't forget to put a blank line *between* cases only.

# #615 - Is It A Tree?

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: other graph Solution Description: Use hash tables to hold all the nodes and edges, since the integer labels may be *any* number. First, check the indegree of each node. There must be exactly 1 node of indegree 0, which is the root. Then, all other nodes must have indegree 1. Next, run a search from the root to make sure that all nodes can be reached. If any of these conditions fail, the graph is not a tree, otherwise, it is. Note the special case of a null graph, which is a tree by the definition given in the proble description.

# #619 - Numerically Speaking

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: mathstrings Solution Description: This problem is basically just doing base 26 conversion, with a little bit of fiddling around because there's no symbol for 0. When you're converting from words to numbers, just treat 'a' as 1 and 'z' as 26. Treat every place as a different power of 26. So for instance: "bz" = 2*(26^1) + 26*(26^0) When you convert from numbers to words, keep taking mod 26 to get the next character, but now 'a' is 1, 'b' is 2, ... 'y' is 25, but the exception is that 'z' is 0.

# #620 - Cellular Structure

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: recursionstrings Solution Description: This problem can be done with just backtracking. For each string, test whether it's of the form of a fully-grown, or mutagenic string. If it might be one of the latter, take off those two characters and test the inside, recursively, until you hit either a single "A" (simple) or a different string that can't be decomposed (mutant). The bounds on the problem must be pretty small, because this ran in about 0.1 seconds in Java.

# #621 - Secret Research

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: ad hocstrings Solution Description: Just check for the four different cases in the order they're given. There's nothing more to this than a 4-branch if statement.

# #623 - 500!

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: dynamic programming Solution Description: loop from 1 to 1000, at each iteration multiplying a tmp BigInteger by the current i, and storing the current tmp in a res[] array of strings. take in the input (n) output (n + "!") output res[n];

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: dynamic programmingmath Solution Description: Pregenerate an array of 1001 items where a[i] is i!. Start with a = 1, and then multiply by i until you have all the items filled. Then you just need to print out a[i] for any i you're given. Use BigInteger and it'll run fast enough, even in Java.

# #624 - CD

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programmingstrings Solution Description: This is just a knapsack DP problem where v[i] = w[i] (value = weight). See my solution for Problem 10130 (SuperSale) for the recurrence. As far as outputting the string goes... Keep an array s[][] where s[i][j] is the string that represents the (an) optimal arrangement for i weight and j items. Whenever you update a[i][j] (the dp array), s[i][j] = s[i-Wj][j-1] + "j " if you added a new item. Fairly simple. See Also: Problem 10130 (SuperSale)

# #636 - Squares (III)

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: brute forcemath Solution Description: Starting at min(2, largestDigitInNumber+1) for base test the value in each base, to see if Math.pow((int)Math.sqrt(value), 2) == value Where value is the decimal value of your number in the current base. You can't use Integer.parseInt() here, since the base can be up to 100, and that function can't handle bases that high.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: brute forcemath Solution Description: Just try to interpret the input in all bases from 2 to 10, checking for sqrt(num) == (int)sqrt(num). When this condition is true, output the current base and move to the next number.

# #637 - Booklet Printing

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hoc Solution Description: Notice that pages get printed in a sort of zigzag pattern. So for 8 pages: 8, 1 2, 7 6, 3 4, 5 Use ceil(n/4) sheets. You start at the upper-right, zigzag down to the bottom, and then zigzag up in the opposite direction. If any number would be too large, replace it with "Blank". So if we only had 7 pages, the 8 would say "Blank" instead. This pattern holds for any number of pages > 1. When you have only 1 page, then you get a special case where you only use one side of the piece of paper.

# #639 - Don't Get Rooked

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute forcerecursion Solution Description: If you know how to deal with rook polynomials, then the recursion for this problem should be obvious. Pick an arbitrary cell that is free and isn't threatened, and take the maximum value of (putting a rook there + 1) and not putting a rook there. You can brute force this problem as well, as there are only 2^16 possible combinations.

# #640 - Self Numbers

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: simulation Solution Description: Hold an array of booleans, and iterate N from 1 to 1000000. For each n, recurse through the d(n)'s and set the array element at the current d(n) to true. If you ever encounter an element that's already true while doing this, stop recursing, since all the d(n)'s from that number on will have already been set. Iterate once more through the array, outputting to a stringbuffer each time you encounter a false element. Make sure you didn't set the values of n to true during iteration, and make sure you don't print an extra line at the end of your output.

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: Create an array of 1,000,000 booleans, initially true. Iterate through it, and for each number i, set a[d(i)] to false. Then, iterate through the array and print out all i where a[i] is true. In Java, use StringBuffer as the output is massive.

# #642 - Word Amalgamation

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: ad hocbrute forcesearchingsortingstrings Solution Description: Use a hash table or sorted array to hold the dictionary. Then for each input word, find all permutations in lexicographic order and see if the dictionary contains each permutation. Use binary search if you're using an array rather than a hash table.

# #644 - Immediate Decodability

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: brute forcestrings Solution Description: Given the small bounds, just do a pairwise comparison between all strings in a set to see if any is the prefix of any other.

# #657 - The die is cast

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: medium Algorithms Used: other graph Solution Description: This is a slightly trickier variant of the average floodfill problem. Scan the input looking for non-background pixels (* or X). When you encounter an asterix, start a floodfill that changes all asterixes it encounters into periods, and starts a second "sub"-floodfill when it encounters an X. When you hit an X, the sub-floodfill should search out all connected X pixels and change them to asterixes, and NOT to periods. When you exit this sub-floodfill, increment a counter that keeps track of how many dots have been found in the super-floodfill. When a super-floodfill ends, add the running total to an array that will be sorted at the end. A good test case is: 5 5 XX**X XX**X ..... ..... XX**X 0 0 ...for which you should get two dice, {2, 2}.

# #661 - Blowing Fuses

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: easy Algorithms Used: simulation Solution Description: Let a[i] be the power of the ith device, and let b[i] be true if the ith device is on, and false otherwise. Just run through the list of togglings and for each one, if b[i] is false, add a[i] to a running total. If b[i] is true, subtract a[i] from a running total. Toggle b[i] afterwards. Keep track of the maximum as you go along. If the maximum at the end is greater than te limit, then the fuse was blown. Otherwise, the fuse was OK and the maximum is what you output.

# #673 - Parentheses Balance

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: strings Solution Description: Create a stack of characters and iterate through the input string. When you encounter a ( or [, push it onto the stack. When you encounter a ) or ], pop the top character off the stack and confirm that it's the opposite bracket, ie, ( for ) and [ for ]. If the stack is empty when you try to pop it, the string is incorrect. If the stack is not empty after you finish iterating through the string, then it's also incorrect. And of course if you find a mismatched bracket, it's incorrect. Don't forget that blank lines are considered correct.

# #674 - Coin Change

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programming Solution Description: This is a Coin Change DP straight-up. Just build the table beforehand, and then output the answer from the table each time. You can use unsigned ints (which is why the upper bound is so strange).

# #675 - Convex Hull of the Polygon

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: medium Algorithms Used: 2D geometry Solution Description: WARNING: THIS PROBLEM IS BROKEN If you submit an actual solution, you will likely get Runtime Error for no particular reason. However, if you submit something like this in C++: #include int main() { char s; while(gets(s)) { printf("Its ok\n"); } return 0; } ..it'll get accepted (thanks to Anindya). If you want to know how to *actually* do the problem though, read below: This is just straight up convex hull. Graham's Scan is a fast and intuitive way of doing convex hull, so look it up on Wikipedia for a thorough description. The first and last points of the polygon are the same, so ignore the last point in the input. Then, when you output the points on the convex hull, output the first one once more at the end.

# #686 - Goldbach's Conjecture (II)

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: math Solution Description: Use the sieve of Eratosthenes to generate primes up to 32768. For each n, iterate through the primes( with variable i ) and see if primes[n-primes[i]] = true If so, add to a counter for that n. Check each iteration, and break when the prime you're considering is > n/2 to remove duplicates.

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: mathsearching Solution Description: Use the Sieve of Eratosthenes to generate all primes up to 35000 or so. For each input n, iterate through the primes array from 2 to n/2. If n - p[i] is prime, then add one to a running total. Output the total at the end.

# #694 - The Collatz Sequence

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: simulation Solution Description: Just run the collatz sequence as given using longs, and count the iterations. The sample output shows spaces before the outputs, but that's wrong - they don't want any.

 Solved By: wesley Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: mathsimulation Solution Description: Just run through the given algorithm until a generated value is 1 or greater than the limit. Output how many values you generated. Note that the generated value that exceeds the limit is not included in the total. The initial value *is* included in the total.

# #696 - How Many Knights

 Solved By: peter Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: Given n and m (make n the smaller #): if(n == 1) output m if(n == 2) output (m+3)/4 + (m+2)/4 otherwise output ((n+1)/2)*((m+1)/2) + (n/2)*(m/2)

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: trivial Algorithms Used: math Solution Description: In general, knights can be placed in a staggered pattern: X.X.X .X.X. X.X.X In this case, the closed form is ((m+1)/2)*((n+1)/2) + (m/2)*(n/2) If one of the dimensions is 1, then you can fill the entire board with knights: XXXXXXXX If one of the dimensions is 2, then you can fill sets of 2 rows: XX..XX..X XX..XX..X

Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By 