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. #900  Brick Wall PatternsSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  brute force
 Solution Description:  BF generate all the Fibonacci numbers and given n, output f[n];
just remember> f[0] = 0, not 1 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  It's just the Fibonacci sequence. Print out Fi for any i.
I just pregenerated the first 50 numbers, and then printed them out when necessary. 
#902  Password SearchSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  strings
 Solution Description:  I got this to run in time in Java.
You have to use a HashMap (a handy object from the jdk) and use each substring as a Hash key. Take the input in, iterate through the string, and for each substring:
If the HashMap already contains a value for that key, add one to the value.
Otherwise, add the value of 1 to the key for that substring.
Make sure, though, that you handle test case where the number given and the string given are on different lines! They don't really tell you that in the input  annoying. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  searching strings
 Solution Description:  Use a HashMap where the keys are substrings, and the objects in the HashMap are Integers. For each substring of the given length, pull the corresponding integer from the hash table and increment it (and put it back). If no integer exists with that key, then add a new one with initial value 1.
Keep track of the best value as you go so you don't have to search through the hash table later. Use BufferedReader and StringBuffer in Java to make this run in time. 
#913  Joana and the Odd NumbersSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Write out the index of odd numbers 1  16 in the pattern shown in the question. You'll realize that the index of the first number of each row is:
(row*row) + 1 ... they're squares
You can use a formula (1 + 2x) to get the xth odd number. From there it's trivial to get the last three numbers of that row. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  If you look at the first few rows, you can discover the pattern. Where N is the input number:
Let X = 2*((N/2) + 1)^2  3
X is the second to last number in the row with N digits. It's also the average of the last three numbers in that row, so just multiply X by 3 and output it. 
#914  Jumping ChampionSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Not too bad. Generate all primes using the sieve from 2 to 1000000.
Put the primes into a smaller array (about 72000 primes I think)
For each lower and upper bound given, linear search to the lower bound in your primes array, and just iterate upwards with a diff[] array to hold the number of times a difference occurred, while tracking your maximum diff and its number.
Output your maximum.
You'll also need to have a 'nummax' variable which counts the number of different differences that share the current maximum number of occurrences, and reset it to 1 every time you set max to something new. That way, when you end up with two jumping champions, you can detect it and output a failure.

Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  dynamic programming math
 Solution Description:  Use the Sieve of Eratosthenes to generate all the primes up to 1,000,000. For every lower and upper bound, just use a linear search to determine which primes you're going to search between.
If you find only one prime, return failure. Otherwise, keep an array where a[i] is the number of times the a difference of i has occurred between two primes. Then just search through the array to find the greatest a[i]. If there's a tie, return failure. 
#924  Spreading The NewsSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  other graph
 Solution Description:  Setup the adjacency matrix, but be careful. For this problem, the friendship links are NOT bidirectional (sad but true).
Run BFS from the starting point they give, and hold a daycount array.
When you BFS, use two dimensional objects instead of just integers, so that the first dimensional can be the node index, and the second the day that it was reached.
Every time you look at a new node in your Queue, add unvisited friends to it with their day values = the current + 1. Also, for each friend you add, increment the appropriate element in the day array, and at the end find the earliest day with the highest count.
I'd rate this problem as easymedium. Consequently, I'll make... coding medium, since it can take a bit of work if you don't know exactly what you're doing. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  other graph
 Solution Description:  For each source, do a BFS to all other employees. Keep track of the distance to each employee, and keep track of how many times each distance comes up.
After the BFS, look for the distance that appears the most frequently, with ties broken by shorter distance. Output how many people have this distance, and what the distance is. 
#929  Number MazeSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  medium  Algorithms Used:  dijkstra
 Solution Description:  Wow, what a problem.
