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' DilemmaSolved 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 DisplaySolved 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 NumbersSolved 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 ProblemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc strings
 Solution Description:  Create an array with nh 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 IndexingSolved 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 CodeSolved 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  ExponentiationSolved 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 lefthand side to make up for the difference. 
#750  8 Queens Chess ProblemSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  ad hoc recursion
 Solution Description:  8Queens 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 rightaligned in a column two characters wide. This doesn't seem to be stated anywhere in the problem description. 
#753  A Plug for UNIXSolved 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 NumbersSolved 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 PaintingSolved 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 ExplorationSolved 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 ColouringSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  We're guaranteed that all noncontour, nonspace characters are inside contours. So, do a DFS/BFS from the upperleft corner, and the first nonspace character you hit will be the contour character.
Now, search the grid for all noncontour, nonspace 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
