Changes 11/7/14
UMD Programming Contest:
- Had a conversation with Kevin about more efficient ways to fulfill the functionality requested by the Pythagorean triples problem from the contest.
- He suggested converting the array to a hash, using two for loops in order to identify a and b values, then checking if the corresponding c value was present in the hash.
- Since getting a specific element in a hash table is an O( 1 ) operation (although I haven't learned that yet), his solution would bring this down to O( n2 ).
- He also suggested pre-sorting the array and pre-squaring all the values, which would bring performance benefits for large values of n
- Looked at UMD's solution to the Pythagorean triples problem
- I guess I'm not quite clear on the design philosophy behind this contest. Are we supposed to have the simplest solution, the most elegant, the fastest? Can I pull in more advanced constructs like Hashes, or am I stuck with only the default imports of Java. In their solution for this problem, they used Arrays.sort(), but did not use Math.pow().
Great questions. Let me answer those that I can. Most of the time, you want arrive at an acceptable solution in the shortest time you can. Neither elegance nor efficiency count, except when you are told that there is a runtime limit for an passing solution. You can't add any libraries beyond what comes with the standard Java distribution. The focus is on writing your own algorithms for solving the problems given to you (as a team) as quickly as you can.
ReplyDeleteI haven't been to the contest for several years now, but there was a special $500 prize for "the most elegant numerical solution" to one of the given problems. It that is still the case, it is in addition to, and not instead of the time requirement for the overall contest.