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.

#400 - Unix ls

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: This isn't so much a computing science problem as it is an intro CMPT 120 homework assignment.

Take the filenames into a string array, and run Arrays.sort

Iterate through the list, with an index variable starting at 0. It's easiest to just have another string array called output[], and then
for ceiling(n/cols) at i
--if index < n
-----output[i] += (spaces needed) + filenames[index++]

and then output your output array

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
strings
Solution Description: Just a simulation, with a little math to get the formatting correct. Where max is the length of the longest filename, the number of columns is

(60-max) / (max+2) + 1

and the number of rows is

ceil(n / columns)


#401 - Palindromes

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Make sure you don't forget the empty line after each output.

Keep two booleans, one to check if its a palindrome, and the other to check if its a mirrored string.

Checking if its a palindrome or a mirrored string independently is pretty easy. Just iterate through the string and perform a check at each character, breaking the loop if the check fails and setting the appropriate boolean to true if the loop never breaks.

Make sure that you set palindrome to true if the length = 1, in all cases.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Hardcode an array of characters, a[], with their reverses. So a['Z'] = '5' and so on.

Compare every character in the string with the one in the mirrored position. If mirror(i) = a[i] for all characters i, then the string is mirrored. And of course, if mirror(i) = i for all i, the string is a palindrome.


#406 - Prime Cuts

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Use a primes sieve to generate the primes, and store in an arraylist.

The rest is just annoying formatting, however be sure to handle when the leftmost prime to output is 'less than 0', or when the rightmost is above N.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Use the Sieve of Eratosthenes to generate all the primes up to 1000. Create an array where a[i] is the number of primes between 1 and i inclusive.

For each number, determine how many primes you need to show based on a[i] and c. Iterate through your array of primes and print the necessary ones out.

Note that 1 is considered a prime number for this problem, and that if c is so large that you're asked to print out more numbers than you have, then just print out all the primes from 1 to n.


#408 - Uniform Generator

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
simulation
Solution Description: Keep an array of MOD booleans, a[], where a[i] is true if i has been generated already.

Starting at 0, generate the next MOD numbers in the sequence. For each number i generated, set a[i] to true. If a[i] is already true, then output "Bad Choice". If you get through all MOD numbers without finding a repeat, then output "Good Choice".


#409 - Excuses, Excuses!

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
strings
Solution Description: Pretty straightforward. The real difficulty is in the poor problem description. Just keep a keywords string, that holds each keyword delimited by a space, and check for every word in the excuse if keywords.contains(" " + current + " ").

Make sure that you treat words separated by the special characters as different words (special characters are like spaces in this problem, so just use replaceAll)

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: This problem is not tricky, but there are some mistakes in the problem description (and the PDF file).

Firstly, [SPMamp".,!?&] should read [#@".,!?&]

Secondly, "If there is more than one worst excuse, you may print them in any order" is actually wrong. You need to print them in the order they appear in the input.

