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 PATHSolved 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 DollarSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc brute 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 SortingSolved 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 SpeakingSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math strings
 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 StructureSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  recursion strings
 Solution Description:  This problem can be done with just backtracking. For each string, test whether it's of the form of a fullygrown, 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 ResearchSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  ad hoc strings
 Solution Description:  Just check for the four different cases in the order they're given. There's nothing more to this than a 4branch 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 programming math
 Solution Description:  Pregenerate an array of 1001 items where a[i] is i!. Start with a[0] = 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  CDSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming strings
 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[iWj][j1] + "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 force math
 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 force math
 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 PrintingSolved 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 upperright, 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 RookedSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force recursion
 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 NumbersSolved 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 AmalgamationSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc brute force searching sorting strings
 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 DecodabilitySolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force strings
 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 castSolved 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 nonbackground 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 subfloodfill should search out all connected X pixels and change them to asterixes, and NOT to periods. When you exit this subfloodfill, increment a counter that keeps track of how many dots have been found in the superfloodfill.
When a superfloodfill 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 FusesSolved 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 BalanceSolved 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 ChangeSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a Coin Change DP straightup. 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 PolygonSolved 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<stdio.h>
int main()
{
char s[100];
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[nprimes[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:  math searching
 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 SequenceSolved 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:  math simulation
 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 KnightsSolved 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
