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.

#200 - Rare Order

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
strings
Solution Description: Look at each adjacent pair of lines to get some clue as to the ordering. The only information you can infer is from the two characters where the strings first differ. For example:

XWY
ZX
ZXY
ZXW
YWWX

XWY -> ZX (We know that X comes before Z)
ZX -> ZXY (Can't infer anything because the strings don't differ before one runs out)
ZXY -> ZXW (We know that Y comes before W)
ZXW -> YWWX (We know that Z comes before Y)

Create a DAG where there is an edge between u and v if we know that u comes before v. Run topological sort on this graph to get the answer.


#201 - Squares

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Hold a grid array with 4 dimensions.

For each size of square:

Loop through all possible top-left-corners that would be in a valid square, and see if a square of the current size exists from that top corner.

Doing so is fairly simple, loop from 0 to the current size-1 in a variable i, and hold a "we're still good" boolean before you run the loop that's set to true by default. Then use the variable i and your coordinates for the topleft of the current square to check all the sides, ie:

grid[x+top][y][x+top+1][y]
grid[x+top][y+size][x+top+1][y+size]
grid[x][y+top][x][y+top+1]
grid[x+size][y+top][x+size][y+top+1]

If any of them, for each value of top, has not been set (does not exist on the game board), set your "we're still good" variable to false and therein don't count the would-be square of the current size from that topleft corner spot.

[EDIT] NOTE: the input isn't very nice, since they'll through you some out of boundary inputs... just literally add 1 to each dimension of your grid array, and it will be fixed. Scanner class runs in time.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Create an n x n array where a[i][j] = 0 if the dot at row i, column j has no line to the right or below, 1 if it has one to the right only, 2 if it has one below only, and 3 if it has both. This way, when you take in the input, add 1 to a[i][j] for a horizontal line, and add 2 for a vertical line.

For each possible size of square, and each possible starting upper-left co-ordinate, check if the square exists. Check a[i][j] % 2 == 1 for horizontal lines, and a[i][j] >= 2 for vertical lines.

You'll need to use BufferedReader and StringTokenizer in Java as the input is quite large.


#202 - Repeating Decimals

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
simulation
Solution Description: It's the bane of elementary math students. Long division! But you love it, right?

Do the division step by step, keeping track of the dividend each time. When you hit a dividend you've already seen, stop, and your cycle goes from the first time that dividend showed up to where you stopped. For example, 1/7:

7 into 1 : 0
7 into 10 : 1
7 into 30 : 4
7 into 20 : 2
7 into 60 : 8
7 into 40 : 5
7 into 50 : 7
7 into 10 : STOP

We've seen 10 before, so the cycle is 142857, giving us the answer 0.(142857)

Watch out for cases that divide evenly. So for example, 6 / 2 is 3.(0), with a cycle length of 1.


#216 - Getting In Line

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:2D geometry
brute force
Solution Description: Essentially, you're trying to find a Hamiltonian path, so brute force is the way to go. I used Dijkstra's permutation algorithm to run through the permutations.

It's just Pythagoras to get the distance between any two points, but don't forget to add 16 as per the problem description. After that, just make sure you have the output formatted exactly.


#227 - Puzzle

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Create a grid array, and simply move the pieces according to the input given.

The nice thing about doing this in java, is that you can encapsulate the last part of your program(the loop that goes through your 'commands' string and normal output) in a try catch block, and if an exception is thrown, then you know an illegal move was made since you would have tried to access outside the normal bounds of your grid. In the catch, just output that there isn't a final config!

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Keep a 5x5 array of characters, and when you take in the input, keep track of where the empty space is. Just follow the instructions. For every character, move swap the empty space with the appropriate character, and modify the empty space's co-ordinates accordingly. If any move would cause the empty space to leave the board, then the puzzle has no final configuration.

Don't forget that the commands may be split over many lines. Also, make sure that you finish reading the commands, even if the puzzle becomes invalid. If you just stop immediately, then you risk reading the remaining commands as puzzle input.