It's quite obviously Dijsktra, with some horrifying exceptions:
You cannot use a conventional adjacency matrix, ([x][y][x2][y2]) since you'll have a java heap space error on your hands. You have to settle with an adjacency matrix [x][y] that holds the distance from 0, 0 to x, y. You then perform:
adj[x+i][y+j] = Math.min(adj[x+i][y+j], adj[x][y]+grid[x+i][y+j]);
The input on this is ridiculous. Even with a stringbuffer and a bufferedreader I can't get it to run in time on Java. If you just parse the input and output garbage, it takes 1.5 seconds to run!
You need to be AS EFFICIENCT as humanly possible if you want any chance in getting this to AC. One possible strategy (that still isn't enough for me apparantly) is to use 10 stacks instead of the 1 priority queue. This is because the nodes you are to visit will be sorted by their values in the grid, and they are only from 0..9. So what you would do is pop a node onto the stack corresponding to their grid value, and always pop the next node off the lowest stack you can. 
Solved By:  wesley  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  dijkstra sorting
 Solution Description:  This is an evil version of a simple Dijkstra problem. The problem isn't that there are any strange constraints, but that there is *so much input*.
The idea behind this problem is to find a faster way of doing Dijkstra than O(E log V), given this special type of graph (that is, one in which all weights are less than 10). This can be accomplished by using 10 queues. The idea works as such:
When you want to get the next node, search all of the queues in order until you come to one that isn't empty. Take the top node from this one. When you add a node to the queues, add it to the one that is c queues away from the one you are currently at, where c is the cost of traversing that node.
For example, in the first test case:
 The starting node has cost 0, so we put it onto queue 0. We dequeue this node, and look at it's neighbours. They have costs 3 and 7, so they go in queues (0+3)%10 and (0+7)%10 respectively.
 Next, we take the node from queue 3 and examine its neightbours. They have costs 1 and 3, so they go in queues 4 and 6 respectively.
So you make your way around the queues in a circle, and you keep taking from one queue until either it is empty, or the next queue in the circle has a node at the front that has shorter distance.
I haven't been able to get this to run in time in Java, though it is *apparently* possible, but in a very, very irritating manner. I've managed to get this done in C in 0.888s using a handmade queue. 
#948  Fibonaccimal BaseSolved By:  peter  Theory Difficulty:  medium  Coding Difficulty:  medium  Algorithms Used:  greedy math
 Solution Description:  Pregenerate all the fib numbers up to and including whatever is just over/under 10 000 000.
For each decimal number you get, loop back from this big number to the smallest, subtracting from your variable 'decimal' each time if the fib <= decimal. When you subtract, output a 1. When you don't, output a 0 (if you've outputted a 1 before).
The rest is just formatting. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Pregenerate an array, f[], of Fibonacci numbers (no more than 45).
For each input n, loop through your array from highest to lowest. If n >= f[i], add a "1" to an output string and decrement n by f[i]. Otherwise, add a "0". Make sure not to add any "0"s before "1"s. 
#967  CircularSolved By:  peter  Theory Difficulty:  easy  Coding Difficulty:  easy  Algorithms Used:  math
 Solution Description:  Pregenerate your results.
You'll need a boolean array to generate the primes, and an integer array to store your results. Fill the boolean array to initially be true!
Use a prime sieve to generate all the primes with the boolean array, and whenever you find a prime, test to see if its circular  if so, res[i] = res[i1]+1, otherwise res[i]=res[i1]
I only now realize that this isn't a really correct solution. You should generate the primes FIRST, and THEN go through each prime. However, it just so turns out, that each prime you encounter (that they ask you about at least) is circular.
Note: You need to use a bufferedreader and a stringbuffer. 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  There are only 55 circular primes below 1,000,000, so you can generate them beforehand and hardcode them into the problem (not entirely necessary, but handy).
Then, for each range given, just iterate through your circular primes array and check how many lie inside the range.
Use BufferedReader and StringBuffer to ensure that this runs in time in Java. 
#974  Kaprekar NumbersSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  math strings
 Solution Description:  Pregenerate all the kep numbers up to and including 40000, and keep them in an arraylist.
Iterate through the arraylist for each input, and output the numbers within the given range. 
Solved By:  wesley  Theory Difficulty:  trivial  Coding Difficulty:  easy  Algorithms Used:  brute force math
 Solution Description:  Pregenerate an array of booleans where a[i] is true if i is a Kaprekar number. Then for any input pair (x,y) just search the array for i from x to y outputting whenever a[i] is true.
To determine whether a number n is a Kaprekar number, just cast n^2 to a string and search through all possible substrings, seeing if the left hand side and the right hand side add to n. 
#991  Safe SalutationsSolved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  dynamic programming math
 Solution Description:  Let a[i] be the number of ways i pairs of people can shake hands.
It's easy tell that a[0] = 1, a[1] = 1, a[2] = 2.
For larger n, imagine choosing an arbitrary pair of people to shake hands. You've now divided the circle into two smaller circles (one of which may have 0 people in it). The number of ways you can arrange the rest of the people is the product of the answers for the two smaller circles.
So for example, to compute n = 3:
a[3] = a[0]*a[2] + a[1]*a[1] + a[2]*a[0]
a[4] = a[0]*a[3] + a[1]*a[2] + a[2]*a[1] + a[3][0] 
#993  Product of digitsSolved By:  peter  Theory Difficulty:  trivial  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Keep a stringbuffer for output, and take the number in a variable s.
while(s >= 10)
loop from 9 to 2 with i
if(s % i == 0)
s /= i
Every time you find an i that evenly divides s, add it to your output stringbuffer. Sort the stringbuffer's characters ascending, and output it along with the remaining s (if it's > 1). 
Solved By:  wesley  Theory Difficulty:  easy  Coding Difficulty:  trivial  Algorithms Used:  math
 Solution Description:  Factor all onedigit numbers out of the given number, from 9 down to 2. Every time you factor a number out, add it to an output string (which will always be nondecreasing order).
Make sure you handle the special cases of 0 and 1. 
Copyright 2008 (c) QuestToSolve.Com  Graphs Powered By
