2004 Heat 1 ACM Programming Competition Solutions

<=
 
  Question 1A
  Question 2B
  Question 3C
 

Question 1A - Rename

  • Problem Sheet
  • This was not quite as easy as it looked. It is just a cut and paste game around the '*', but not a single team passed their first or second attempt against the 'judges data'. Mostly they failed to properly consider the 14 character limit for file names, and the output data contained a rename which would result in a 17 character name if enacted upon. While many teams argued the behaviour was not sufficiently specified, not one of them indicated any kind of error, they simply printed the 'mv' command as if it was acceptable (which it could not be). The second killer in the judges data was that the pattern "abcd*dcba" cannot match the file name "abcdcba", causing lots of -1 substring exceptions or other mistakes as people failed to seperate letters used for the first match against letters used against the second.
  • Sample Solution [input=>output] [input=>output]


Question 2B - Bit String with Distinct Substrings

  • Problem Sheet
  • This is unavoidably a math question. First and foremost a lot of people had difficultly understanding the question. The goal is not to produce a (say) 36 bit number with 7 unique substrings tacked together, the goal is to produce a 36 bit number where every choice of 5 consectutive bits was different from every other choice of 5 consecutive bits. A lot harder, and I can't see a way of doing this without a full history of where you have previously exhausted your options (or paying a massive time penalty constantly recalculating that fact). The second thing that was hard about the problem is that you need to consider all n of your future substrings each time you make a choice between 0 or 1, otherwise you risk choosing a path that will later on require you to backtrack from. Using an actual tree is slightly slower, but allows for slightly larger numbers v.s. using a flattened tree implicitly stored in an array. I have also provided a couple of extra functions for double-checking an answer since 'human inspection' is clearly inadvisable.
  • Sample Solution [input=>output] [input=>output]


Question 3C - Base

  • Problem Sheet
  • This turned out to be a painful reminder of the limitations of modern computers for most people (including me)! However it also proved to be a great reminder of not trying to re-invent the wheel too! A few seconds of maths will reveal that 35^35 > (2^5)^35 = 2^165. Which is far in excess of any primitive type of any language I know about. Some people realised this faster than others, with the quickest time being about 5 minutes for a team which had good hearing! Obviously, for those people not using a library-rich language, this question would be much, much harder. My solution also uses the input data "0 0 *" as a terminating sentinal.
  • Sample Solution [input=>output] [input=>output]

Updated 30 / 8 / 2004