As far as I can tell, there will be no whitespace in the middle of the commands (except newlines of course) and there will be no characters following the terminal 0. There will also be no invalid characters in the commands.


#231 - Testing the CATCHER

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: keep two arrays, one for heights and one for 'values'. The values array at [i] will hold the maximum number of missles that could be intercepted should the set of missles end with i.

Loop through your height array using a variable x, and for each element, loop from 0 to x-1 to find the 'best' previously shot missle (ie the one with the highest value that is still at least as high as the current). Value[x] will be the value of the 'best' that you found + 1 or 1 if you found nothing.

Output the hightest value in the value array.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:dynamic programming
Solution Description: This is just a Longest Increasing (Decreasing) Subsequence DP. Nothing particularly tricky, so just make sure you don't have an extra blank line at the end. An array of 1,000,000 integers is large enough to hold the input.


#232 - Crossword Answers

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:strings
Solution Description: There's a bit of coding. Keep a grid array so you have the info stored. Keep a numbers array, so that you know what numbers go where.

Iterate through the crossword once, entering in the numbers as suitable (with an incrementing counter).

Then, go to output. When you're doing across, iterate through once more in the same fashion, but this time, whenever you reach a number that has a block to the left of it, output the number and the string that extends to the right of it.

Iterate once more, in the same fashion, however this time when you find a number, check to see if there's a block above it - and then temporarily iterate downards before returning to grab the string you need and output.

Doing that last array traversal in that way will automatically sort the output for you.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:searching
strings
Solution Description: Keep two arrays, c[][] and n[][]. c[i][j] is the character in the ith row, jth column. n[i][j] is the crossword number in the same cell, or 0 if it's an unnumbered white cell, or a black cell.

Take your input into c[][], and then iterate through n[][] setting up all of the crossword numbers. Any white cell that is on the upper or left border is numbered, and any cell that has a black cell directly above or to the left of it is also numbered. Make sure you iterate through row by row and not column by column.

Now, iterate through n[][] two more times. Once for Across words, and once for Down words. Any numbered cell on the left border or with a black cell directly to the left is the beginning of an Across word. Any numbered cell on the top border or with a black cell directly above it is the beginning of a Down word.

When you find such a cell, search c[][] across or down as applicable, appending every character you come across to a temporary string, and stopping when you encounter the right/bottom border or a black square. Output the number of the starting cell along with your temporary string.

Make sure that you print out the Across and Down headers even when the entire puzzle consists of only black squares.


#253 - Cube painting

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:brute force
strings
Solution Description: This problem isn't conceptually difficult, but it takes some carfeul spatial perception to avoid making errors in the implementation.

Call the first cube A and the second cube B. a[i] = the ith character in A's string, and b[i] = the same for B. I'm assuming a 0-indexed array, so be wary that the face numbers I use here are 1 less than how they're given in the problem.

We're going to test all rotations of B to see if any of them match A. Iterate through all six sides testing each one as the top face. So check that b[i] = a[0] && b[5-i] = a[5].

If the top and bottom match, then we must check all four rotations of the sides. Make a temporary array where s[j] = the jth side (in clockwise order from the top), given that i and (5-i) are the top and bottom. So for instance, if the top and bottom are 1 and 4 respectively, then s[] is initialized to {b[5], b[2], b[0], b[3]}.

Now test this condition for all four rotations of the sides:

s[0] == a[1] && s[1] == a[2] && s[2] == a[4] && s[3] == a[3]

If it's true, then the cubes match. To get the next rotation of the sides, just cycle s[] around, so s[0] = s[1], s[1] = s[2], etc.


#254 - Towers of Hanoi

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: If you look at the first few moves of the puzzle, you'll see an important pattern. Each move (i - j) below means on turn i, move disc j. Discs are 0-indexed, where 0 is the smallest disc.

1 - 0
2 - 1
3 - 0
4 - 2
5 - 0
6 - 1
7 - 0
8 - 3
9 - 0
10 - 1
11 - 0
12 - 2
13 - 0
14 - 1
15 - 0

