2001 ACM Programming Competition Solutions

<=
2001 Regional Results
 
  Question 1
  Question 2
  Question 3
  Question 4
  Question 5
  Question 6
  Question 7
  Question 8
  Question 9
 

Question 1 - Prime Digital Roots

  • Problem Sheet
  • Wow, a pretty nasty problem right off the bat. The hard part is coming up with a way of testing if 999,999 is prime as many times as they throw it at you in the given time frame!
  • Sample Solution [input=>output]


Question 2 - Desert Bitmap

  • Problem Sheet
  • Very basic pattern matching problem. Only real tricks are making sure you keep your rows and columns in the right order and that you don't run off of the end of the grid in the last few rows/columns. This is the kind of problem made much cleaner using Java.
  • Sample Solution [input=>output]


Question 3 - Normalized Histogram

  • Problem Sheet
  • Pretty simple problem, just a whole bunch of range-fiddling going on to work out which of the seeds given will form the best fit for the data that is given. Ironically you don't actually need to sort the data! I probably could have collapsed some of my function calls, but I like it better this way, just in case there might be a similar problem but with slightly different values in the future.
  • Sample Solution [input=>output]


Question 4 - Encryption Scheme

  • Problem Sheet
  • This looks like a state searching problem, but it isn't really. The key difference is that we don't need to actually keep any of the solutions that we generate, only determine the smallest solution possible. The only information we need to track is the current minimum generation that could reach each position in the string, and then eliminate paths that go past that, and explore paths which take fewer steps than that. The tricky part of the question is finding possible substrings of the message in the key, as this generates a large number of instructions even for relatively small strings. Fortunately, a HashMap makes this really quite easy for us, allowing us to save lots of time once the dictionary has finally been completed.
  • Sample Solution [input=>output]


Question 5 - James Bond

  • Problem Sheet
  • This might look like a searching problem, but it is really just a standard maze marking problem. Our goal is to only explore the minimum paths through the maze, and avoid any backtracking. In this way we only *explore* each node once, although we may see it a few times during our search. Don't forget to watch out that the input data numbers the nodes from 1, while both C and Java number them from 0. You might also forget to actually check whether the bomb could go off right as Bond steps into the terrorist's hideout.
  • Sample Solution [input=>output]


Question 6 - Basalt Buckets

  • Problem Sheet
  • Wow, this is a real gem of a question! What makes it really interesting is the amount of testing you need to do to actually work out whether a pillar is going to hold water or not. What I did was to build groups of 'potential' candidates for buckets of water, then check to see if any of the pillars 'stick out' from those groups. If it does stick out, we convert it to an edge (since it will never hold water), then recalculate the groups that pillar was previously participating in. Bearing in mind that we have to always consider the highest pillar first (as a high pillar might be able to hold water once an even higher pillar is blocked off), so it is much more efficient to sort the pillars by height first. This also buys us the *extremely* nice optimisation that once the highest pillar within a particular group is clear, all the pillars in that group are clear. This enables us to dramatically reduce the number of times we call the dynamic methods "join()" and "getLowestWall".
  • Sample Solution [input=>output]


Question 7 - Take 5

  • Problem Sheet
  • This is one of those questions you might want to skip simply because of the huge drain on time it will take to write up the solution. Which is not to say that the question is inherintly easy, no way! The key 'GOTCHA' behind these kinds of questions is the fact that a brute force search will take up far too much time on the Judge's test data (which is massive). In this question the key optimisation is to try and eliminate impossible combinations as early as possible, and as quickly as possible. To do this we create a staggeringly ridiculous number of HashMaps, each of which contains a very specific piece of information, constructed in the minimal O(words x length) time, but which can then be retreived and tested in O(1) time. This allows me to eliminate vast herds of letter combinations that would never work straight away, instead of having to continuously scan all of the patterns in the grid for every single combination of the alphabet (26 factorial). This is a very large solution (521 lines), so some care should be taken as you read through to make sure you understand the role each data structure plays in providing my solution as quickly as possible.
  • Sample Solution [input=>output]


Question 8 - Maximum Subsequence

  • Problem Sheet
  • Beware! This problem does not have a 'clever' solution, it is just outright hard. You will basically perform a depth-first search of all the possible subsequences of each of the words, occupying an enormous amount of time and space - hence the restriction on the input that the product space will be small enough to fit as an integer dereferencing a single linear array. This is necessary because doing arbitrarily dimensioned arrays can become quite expensive in most languages, in terms of the additional data structure overhead and dereferencing time needed. It is a simple optimisation to first eliminate those letters which will *NEVER* participate in a common subsequences, saving us an exponential amount of time per letter removed compared to the linear time needed to remove them.
  • Sample Solution [input=>output]


Question 9 - Kth Smallest

Updated 15 / 6 / 2004