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.

#701 - The Archeologists' Dilemma

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:brute force
math
Solution Description: If the prefix of the given number is X, then we're looking for a power of 2 that lies between X*(10^N) and (X+1)*(10^N), where N is greater than the number of digits in X.

You can brute force values of N until you find one such that log2(X*(10^N)) and log2((X+1)*(10^N)) are on opposite sides of an integer. So for instance, if the former is 4.8, and the latter is 5.2, then the answer must be 5.

Of course, N may be very large, so you'll need to work in logarithmic space to calculate 10^N. So:

log2(X*(10^N)) = log2(X) + log2(10)*N


#706 - LCD Display

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:medium
Algorithms Used:strings
Solution Description: Wow, this is annoying to write - simply because you have to hand code the for loops for each number... 'sigh'.

I made 10 functions, labelled one, two, three, four, etc. Each took a string array(a[]) which was my output array, and appended the appropriate characters to it, line by line.

Then I outputted the output array, line by line, being sure to substring off the last character (my extra space that had been for separating numbers).

In total, my solution is 300 lines. Luckily, though, once you have functions one and two, the rest are just slight modifications of one of them (mostly two). So.. copy and paste.

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
Solution Description: Not much of an intellectual challenge here, so just make sure that you format everything properly. Break each number into five sections, the top row, the upper section, the middle row, the lower section, and the bottom row. Each of these pieces needs to be coded with a separate for loop.

A note for Java users: You'll need to use a StringBuffer to hold each row as you build it. Printing out character by character is too slow.


#713 - Adding Reversed Numbers

Solved By:peter
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just do exactly as the problem states using BigIntegers and StringBuffers ONLY (except maybe for N), and the problem will run in time.

Use StringBuffer.reverse().

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:trivial
Algorithms Used:math
Solution Description: Just use StringBuffers to reverse the two strings, then BigIntegers to add, then a StringBuffer to reverse the sum, and then a BigInteger for output.


#729 - The Hamming Distance Problem

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
strings
Solution Description: Create an array with n-h zeros followed by h ones, and print out all possible permutations using Dijkstra's permutation algorithm.

In Java, use StringBuffer for your output, or it probably won't run in time.


#739 - Soundex Indexing

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
simulation
strings
Solution Description: Just simulate the rules given, and be sure to get the spacing correct.


#740 - Baudot Data Communication Code

Solved By:wesley
Theory Difficulty:trivial
Coding Difficulty:easy
Algorithms Used:simulation
strings
Solution Description: Store the code characters in an array so that you can just use every series of 5 bits as an array index. In Java, use Integer.parseInt() to do conversion from base 2 automatically.

Keep a boolean to represent which shift you're currently in (up/down) and just output the characters as necessary.


#748 - Exponentiation

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
math
strings
Solution Description: Remove the decimal point from each input, and record how many decimal places there were. Let R' be R with the decimal point removed. Let d be the number of decimal places in R. We know that R^n will have n*d decimal places.

Use BigInteger or string multiplication to compute R'^n. Then, put the decimal point back in n*d places from the right hand side. If R'^n has fewer than n*d characters, then add zeros to the left-hand side to make up for the difference.


#750 - 8 Queens Chess Problem

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:ad hoc
recursion
Solution Description: 8-Queens is a classic problem that can be solved very easily with backtracking. Keep an array that marks spaces that are being attacked by queens. For each column, try all valid locations for a queen, and recurse onto the next column.

In this way, you do less than 7! operations per test case which is quite fine.

Beware the output formatting. The solution number is actually right-aligned in a column two characters wide. This doesn't seem to be stated anywhere in the problem description.


#753 - A Plug for UNIX

Solved By:wesley
Theory Difficulty:medium
Coding Difficulty:medium
Algorithms Used:max flow
strings
Solution Description: This is a matching problem with a few additional edges. Set up a graph that has a vertex for each device, and a vertex for each kind of plug, whether there is a receptacle for it or not in the hotel room. Also, include a source and a sink.

- Draw an edge of capcity 1 from the source to each device.
- Draw an edge of capcity 1 from each device to the receptacle it requires.
- Draw an edge of capacity C from each receptacle to the sink, where C is the number of times that receptacle shows up in the hotel room.
- Draw an edge of infinite capacity between each receptacle pair (X, Y) where an adapter from X -> Y exists.

Run max flow on this graph to see how many devices you can plug in. Return (m - flow) as your answer.


#763 - Fibinary Numbers

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:math
Solution Description: This is a pretty simple base conversion problem. Precompute the first 105 Fibonacci numbers using BigInteger, and use them to do your conversions.

Make sure that when you convert the answer back into base Fibonacci you take the largest possible terms first. Also, don't forget the case of 0 + 0 = 0.


#782 - Contour Painting

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is a floodfill problem that requires a little extra work. Really, the problem lies in the underspecified problem description. What isn't stated is that the grid goes on infinitely to the right. So for example: given this input:

1

*XXXXX
X X
XXXXX
____

You should output:

#####
#XXXXX#
#X X#
#XXXXX#
____


Basically, make the grid you work on one column wider than the length of the longest string in the input.

Also, don't leave trailing spaces at the end of your lines.

See Also:
- Problem 784 (Maze Exploration)
- Problem 785 (Grid Colouring)

This Miguel Revilla guy is not very creative...


#784 - Maze Exploration

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: This is a simple floodfill problem. Just run floodfill starting from the asterix, and fill with hashes.

Do not print any trailing whitespace at the end of the lines.


#785 - Grid Colouring

Solved By:wesley
Theory Difficulty:easy
Coding Difficulty:easy
Algorithms Used:other graph
Solution Description: We're guaranteed that all non-contour, non-space characters are inside contours. So, do a DFS/BFS from the upper-left corner, and the first non-space character you hit will be the contour character.

Now, search the grid for all non-contour, non-space characters and do a floodfill from each one to fill in the contour.

Beware the extremely pedantic output requirements. Every line you output must be exactly the length of the input line, including all trailing whitespace.

See Also:
- Problem 782 (Contour Painting)
- Problem 784 (Maze Exploration)





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