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 lsSolved 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
(60max) / (max+2) + 1
and the number of rows is
ceil(n / columns) 
#401  PalindromesSolved 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 CutsSolved 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 GeneratorSolved 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 nonalphabetic 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 lowercase, 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  PiSolved 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(n1)/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*(n1)/2))). If the count is 0, then return failure. 
#413  Up and Down SequencesSolved 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 SurfacesSolved 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 IndexSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  brute force
 Solution Description:  Pregenerate 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  WordSearch WonderSolved 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 MaelstromSolved 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 FloydWarshall. Then, iterate through a[0][i] for all i, and return the maximum. 
#424  Integer InquirySolved 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 TransformationSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  floyd warshall strings
 Solution Description:  This is FloydWarshall 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 FloydWarshall 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 FloydWarshall. Set up your adjacency matrix, and then run FloydWarshall 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 BabylonSolved 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 FloydWarshall 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 FloydWarshall, 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 CircleSolved 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 MovesSolved 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 08, and the row to a number from 08. 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  LottoSolved 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 MultiplicationSolved 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 NumbersSolved 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 (i1)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 DecoderSolved 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 MazesSolved 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" BitsSolved 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 StringsSolved 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 AutomataSolved 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 DecoderSolved 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 (newline7).
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 ConnectivitySolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  Use a unionfind 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  OverflowSolved 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 FloridaSolved 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 waterfilled 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 ProbabilitySolved 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.562e2
...rather than:
2^6 = 1.563e2
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: RectanglesSolved 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 coords). For each point i with coordinates x and y, and each rectangle r with coordinates (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 CirclesSolved 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 coordinates x and y, and each circle c with center coordinates cx and cy and radius r, i lies inside c if and only if:
sqrt((xcx)^2 + (ycy)^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, TrianglesSolved 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 [cx1ax1] [cy1ay1] 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 coordinate vector P = (x,y), and each triangle t with coordinate 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)
((BA) X (PA)) * ((BA) X (CA)) > 0
((CB) X (PB)) * ((CB) X (AB)) > 0
((AC) X (PC)) * ((AC) X (BC)) > 0
You can interpret * as dot product or multiplication (as the cross product of twodimensional 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 UpSolved 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 ArraysSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  sorting
 Solution Description:  Make a pair object that holds a pvalue and a number. Parse the input into these pairs, sort based on the pvalues, 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 ScrambleSolved 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 nonwhitespace 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 DepartmentSolved 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 DeathSolved 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  EnglishNumber TranslatorSolved 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 InitiativeSolved 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 WaveSolved 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 JudgeSolved 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 SentencesSolved 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  PigLatinSolved 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 nonletter, print out the PigLatin version of the current word (if there *is* a current word), and then print out the nonletter.
Don't forget to output any word you might have in the buffer when you hit EOF. 
#494  Kindergarten Counting GameSolved 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 nonletter 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 FreezeSolved 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 SubsetsSolved 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 PolynomialSolved 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 32bit 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
