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. #10800  Not That Kind of GraphSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation sorting strings
 Solution Description:  Run the simulation as given. The only thing I can really say is to use a character array and string buffers.
Some tips:
You have to trim the excess spaces on the right side of the graph. So, if you have a straight increasing line like y=x, you have to trim off the spaces in your output on the right side of the line.
Make sure you compensate for:
RRRFFFFFFFFFFFFF
Watch out for when the very top of your graph gets a couple blank lines (that is, you got a RF at the top, and consequently you've got a y axis placeholder with no graphed line in it) 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Not conceptually difficult, but it's easy to make mistakes.
Keep an array of characters 50 wide and at least 101 high where a[i][j] is the character at time i, height j. Fill the array with spaces. Let the starting height of the graph be 50. For the ith character you read:
C  Print an underscore at a[i][h]
R  Print a slash at a[i][h], increment h
F  Decrement h, print a backslash at a[i][h]
Keep track of the minimum and maximum height that characters are printed at. Output only the rows between the minimum and the maximum.
Also, keep an array of integers l[] where l[i] is the latest time at which a character was printed on the ith row. Use this to ensure that you don't print trailing spaces at the end of any row. 
#10801  Lift HoppingSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dijkstra
 Solution Description:  This is a Dijkstra problem that isn't too hard, but takes a bit to set up.
Keep 100*n nodes, where n is the number of elevators. So, nodes 099 are the first elevator shaft on all floors, and 100199 are the second the second elevator shaft, etc.
Put an edge between each pair of adjacent floors that an elevator stops at. So in the first sample case, there's an edge betwee 0 and 1, 1 and 3, 3 and 5, 5 and 7, etc. for the first elevator. There'll be edges between 104 and 113, 113 and 115, 115 and 119, etc. for the second elevator. The weights on these edges should be the difference in floors multiplied by the time it takes to travel between two floors.
Then, put an edge between nodes on the same floor if both elevators stop at that floor. So, there should be an edge between 13 and 113, 15 and 115, and 20 and 120. All of these edges should have weight 60 (remember, it's 1 *minute* to change elevators, not 1 second).
Run Dijkstra on this graph, and return the minimum distance across all nodes on the desired floor. If all of them are infinity, then output "IMPOSSIBLE".
Note that you get to assume that all elevators start at their optimal location, not necessarily at floor 0. Take this case for example:
2 90
1 10
0 80
80 90
If both elevators started at floor 0, it would take you 80 seconds to get to floor 80, but then 800 seconds for the second elevator to get to floor 80 for you to use it. However, you get to assume that it only takes 60 seconds to change elevators, so that basically means that all elevators are where you want them to be. 
#10803  Thunder MountainSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry floyd warshall
 Solution Description:  Use pythagoras to create an adjacency matrix from the points, where two points are connected with an appropriate length if that length is <= 10.0, otherwise the length is infinity
Run warshall on this, and afterwards iterate through all the edges and get the maximum.
If it's infinity, output "send kurdy", otherwise just output it. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  2D geometry floyd warshall math
 Solution Description:  To set up your adjacency matrix for a[i][j], calculate the distance between point i and point j. If it's 10 or less, then a[i][j] = distance. Otherwise, a[i][j] = infinity.
Run FloydWarshall, and then iterate through the array looking for the largest a[i][j]. If it's less than infinity, output it. Otherwise, send Kurdy. 
#10812  Beat the Spread!Solved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  if(a+b != s  Math.abs(ab) != d  a < 0  b < 0)
print("impossible");
else
println(a + " " + b);
given:
b = (sd)/2;
a = s  b; 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  There are two impossible situations. One is if d > s, and one is if one of s and d is odd, and the other is even.
If s and d are both even then the scores are (s/2) + (d/2) and (s/2)  (d/2). If both are odd, then the scores are the same, but add 1 to the upper score to account for the integer division. 
#10813  Traditional BINGOSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Annoying to program. You pretty much just have to simulate the game  but on the bright side, you can be absolutely wasteful with your for loops and this will STILL run in time.
Also, the problem description is poorly done, and has shameful ambiguities.
INPUT:
Starts with an integer n = # of test cases.
FOR EACH TEST CASE there will be five lines that describe a bingo game card AND 75 numbers to describe the order in which the bingo numbers are drawn.
OUTPUT:
Any bingo card can only BINGO once, and the results from each game should be outputted on their own line in the order they're given in the input.
I'd rate the coding as easymedium. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  simulation
 Solution Description:  Keep an array of integers that represents the BINGO card. Mark the free space as 0. Whenever a number is called, search the card for it. If it exists, change it to a 0. To check for a win, See if any column, row, or diagonal has a sum of 0. 
#10815  Andy's First DictionarySolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  Use an arraylist and a string tokenizer to parse the input.
After, use Collections.sort, and output the arraylist. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  sorting strings
 Solution Description:  This is a list of all nonalphabetic characters that may appear:
" !\"#$%&'()*+,./0123456789:;<=>?@[\\]^_`{}~\t\r\n"
Just parse each word and check an array of strings to see if you already have it. If you do, ignore it, otherwise add it. Make sure to store the lowercase representations. At the end, just sort and output the array.
I used BufferedReader and StringBuffer in Java, but it may not be necessary. 
#10820  Send a TableSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  The basic idea here is to find all pairs of numbers (x,y), x < N, y < N such that x and y are coprime.
The first few values look like this:
For N = 1, we need (1,1)
For N = 2, we need (1,2) and (2,1) also
For N = 3, we need (1,3), (2,3), (3,1) and (3,2) also.
Notice that each time we increase N, we need a pair for every number that is coprime with, and less than, the new N, and a pair that includes 1. Also, we need the symmetric version of each pair, so (2,3) as well as (3,2).
The number of values less than or equal to N and also coprime with N is phi(N), so for each new N, 2*phi(N) new values are needed. The constant 2 is because we need both (x,y) and (y,x). This leads us to the recurrence:
a[i] = a[i1] + 2*phi(i)
Let a[i] be the number of values needed for N = i.
Precalculate this for i <= 50000, and then just output every requested value. 
#10838  The Pawn ChessSolved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dynamic programming recursion
 Solution Description:  This is a fairly standard minimax game playing problem. There are fewer than 3^16 states, so you can store the result of the game for each possible configuration.
Keep a 3^16 array for each colour. So, w[s] is the number of moves before white wins (or loses) given state s. b[s] is analogous for black.
Your state should be a base3 encoded number where each ternary digit corresponds to one cell on the board.
w[s] > 0 means that white will win on state s in w[s] moves.
w[s] < 0 means that white will lose on state s in w[s] moves.
w[s] = 0 means that white has no valid move in state s.
Write a recursive function that takes a state, finds all possible moves, and chooses the best one. Memoize your results in w[] and b[]. The two base cases for your recursion are:
1) The current player has a winning move (return 1)
2) The current player has no moves (return 0) 
#10852  Less PrimeSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Generate all the primes up to 10001.
For each input, just iterate through them, and find if there exists a small p that satisfies the given equation. If there is, see if the function with that p and that prime is greater than your current maximum (and record down both the max and the prime if it is).
Output your prime. This should run in time with no problems  my code was fairly bulky and it ran in 0.220. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  If you think about the problem a bit, it's really asking: "What is the smallest prime number x such that 2*x > n?"
So, generate the primes up to 10000 with the Sieve of Eratosthenes, and for each input, scan your primes array for the answer. 
#10878  Decode the tapeSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting strings
 Solution Description:  Each row on the tape is a binary sequence, that represents the ascii value of a given character.
Ignore the lines  and _ which define the outer perimeter of the tape, and ignore the periods as well.
Take the input in, and remove all the unnecessary characters, then change the spaces to zeros and o's to 1's.
Output the characters corresponding to the given ascii values, but do not print out a new line after the input!!! 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  sorting
 Solution Description:  Being such a cute and unique problem, I think it's best to figure it out for yourself. It's not at all hard, at least not for any reasonable computer scientist.
One thing to note: Do not put an extra newline at the end of the message. It will contain its own newlines. 
#10879  Code RefactoringSolved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  For every input, n, just search through all numbers, i, from 2 onwards. If (n % i) == 0, then output i and n/i as two possible factors. 
#10891  Game of SumSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming
 Solution Description:  This is a fairly standard minimax gameplaying DP problem.
Let the sequence of numbers be a0, a1, ..., an1.
Let dp[i][j] be the maximum score Player A can get when the remaining numbers are ai, ai+1, ..., aj
dp[i][j] = the maximum over all possible moves of (value of move)  dp[i'][j']
i' and j' are the new left and right sides after taking your move.
This is the minimax step. dp[i'][j'] is the maximum score your opponent could possibly get, so (value of move)  dp[i'][j'] is the score you'll get.
At the end, output dp[0][n1]. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
