The TopCoder Easy

The easy division one problem on TopCoder is a weird type of problem, that I'm not sure exactly how to tackle. The problem almost always has a very short (~15 lines of code) solution, but normally you need at least one insight to get to that solution. My problem has always been either finding the insight, or being able to prove its correctness.

For the last two SRMs I have solved the easy using a more complicated approach, but one that doesn't require much insight at all. Take OrderedNim(http://www.topcoder.com/stat?c=problem_solution&rm=302474&rd=13904&pm=10190&cr=22657324) for example. The answer is directly related to whether or not the piles have one stone or more than one, but I couldn't think of the exact solution. Instead I just used DP to solve the problem. Sure it took me longer to code, but it avoided a leap of faith in doing so.

I'm still not sure if it is optimal to spend more time looking for the elegant solution, or to just dive into the longer solution. At this point I am confident enough in my coding that I'm not going to lose much time by coding the longer solution. On the other hand I think I am also running away from the elegant code because I don't have the solution. It is hard to force yourself to think of a better way when you have found a method that works.

I am probably doing something wrong because my times for the easy solutions have not been great. ()They haven't been bad, but for the last two SRMs my mediums have carried a majority of the weight. I'm very happy to be able to get fast times and still be very confident that my code is correct. I got the fastest medium overall in SRM 450 and the fastest Java solution in 451 (~10th overall). ()