Monday, May 24, 2010

GCJ 2010: Load Testing in Common Lisp (wrong)

I thought a little about this problem, and then had the idea that the optimal strategy would be to do a binary search between L and P in log-C space. So the required number of tries would be

(defun min-tests (l p c)
  (max 0 (ceiling (log (- (log p c) (log l c)) 2))))

This gave the correct results for the tiny input set on the problem description page, but unfortunately failed on even the small competition set. At this point I gave up and passed on to C (Making Chess Boards), which was more fun anyway.

Later I noticed that someone else solved the small set in Lisp in an identical way, except they computed the log-C distance differenty:

(defun min-tests (l p c)
  (max 0 (ceiling (log (log )/ p l) c) 2))))

With this modification, my code successfully solved the small practice set! Just shows that floating-point arithmetic should never be trusted.

Unfortunately this fails on the large input set, probably because the approach is too simplistic.

No comments: