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 Patterns

Solved 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 Search

Solved 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 Numbers

Solved 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 Champion

Solved 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 News

Solved 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 easy-medium. 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 Maze

Solved 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 hand-made queue.


#948 - Fibonaccimal Base

Solved 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 - Circular

Solved 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[i-1]+1, otherwise res[i]=res[i-1]

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 Numbers

Solved 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 Salutations

Solved 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 digits

Solved 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 one-digit 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 PHPGraphLib - Click For Official Site