So once you get over these obstacles, the problem is just linear search and string matching. Keep an array of keywords, and check it against every word in each excuse. Remember that words are delimited by any non-alphabetic character, so just use the given characters (#@".,!?&0123456789 ) as delimiters when you parse the string.

Also, the matching is case insensitive, so put the entire string into lower-case, and then search it (as all the keywords are guaranteed to be in lower case). Make sure you keep a copy with the proper case for outputting though.


#412 - Pi

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: One thing to note, when they say 'round to six digits', they actually mean truncate.

keep an array of numbers, and make a gcd function.
as you take in your numbers, check each against what is currently in the array using gcd, and increment a counter whenever gcd == 1. after checking each, put it into the array.

output: sqrt(6*(nC2)/count)

nC2 happens to work out to n(n-1)/2

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Use Euclid's GCD function to determine whether a given pair of numbers shares a common factor. So for all pairs (a,b), if gcd(a,b) = 1, add 1 to a running count.

At the end, the estimate is sqrt(6 / (count / (n*(n-1)/2))). If the count is 0, then return failure.


#413 - Up and Down Sequences

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
Solution Description: Not too much to say here. Just follow the directions carefully. Keep a state variable that means either "increasing", "decreasing", or "neither". Initially, it will be "neither", but whenever you see an increase or decrease, modify it accordingly. (Note, it will never be set back to "neither").

Whenever you change states from "increasing" to "decreasing" or vice versa, store how long that path was. Average them all at the end.


#414 - Machined Surfaces

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:greedy
strings
Solution Description: For each test case
----for each line
--------count spaces
--------minval = min(minval, spaces)
--------total += spaces

output: total - (minval*lines)

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
simulation
Solution Description: You can take the simulation approach and bring each side closer together until they touch, then count the spaces... but the math approach is a lot faster.

Recognizing that the most you can move the surfaces together is the length of the smallest gap across all rows, the answer is simply:

(total) - (n * min)

total = total number of spaces in input
n = number of rows
min = smallest gap across all rows


#417 - Word Index

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: Pre-generate a list of the words where all characters ascend from left to right, and store them in an array.

When you get a word, just brute force iterate through the array, and output the index+1. You COULD binary search as well - if you wanted.

It takes five sets of for loops (four are nested to a degree) to generate the array.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Pregenerate an array of all 83681 strings. Then for each input, just scan the array. If you find it, print out the index. Otherwise, output 0.


#422 - Word-Search Wonder

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: Brute force through the grid, and when you find a character that is the first character of the string you're looking for (a):

Loop through a variable k, from zero to the length of (a)-1. Check in all directions using k to traverse the length of the string in a given direction. You have to hard code this.

If you reach the end of the string in one direction, break out of your loops and output. You can use try catches to handle the 'checking outside your grid array' issue.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
Strings
Solution Description: Completely brute force. For every string, look through the matrix to find all instances of the string's first character. So for "DISC" look for all cells that have a "D". From each of these cells, check all 8 directions to see if the word exists.


#423 - MPI Maelstrom

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dijkstra
Solution Description: Use Dijsktra's Algorithm from processor 0. While running, keep track of the maximum final dist value as you do your final visit to each node.

Output the max.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: There's only one input case, so just run Floyd-Warshall. Then, iterate through a[0][i] for all i, and return the maximum.


#424 - Integer Inquiry

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Use BigIntegers to add.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just use BigIntegers and add the numbers together.


#429 - Word Transformation

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
strings
Solution Description: This is Floyd-Warshall with strings. Each string is a vertex, and two vertices are connected if they differ in only one letter. Note that vertices do not connect to themselves.

So keep an array of strings, and then use it to set up an adjacency matrix. a[i][j] = 1 if the strings with indices i and j differ in only one letter, and a[i][j] = infinity otherwise. Run Floyd-Warshall on the matrix, and a[i][j] will be the distance between any two strings with indices i and j.


#436 - Arbitrage (II)

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: Run warshall on an adjacency matrix, and substitute the max statement with:

adj[i][j] = max(adj[i][j], adj[i][k]*adj[k][j])

Then, at the end, check to see if any adj[i][i] > 1.0, and you have your answer.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: This is just a slightly modified version of Floyd-Warshall. Set up your adjacency matrix, and then run Floyd-Warshall with the following line:

a[i][j] = max(a[i][j], a[i][k] * a[k][j])

At the end, iterate through all currencies and check if a[i][i] > 1. If at least one is, then you have arbitrage.

This is an easier version of Problem 104 (Arbitrage).


#437 - The Tower of Babylon

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:dynamic programming
floyd warshall
other graph
Solution Description: There are two main ways to do this problem... either Longest Increasing Subsequence, or finding the longest path in a DAG.

I prefer the latter, because you can use Floyd-Warshall with the bounds of this problem, and that's much easier that doing LIS.

Let the weight of edge (u,v) be the height of block u, if u fits on top of v, and -Inf otherwise.

Then, run Floyd-Warshall, but with max instead of min. For an arbitrary graph this won't work, but for DAG it's just fine. At the end, maximize (a[u][v] + h[v]) across all (u,v) where h[v] is the height of block v (because we didn't add that during Floyd).


#438 - The Circumference of the Circle

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: Find the perpendicular bisectors of the lines p1p2 and p2p3. The perpendicular bisectors intersect at the center of the circle. Once you have the center of the circle, you can get the radius, and therefore the circumference.

Be careful of infinite slopes. The sample input is pretty versatile so it should help you find any problems concerning that.


#439 - Knight Moves

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:floyd warshall
Solution Description: Pregenerate the answers, by:

First, create an adjacency matrix 8x8x8x8.
It represents the distance between two squares i,j and k,l.
Iterate through all possible entries in the matrix, and make the distance infinity or 1 (1 if a knight on either square can reach the other).

Then run floyd warshall, and for each input, convert the column to a number from 0-8, and the row to a number from 0-8. You'll end up with the i,j for the starting point, and the k,l for the ending point.

Then, just output adj[i][j][k][l].

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: For each starting cell, do a BFS to determine how many moves it takes to get to any other spot on the board.

In case you don't know (and the problem should really tell you this), a knight must move 1 space in any cardinal direction, and then 2 spaces in a parallel direction. That is, a knight has these 8 moves:

........
........
..x.x...
.x...x..
...k....
.x...x..
..x.x...
........


#441 - Lotto

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: C(13,7) is only 720, so you can easily brute force all of the different combinations with 6 nested for loops. The brute force should be pruned well. For instance, if you have 8 numbers to choose from, the first number you choose can only be one of the first 3, as there must be at least 5 numbers left over to choose from afterwards.


#442 - Matrix Chain Multiplication

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: This is a pretty simple parsing problem. Keep a stack of matrices, and a running count of how many multiplications have been done so far.

Iterate through each expression. Ignore all left parentheses. If you hit a character, push that matrix onto the stack. If you hit a right parenthesis, pop the top two matrices from the stack. If their inner dimensions match, add the number of multiplications to the running count and push back the new matrix. If not, output "error".


#443 - Humble Numbers

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
math
Solution Description: See my solution for Ugly Numbers. This is the same thing, except with a 7 as well.

Pregenerate and output.

You can use an array of strings called map to map the string endings. So map[1] = "st" and map[2] = "nd". Then just append map[n%10].

Be careful, though, since you have to accomodate the teens which all end in "th" - and make sure you accomodate the input of 3212.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Pregenerate the array of humble numbers that you'll need, as follows:

For each number, i, you want, search through all ugly numbers, j, below and calculate 2*j, 3*j, 5*j, and 7*j. Find the smallest multiple of j that is larger than the (i-1)st humble number. This is the next number.

Either use longs for intermediate calculations, or be careful not to cause overflows or you'll have some issues around number 5000.

See also: Problem 136 (Ugly Numbers)


#444 - Encoder and Decoder

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Pretty much just do as the problem states. Use a stringbuffer so it'll run in time, and watch out for blank lines and punctuation.

Ad Hoc.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Check the first character of each message. If it's a digit, then the message must be decoded. Otherwise, it must be encoded.

Encoding: Iterate through the string. For each character, append its ASCII valule to an output string. Reverse the output string at the end.

Decoding: Reverse the input string. While there are more characters to process, check the first unprocessed character. If it's a 1, then grab the next three characters as an integer. Otherwise, grab the next two characters. Convert this integer into a character and append it to an output string.

Beware of blank lines, as they *do* exist in the input. If you encounter a blank line, just output a blank line.


#445 - Marvelous Mazes

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: The problem is fairly straightforward.

Use a stringbuffer for output so you can just add to it and save time.

Keep a counter variable, and add to it when you get a number. If you get an !, add a newline to the output. If you get a b or a character, use a for loop to output that many instances of that character to the stringbuffer.

Output a newline after each test case, including the last one.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: For each string in the input, iterate through all the characters. If the character is a number, add it to a running total. If the character is an excalmation point, output a newline. Otherwise, output the character as many times as the running total says, then reset the running total to 0.

Output a newline once you've finished processing each line. You don't even need to handle the test cases as separate entities this way. You can think of it as one big test case with some blank lines in between.


#446 - Kibbles "n" Bits "n" Bits "n" Bits

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
strings
Solution Description: Just use:

Integer.parseInt(a, 16);
Integer.parseInt(b, 16);

To get the integer values, and then do addition or subtraction. For the output, use:

Integer.toBinaryString(whatyouwant)

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just add or subtract, as asked. Make sure that you output 13 bits, even though the maximum used will never exceed 12...

This is especially easy if you have a way of specifying the radix for the input. Using Scanner.nextInt(16) in Java is a speedy way of getting the input.


#448 - OOPS!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
strings
Solution Description: Dump all of the input into one string at the beginning -- it'll be easier to work with.

There isn't much to do here except translate the operations as they come. Don't pay any attention to the valid ranges of registers, addresses, etc. Invalid ones won't come up.

Bitshifting is a very natural way to split and parse the different components.


#455 - Periodic Strings

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
strings
Solution Description: Just try all possible periods, k, from 1 to n, the length of the string. Concatenate the first k characters together n/k times, and see if the resulting string matches the input string.


#457 - Linear Cellular Automata

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: This problem is actually really fun to play with after you've solved it. You can make lots of entertaining patterns. It's like your own little Game of Life!

Set up dna[] from the inputs, and the use an array of integers a[] (with a[19] set to 1) as the initial state.

After that, just simulate the process, printing out each state *before* updating it. Use a temporary array to hold the updated state, and then swap it with a[] after all of the cells have been processed.

Make sure you don't have an extra blank line at the end of your output. There should be a blank line *between* cases only.


#458 - The Decoder

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Take each character in and output that character - 7 in ascii value.

Does not work in Java.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: All you do is read in each character, subtract 7 from the ASCII value, and print it out again. Just make sure that when you read a newline, you put out a newline, and not (newline-7).

I had to do this one in C++ because it just doesn't seem to work in Java. It may have something to do with Java's characters being two bytes instead of one, but I really don't know. If you *do* want to try this in Java though, make sure you use a StringBuffer. You'll get TLE if you print each character individually.


#459 - Graph Connectivity

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Use a union-find structure. For each edge, union the two endpoints. At the end, output the number of unique set leaders (that is, unique values for find(i)).


#465 - Overflow

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Just use BigIntegers to hold the input, and compare each operand and the result to (2^31 - 1). If any exceed this value, say that they're too large.

You may want to watch out for lines with extra whitespace or no whitespace at all. There is no guarantee that there will be whitespace of any particular quantity in the problem description. I haven't checked myself, but best to be careful.


#469 - Wetlands of Florida

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is a pretty standard floodfill problem. Just do a DFS/BFS from each given cell to find the number of water-filled cells it's connected to.

Be warned that you may be asked to floodfill on the same lake more than once, so make sure you clear your visited array each time.


#474 - Heads / Tails Probability

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Given that you're calculating very small numbers, you'll want to work in logarithm space.

log(2^-n) = log(0.5^n) = n * log(0.5)

Use base 10 logarithms. Then, e = ceil(log(0.5^n)) - 1.

To normalize the first few significant digits, take 10^(n*log(0.5) - e). Output this, rounded to three decimal places.

WARNING: There is one very poor test case in the judge input: n = 6.

2^-6 = 0.015625, and the judge's output is:

2^-6 = 1.562e-2

...rather than:

2^-6 = 1.563e-2

Why the judge would choose to round half down (or maybe round even?), I have no clue. I suggest just hardcoding this case.


#476 - Points in Figures: Rectangles

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
math
Solution Description: See my solution for problem 478

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: Keep an array of rectangle objects (just a package of the co-ords). For each point i with co-ordinates x and y, and each rectangle r with co-ordinates (x1,y1) and (x2,y2), i lies inside r if and only if:

(x > x1 && x < x2 && y < y1 && y > y2)

Make sure that you're using strict inequalities, as per the problem description.


#477 - Points in Figures: Rectangles and Circles

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
math
Solution Description: See my solution for 478.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:2D geometry
Solution Description: The same as Problem 476, but with circles as well.

For each point i with co-ordinates x and y, and each circle c with center co-ordinates cx and cy and radius r, i lies inside c if and only if:

sqrt((x-cx)^2 + (y-cy)^2) < r

So just ensure that the distance from the point to the center of the circle is less than the radius.

Make sure that you're using strict inequalities, as per the problem description.


#478 - Points in Figures: Rectangles, Circles, Triangles

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
math
matrices
Solution Description: I used linear algebra to solve each of the cases (triangle, rectangle, circle).

Circle:

Given ax1 and ay1 (coordinates of the point) and cx1 and cy1 (coordinates of the center of the circle):
Create a vector with rows [cx1-ax1] [cy1-ay1] and calculate the length of this vector, sqrt(x^2 + y^2). If the length of the vector is less than the radius of the circle, the point is within the circle since this vector is the distance from the point to the centre of the circle.

Rectangle:

Yes, there's an 'easier' way to do this, but if you do this with linear algebra, you can pretty much copy and paste the solution for the triangle.
Hold an angle variable, and set it to zero. For each side of the triangle, create two vectors a[] and b[], where each is the vector pointing from the point given to an end of the side you are at currently. With these, you can determine the angle between them:
acos(a dot b / |a|*|b|)
Add the angles up for all sides, and if it is equal to 2*PI, the point is within the square.
NOTE: there are two things you have to watch for. Since we're doing floating point calculations, you cannot check that the angle == 0, but rather subtract PI from the angle, and see if the difference is within a margin of error like 0.0000001
ALSO
each time you add an angle, if the angle = PI, automatically fail. This is because this indicates the point is on a line of the rectangle, and that is outside by the specs of the problem.

Triangle:

Same as rectangle, but just do it for three sides. Mind the Note is the same as well.

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
math
Solution Description: The same as Problem 477, but with triangles as well.

For each point i with co-ordinate vector P = (x,y), and each triangle t with co-ordinate vectors A = (x1,y1), B = (x2,y2), C = (x3,y3), i lies inside t if and only if these three conditions hold:

(X is the cross product)

((B-A) X (P-A)) * ((B-A) X (C-A)) > 0
((C-B) X (P-B)) * ((C-B) X (A-B)) > 0
((A-C) X (P-C)) * ((A-C) X (B-C)) > 0

You can interpret * as dot product or multiplication (as the cross product of two-dimensional vectors is scalar).

So just ensure that for each line of the triangle, the point and the vertex of the triangle not involved in the line are on the same side of the line. That is:

P and A are on the same side of BC
P and B are on the same side of CA
P and C are on the same side of AB

Make sure that you're using strict inequalities, as per the problem description.

You can actually use this problem's code for Problems 477 and 476.


#481 - What Goes Up

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a standard LIS problem, but the input is large so you'll need to use the O(n log n) version of the algorithm.


#482 - Permutation Arrays

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
Solution Description: Make a pair object that holds a p-value and a number. Parse the input into these pairs, sort based on the p-values, and output the sorted numbers.

However, the numbers must match the input *exactly*. So if you're given 5, you cannot output 5.0. Therefore, it's easiest to just treat all the numbers as strings, and not floating points.


#483 - Word Scramble

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Take the input line by line.

Retokenize it, reversing each word with a for loop and outputting in the same order.

Print out the modified line.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Iterate through each line. When you encounter a non-whitespace character, set an index variable to the index of that character. When you encounter a whitespace character (or end of line) and the index has been set, then reverse the characters between the set index and the current index - 1.

In Java you can make quick work of this problem using StringBuffer.

I handled space, newline, tab (\t), and carriage return (\r) as whitespace. I'm not sure if tabs or carriage returns actually show up in the input.


#484 - The Department of Redundancy Department

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: Hold an arraylist of two dimensional objects. For each input term, check if the arraylist already has it, and if so increment - otherwise just add it.

Output the arraylist in order.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:searching
Solution Description: Create a dynamic array of objects that hold a value and a quantity. For each number in the input, do a standard linear search for the object that has the same value, and increment its quantity. If you can't find one, then add a new object to the array.

Signed ints will work fine.


#485 - Pascal's Triangle of Death

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
dynamic programming
math
Solution Description: Pascal's Triangle has the property that every entry on the sides is a 1, and every other entry is equal to the sum of the two entries above it.

So just run this recurrence, keeping track of one row at a time. Obviously, you'll have to use BigInteger.


#486 - English-Number Translator

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:
Solution Description: This problem is fairly straight forward, but is annoying as hell to code since you've got to hard code every word and associate it with a numerical value.

Have three variables that represent each set of 3 digits in the final result. It's a simple algorithm to assign the values you take in to where they belong.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Simple simulation, but you can make it a little bit easier as follows:

Create four variables, mils, thous, huns, cur.

Whenever you get a word besides "million", "thousand", or "hundred", add its value to cur. When you get "hundred", transfer cur to huns and set cur to 0. When you get "thousand" or "million" transfer cur + (100*huns) to the thous or mils, and set cur and huns to 0.

Your final output is (1000000*mils) + (1000*thous) + (100*huns) + cur.

Two things to remember: If it's negative, negate it at the end, and if you read "zero", just output 0.


#487 - Strategic Defense Initiative

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is a Longest Increasing Subsequence problem. Use a second array, p[], to construct the solution. Let p[i] be the index of the missile you shot down just before missile i. When you get to the end, you can use this array to build a path back through the missiles you shot.


#488 - Triangle Wave

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:simulation
strings
Solution Description: Use a bunch of nested for loops to generate this solution.

You'll need a StringBuffer for output as well.

One newline between each waveform, and none at the end.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: If you want this problem to run in time in Java, you'll need to hardcode all 9 possible wave patterns. I made an array where a[amp] is the pattern for that amplitude, and then I printed it frequency times.

For example:

a[1] = "1"
a[2] = "1\n22\n1"
a[3] = "1\n22\n333\n22\n1"
etc.


#489 - Hangman Judge

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:simulation
Solution Description: This problem is fairly simple, though they don't carefully define what happens if a correct guess is made more than once. As you might expect, it's just ignored.

I use two boolean arrays indexed by characters. b['x'] is true if 'x' is still remaining in the word. g['x'] is true if 'x' has been guessed.

Initially, set all letters in b[] that are in the word to true, and g[] is all false. Then, just run through one letter at a time. After each letter, check whether or not the game has been won/lost.


#490 - Rotating Sentences

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: Hold an array of strings, and fill it with your input.

Fill up the strings with spaces so that all have the same length (the length of the longest inputted string)

Append to a stringbuffer as you iterate through the strings and their characters - in that order. Add newlines as appropriate.

Output the stringbuffer.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Keep the input in an array of strings, and keep track of the longest length across all strings. Then, iterate i from 0 to (max. length). For each i, iterate through all strings j from latest to earliest. Print out the ith character of j, unless i is greater than the length of j. In this case, print out a space.


#492 - Pig-Latin

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:sorting
strings
Solution Description: Read characters one at a time. If the character is a letter, add it to an ongoing string that holds a word. If the character is a non-letter, print out the Pig-Latin version of the current word (if there *is* a current word), and then print out the non-letter.

Don't forget to output any word you might have in the buffer when you hit EOF.


#494 - Kindergarten Counting Game

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: Watch the definition of 'word' closely. They aren't only separated by spaces.

Go through each line, and:
on = false
for each char (i) in line
---if(on)
-----if(i != letter)
---------on = false
-----else
---------count++
---------on = true

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Keep a boolean, initially set to false, and a running count. Whenever you encounter a letter and the boolean is false, make it true. Whenever you encounter a non-letter and the boolean is true, make it false and add one to the count.

If the boolean is true when you run out of characters, add one to the count. Then, just output the count.


#495 - Fibonacci Freeze

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Precalc the fibs, using BigIntegers, and output as needed.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Use BigIntegers to pregenerate an array of 5000 Fibonacci numbers, and just return the one requested.


#496 - Simply Subsets

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: Take each pair of lines into two arraylists, a and b.

make two new arrays, a2 and b2, and extract:
any element in a that is not in b goes into a2
any element in b that is not in a goes into b2

then:

if a.size=a2.size and b.size=b2.size, then they are disjoint
else
---if a2.size > 0
------if b2.size > 0
---------then i am confused
------else
---------then b is a subset of a
---else
------if b2.size > 0
---------a is a subset of b
------else
---------a is equal to b

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: If the sets are of equal size, check if there are any differences, and any matches. If there are differences with no matches, they're disjoint. If there are matches with no differences, they are equal. Otherwise, be confused.

If |A| < |B|, check if there are any A's that don't belong in B, and if there is any A that does belong in B. If there's one that doesn't belong, and none that do, then A and B are disjoint. If there's one that does belong, and none that don't, then A is a proper subset of B. Otherwise, be confused. Swap A and B if |A| > |B|.


#498 - Polly the Polynomial

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:math
Solution Description: There's not a lot to this. Just evaluate the polynomial at the given points. Although it isn't explicitly stated, the evaluation points will also be integers.

Also, no bound are given, but all values seem to fit within signed 32-bit integers.


#499 - What's The Frequency, Kenneth?

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:brute force
Solution Description: treat each line as its own test case.

hold two arrays, an upper and a lower. go through the line and increment upper[line.charAt(i)-'A'] or lower[line.charAt(i)-'a'], whichever is appropriate. Keep track of the max value between the two.

iterate through upper first, printing all chars with the max value, and then again for the lower array, and then print the max variable itself. Done.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Make an array of 256 integers where a[i] is the number of times character i appears in the output. Then just iterate through a[A] to a[Z], and then a[a] to a[z] looking for the maximum quantity. Whenever you tie the current maximum, add the current character to an ongoing string. Whenever you exceed the maximum, starta new string with current character.





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