2009 UMD Programming Contest - Judges' Hints and Notes
Problem A - Power Tower
- Idea - multiply the number 2 to any reasonable power.
- It was my high school pet project - Dennis. One idea was to create
an array or vector of digits to represent the number. First you start
by storing number 1 in position of the array with index 0. Then do n
iterations, where for each iterations you multiply the number by two.
While multiplying number by two, keep track of any carry digits, as
individual array cells overflow their maximum capacity (i.e. 10).
- I imagined this to be an easy problem, actually the easiest. But I
was biased. It is tricky, so indeed it turned out to be one of the
slightly harder problems.
Problem B - DJ Zhzyatslya
- Idea - sum up two fractions and print them out.
- DJ Zhzyatslya is a real DJ, of Russian-Ukrainian origin. His name
is hard to pronounce. Can you do it ?
- Note -- input had spaced in it, so that it was easy to read in
individual numbers without parsing the entire expression.
Problem C - Not a Composite Grid
- Idea - create a grid of primes satisfying prime adjacency rule.
- This problem was thought up by dimkadimon at TopCoder. There are a
few similar programs I know that do not involve a grid, but do involve prime
numbers. This is a really cool adaptation this type of problem.
I like it !
- The algorithm for this type of problem is called Depth First Search, or
Problem D - Dogs with Large Eyes
Idea - find number that repeat in the array, and print them out.
Hans Christian Andersen is a writer. He has a story called Tinder Box.
It will answer the question about whether I was sane when writing up this
Problem E - Reversible Primes
- Idea - find reversible primes in a given interval.
- Most of the difficulties people have had were with reversing a number,
and with coding a fast prime checker.
- Trick - those who pre-computed primes only up to 400,000, got a problem
after reversing this prime --> 100,009.