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 forcemath 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 hocstrings 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 hocsimulationstrings 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: simulationstrings 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 hocmathstrings 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 hocrecursion 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 flowstrings 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 