Disc 0 is moved every 2 turns, starting on turn 1. Disc 1 is moved every 4 turns, starting on turn 2 ... Disc i is moved every 2^(i+1) turns, starting on turn 2^i.

So, in constant time we can determine how many times a given disc has moved, given m:

moves = (m + 2^i) / (2^(i+1)) [integer division]

The next thing to note is that each disc moves in a cyclic pattern. Namely, the odd-numbered discs move to the left each time they move (2, 3, 1, 2, 3, 1...) and the even-numbered discs move to the right (1, 3, 2, 1, 3, 2...)

So once you know how many times a disc has moved, you can easily determine which peg it ends on by taking mod 3 (and doing a little bit of figuring).

Obviously BigInteger is handy for this problem.


#256 - Quirksome Squares

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Brute force the answer, pipe the output to a text file, and then hard code it back into the program. The program runs in something like 5 seconds when you bf it initially.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: Just brute force all of the possible numbers, using strings so as to keep the leading zeroes. For instance, for 4-digit numbers, try all strings between 0000 and 9999. Split them in the middle and see if the sum of the two halves squared equals the original number.

It may take about 30 seconds for this to run, so just copy the results and hardcode them in to create your final solution. There aren't many numbers to print.


#260 - Il Gioco dell'X

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: Run a breadth-first search to find all reachable squares for both colours.

First, put into the queue all black squares in the top row, and all white squares in the left column. Mark all these cells as visited. Then, whenever you take something from the queue, look for any connected cells of the same colour that haven't been visited. Mark these as visited and put them in the queue.

At the end, look for any black cells in the bottom row that have been visited. If you find one, black wins. If you can't find any, then white wins.


#263 - Number Chains

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:sorting
strings
Solution Description: Pretty much follow the instructions. Keep a last variable that holds the last value you calculated, and if you've just calculated what you did before, then stop doing calculations and move on.

You'll need a function to sort the characters in a string asc and desc. You can do that by converting the int to a String, then to a character array, running Arrays.sort, and then turning back into an int.

Reverse the array for desc.

Does not run in time for Java.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
sorting
strings
Solution Description: For each number n in the chain, transfer it to an integer array where a[i] is the ith digit of n. Sort the array ascending and convert the individual digits back into a complete number. Then iterate through the array backwards and convert the digits into another number. Subtract the former from the latter to generate your next n.

Keep an array p[] that holds all values previously reached. Whenever you generate a new n, search for it in p[]. If you don't find it, add it in. If you do find it, then stop processing and print out the length of the chain (which should be the number of elements in p[] +/- 1 depending on how you implemented it).

This problem does not seem to run in time in Java regardless of how many optimizations I throw at it, so watch out.


#264 - Count on Cantor

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
Solution Description: Pregenerate all of the terms, using an array of characters to hold each numerator and denominator.

To generate each term, you'll need a running counter, and a for loop that iterates 10000000 times.

For each iteration of the master loop with i,
depending on if you're counting up or down, you count 'counter' times... eg:

counter = 1 (COUNT DOWN)
1/1
counter = 2 (COUNT UP)
1/2
2/1
counter = 3 (COUNT DOWN)
3/1
2/2
1/3

As you can see, the numerator counts in the opposite direction of the denominator. All it takes is one boolean that toggles to count up and then down every other iteration.

