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 Graph

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: simulationsortingstrings 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 Hopping

 Solved 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 0-99 are the first elevator shaft on all floors, and 100-199 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 Mountain

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: 2D geometryfloyd 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 geometryfloyd warshallmath 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 Floyd-Warshall, 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(a-b) != d || a < 0 || b < 0) ---print("impossible"); else ---println(a + " " + b); given: b = (s-d)/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 BINGO

 Solved 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 easy-medium.

 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 Dictionary

 Solved 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: sortingstrings Solution Description: This is a list of all non-alphabetic 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 Table

 Solved 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[i-1] + 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 Chess

 Solved By: wesley Theory Difficulty: medium Coding Difficulty: medium Algorithms Used: dynamic programmingrecursion 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 base-3 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 Prime

 Solved By: peter Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: brute forcemath 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 tape

 Solved By: peter Theory Difficulty: trivial Coding Difficulty: trivial Algorithms Used: sortingstrings 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 Refactoring

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

 Solved By: wesley Theory Difficulty: easy Coding Difficulty: easy Algorithms Used: dynamic programming Solution Description: This is a fairly standard minimax game-playing DP problem. Let the sequence of numbers be a0, a1, ..., an-1. 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][n-1].