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). ()

The Programming Contest Version of Chicken

In the last few practices we have had a couple of problems that have induced an interesting phenomena. The best example is one problem from world finals last year. It was questionable whether the brute force solution would time out or not. My team decided to wait and just look at the scoreboard in 15 minutes. When we checked the scoreboard a bunch of teams had a wrong answer for the problem and no one had solved it. We had our answer without wasting any of our time solving the problem.

Assuming all parties recognize that the problem may or may not be brute force able it seems optimal to always wait until someone else attempts it. On one side if you are able to brute force it you will have a smaller time penalty, on the other side if it isn't you waste console time. In general I think that console time is more important.

At world finals I think it is much more crucial to not spend times on problems you don't solve then to worry about time penalty. All but a few teams there will solve no more than 6 of the 10 problems. You can waste a ton of time by attempting one of the harder problems and never solving it. This creates an even better argument for not attempting the questionably brute force able problem.

At world finals there will probably always be a couple teams who are too optimistic and try the brute force solution, but at regionals that may not be the case. My region (East Central North America) had only 5-6 top teams last year. In theory this could lead to a phenomenon where a lot of the top teams don't solve a brute force able problem until very late into a contest.