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: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 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 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 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:sorting
strings
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 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 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 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 tape

Solved 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 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].





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