Compensate for your inner counting loop by incrementing the master loop as appropriate, and break the inner loop at 10000000 ('cause it WILL overflow).

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: Pregenerate two arrays where n[i] is the numerator of the ith term, and d[i] is the denominator of the ith term. The pattern is fairly simple:

Numerator: 1 12321 123454321 ...
Denominator: 121 1234321 12345654321

In Java, use arrays of shorts as you'll use too much memory if you declare 20 million integers.


#270 - Lining Up

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:2D geometry
sorting
Solution Description: It looks like an O(n^2 log n) algorithm will be accepted for this, but you can do it in O(n^2).

Let s[i][j] be the slope between points i and j. You can compute this array in O(n^2) of course. Now, search through each row of the array. That is, s[i][j] for all j. Look for the slope that appears the most number of times. This is the line that covers the most points that contains point i. Maximize this value across all points i, and output it.

There are a few things to note:

- I don't know if double precision is enough for holding the slopes, as no bounds are given on the co-ordinates of the points. Consequently, I store the rise and run separately as integers.

- Another problem with having no bounds for the co-ordinates is that you need a hash table to keep track of which slope is the most common.

- There is no guarantee that all points will be unique, so watch out for that. If two points, A and B, have the same co-ordinates, then of course any line through A will also pass through B, and vice versa. Don't forget to factor that in.


#271 - Simply Syntax

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:strings
Solution Description: This is a very simple prefix notation evaluation problem. A stack of characters is the natural data structure to use here.

Iterate through the string from right to left. When you encounter an operand (lower case character), push it onto the stack. When you encounter an N, pop the top of the stack off and push the N. If you encounter any other uppercase letter, pop the top two elements off the stack and push the uppercase letter on.

If at any time you don't have enough elements to pop, then the string is invalid. Also, if there is not exactly one element remaining on the stack (the "result"), then the string is invalid. Otherwise, it's fine.

Now, while using a stack is the usual way to evaluate prefix (or postfix) expressions, you aren't actually being asked to evaluate the expression, so you don't even need the stack. You can just use a variable, s, that keeps track of how many elements would be on the stack if you had one.

So if you encounter a lowercase letter, increment s; if you encounter an N, do nothing, but mark the string invalid if s = 0; if you encounter any other uppercase letter, decrement s, but mark the string invalid if s < 2 (before decrementing).


#272 - TEX Quotes

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Iterate through each line of input, and toggle a boolean value that will tell you if you're turning the next " you see into a `` or a ''.

Output as you finish each line.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:strings
Solution Description: Keep a boolean that is true when an opening mark is needed, and false when a closing mark is needed. Iterate through each string and whenever you encounter a quotation mark, replace it with the appropriate double-mark (`` or ''), and then toggle the boolean. Print out each line after you're done with it. Don't output character by character as it may not run in time.

This can be accomplished quite easily with StringBuffer.replace() in Java.


#275 - Expanding Fractions

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: This problem is just long division. While you do the division, keep track of the different dividends that you see, so that you can detect a cycle. For example, 112 / 900:

112 / 990 --> .1
130 / 990 --> 1
310 / 990 --> 3
130 / 990 --> STOP (We've already seen 130)

Naively, this approach will be O(n^2) where n is the length of the expansion before it repeats or terminates. However, if you use a hash table to map dividends to indices, you can do it in O(n).


#278 - Chess

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Takes a lot of thought - if you're not that great with Chess.

Rooks and Queens are easy enough, they're both just Math.min(m, n).

Knights:
((m+1)/2) * ((n+1)/2) + (m/2)*(n/2))

Kings:
((m+1)/2) * ((n+1)/2))

The kings are just the first part of the knights equation, since the knights equation consists of two parts representing the filled chess board. The first part tallies every other row. The second part tallies the sparser, in between rows - which are the only difference between the knights and kings boards. The knights have them, the kings don't.

I'd say the theory difficulty on this is easy-medium, but I'm pretty exhausted right now, and can't precisely gauge whether I'm just really impaired or if that's really the appropriate difficulty. So, I'm erring on the side of caution.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: For rooks, just put them in a diagonal line:

x....
.x...
..x..
...x.

So for rooks, the answer is min(m,n).

Queens get arranged in a sort of staggered shape:

x....
..x..
....x
.x...

The answer is the same: min(m,n).

Knights can be arranged in a alternating grid pattern:

x.x.x
.x.x.
x.x.x
.x.x.

Using integer division, this works out to ((m+1)/2) * ((n+1)/2) + (m/2) * (n/2).

Kings are arranged as knights, but only on alternating lines:

x.x.x
.....
x.x.x
.....

And the answer is ((m+1)/2) * ((n+1)/2).


