2003 Heat 2 ACM Programming Competition Solutions

  Question 1A
  Question 2B
  Question 3C

Question 1A - Does This Make Me Look Fat

Question 2B - Surround The Trees

  • Problem Sheet
  • This is unavoidably a math question. There are several different ways you can approach this problem (divide & conquer; outlier points; etc...) but at some point you have to know the equation for working out the distance from an arbitrary point to an arbitrary line (known as the cosine rule. The data size is actually pitiful, so a less efficient N^2 solution will probably pass, but ideally this problem should only be as comlpicated as your best list sorting algorithm (like QuickSort).
  • Sample Solution [input=>output]

Question 3C - Treasure Hunters

  • Problem Sheet
  • I do not have a good solution for this problem. This is a hard question. If you don't believe me you should actually try running your problem with the full 100x8x6 data set that the question actually covers. The bottom line is that you will need to have a searching algorithm that is heavily pruned, but is still able to avoid the problem of "local maxima" (a real concern with this kind of problem).
  • Sample Solution (incomplete) [input=>output]

Updated 10 / 9 / 2003