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

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

Solved 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[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 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 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 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 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 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 Decodability

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