#280 - Vertex

Solved By:peter
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: The input is a little funny, but aside from that the problem is straightforward.

Keep an adjacency matrix, and for starting node, perform BFS and mark each node you visit off on a boolean array. At the end, iterate through the array and output when something hasn't been visited.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: For each starting node, run a breadth-first search to see which nodes can be reached. Although you would generally mark the starting node as visited, make sure you don't in this case. The starting node is only visited if there's some loop that brings you back to the starting node.

At the end of the BFS, check your visited array, and count the number of the nodes that haven't been visited. Output this number along with the names of all the unvisited nodes.

In Java you'll need to use BufferedReader and StringTokenizer as the input is quite large.


#291 - The House Of Santa Claus

Solved By:peter
Theory Difficulty:medium
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This problem is annoying to do if you're not comfortable with depth first search - and you're going to use my solution. The DFS algorithm has to be PERFECTLY constructed, with everything in SPECIFIC PLACES, otherwise it won't work properly.

You need two stacks, call them A and B.
A will be your DFS stack, and B will be your path stack. You'll also need an adjacency matrix that you've hard coded with the required edges.

Add node 1 to A to begin the DFS.

while A still has nodes
----pop a node off the stack A into a variable called cur
----if cur = -1
--------pop a node off B
--------restore the adjacency betweeen what you just popped and what's left on top of B
--------skip the rest of this loop
----push a -1 onto A
----if there's a node on B
--------kill the adjacency between B.peek and cur
----push cur onto B
----Iterate through cur's current neighbors and add them to A
----if you didn't add any neighbors
--------pop the -1 off A
--------if the length of B is 9
------------output the contents of B
--------pop off the top of B
--------restore the adjacency between what you just popped and what's now on top of B


Okay, now to explain:

Essentially what we're doing is running a standard DFS, but keeping track of the current path that we've run. We've also made sure to allow some cycling (as in you can visit nodes multiple times), but you won't ever go back over your current path.

The -1 is a placeholder to tell you when you've exhausted all the paths that come from the current top of stack B, and that you should pop it off B so that its no longer included in any paths.

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
other graph
Solution Description: Brute forcing this solution is easier if you 0-index the vertices (so subtract one from each) and represent the house as an adjacency matrix. Create a matrix a[][] where a[i][j] = 1 if i and j are connected, and hardcode it with the 8 (bidirectional) edges of the graph.

Now, iterate through all possible paths from 000000000 to 444444444 (using an integer and bit shifting, or using an array of integers facilitates this). For each path, fill in a temporary adjacency matrix where tmp[i][j] = tmp[j][i] = 1 if i and j are consecutive digits in the path.

If the temporary adjacency matrix matches the hardcoded one in all cells, then the current path is a solution, so output it.

If you iterate through *all* solutions it may not run in time (in Java at least), but you only need to check solutions that start at vertex 0 as per the problem description, and by Euler's path law, all paths must end at vertex 1. Now you only have 5^7 paths to check!


#294 - Divisors

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: The bounds are too large to pregenerate, so you'll have to calculate on the fly.

Iterate through all numbers i between L and U inclusive. For each number, iterate through all numbers j between 1 and sqrt(i) inclusive. If i % j == 0, add 2 to a running count. For all numbers, half of the divisors are below the square root, and half are above, so we only need to search the lower half.

If i is a perfect square, then subtract 1 from the total number of divisors, as perfect squares have one divisor that is exactly *on* the square root, so it has no counterpart.

Output the number with the greatest number of divisors. Make sure that you print the smallest number in the case of ties.

I used BufferedReader and StringTokenizer to be safe, as the bounds are quite large (up to a billion numbers searched per case), but it only took a second to run, so it's probably safe to use Scanner.


#296 - Safebreaker

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:medium
Algorithms Used:brute force
Solution Description: Keep all of the guesses in an array (I made some Guess objects for convenience). Then, iterate through all possible solutions from 0000 to 9999. For each solution, check whether it's consistent with all of the guesses. If only one solution is consistent with all guesses, then output it. Otherwise, output "indeterminate" or "impossible" as applicable.

Representing guesses and the current iteration as an array of four integers works well. To check for consistency, I also used two arrays of 4 booleans to mark whether or not a number had been used.

For example, say we have this guess:

1244 1/1

Let's test 4231 with it, and count the number of correct numbers, and then the number of misplaced correct numbers. F = false, T = true (for the boolean arrays that mark used numbers).

FFFF <- booleans for guess
1244 <- guess
4231 <- current iteration
FFFF <- booleans for current iteration

First we look for all numbers that match, and mark them used in both arrays:

FTFF
1244
4231
FTFF

We've found 1 correct number. Now, we iterate through the ones that haven't been used and see if they match:

FTTF
1244
4231
TTFF

The 4 in the guess matches the 4 in the current iteration, so we have 1 misplaced correct number. Note that each number in the current iteration can only match one number in the guess, and vice versa. So while the guess has two 4's in it, we say that there's only one misplaced correct number.

Since our guess was (1244 1/1), the current iteration is consistent with it, as we found 1 correct number and 1 misplaced correct number.


#297 - Quadtrees

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:recursion
sorting
Solution Description: Use two arrays of 1024 booleans where b[i] is true if the ith pixel is black.

The hardest part of this problem is parsing the trees... You can be pretty inefficient about it if you wish, but it isn't too hard to parse the trees in O(n), where n is the length of the input string. I use a bitstring to keep track of the current spot in the array that I will write to, assuming that the quadrants are all in a row. That is, 0-255 is quadrant 1, 256-511 is quadrant 2, etc.

Initially, the bitstring is 00 00 00 00 00. Each two bit section is a quadrant number. Initially, the first two bits are what we are concerned with. Whenever you hit a parent node, change your focus to the next two bits. Whenever you hit a full quadrant, fill in the boolean array with trues from the start of the current piece (inclusive), to the start of the next piece (exclusive). Here's an example to make things more clear:

Input: pefepeefe
Initially: 00 00 00 00 00

We hit a 'p' first, so focus moves to the first set of bits:

*00* 00 00 00 00

When we hit an 'e', we just increment the currently focused set:

*01* 00 00 00 00

When we hit an 'f' we fill in a section of the array. In this case, from 01 00 00 00 00 (inclusive) to 10 00 00 00 00 (exclusive). We also increment the currently focused set:

*10* 00 00 00 00

Another 'e':

*11* 00 00 00 00

A 'p', so we shift focus:

11 *00* 00 00 00

An 'e':

11 *01* 00 00 00

Another 'e':

11 *10* 00 00 00

An 'f':

Fill in between 11 10 00 00 00 and 11 11 00 00 00.

11 *11* 00 00 00

An 'e', and now there's no more input, so we're done parsing this tree. Of course, it's important to remember to pop back a level once you've processed four nodes.

This may appear to be a slightly convoluted way of going about things, but it's actually quite compact to code.


#299 - Train Swapping

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:greedy
simulation
Solution Description: Takes about 1-2 minutes to write. If you want to code fast, just:

while(!done)
{
done=true;
iterate from end of trains to beginning, and swap two if (left > right)
if(did a swap)
done=false;
}
output count of swaps

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: It's possible to just simulate the train swapping and count the number of swaps (it's exactly bubble sort), but you can apply a bit of cleverness:

Notice that once you get one train into its final position, the remaining trains are in the same order. For instance, look at this series of swaps resulting in train 1 being in the first position:

23154
21354
12354

The remaining trains are in the same order (2,3,5,4). Using this result:

- For the ith train, find i in the sequence of trains.
- Add i's index (assuming a 0-indexed list) to the total number of swaps.
- Remove i from the list

A quick example:

23154 (1 is at location 2, so add 2)
2354 (2 is at location 0, so add 0)
354 (3 is at location 0, so add 0)
54 (4 is at location 1, so add 1)
5 (5 is at location 0, so add 0)

And the answer is 3 swaps.





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