3.5. Timer

Why use a timer?

In practically all olympiads that use automatic evaluation, each test run has a time limit placed on it. While some problems are "all or nothing", there are other problems (particularly optimisation problems) for which it is possible to get some marks for a nearly correct answer. In these cases, you might have already found such an answer inside the time limit, in which case you want to stop and output this answer rather than exceeding the time limit to find the best answer.

How do I measure time?

There are essentially three ways to do it.

  1. Use a function provided by the contest organisers. This is normally a function that will tell you how long your program has been running. This is obviously the best way to do it.
  2. Use some library function to measure time. This may not match up to the way the contest environment measures time (e.g. CPU time versus wall clock time), and may not be legal in some contests.
  3. Use a counter which you increment inside a loop. You will need to calibrate this counter.

Other issues

The primary issue is to decide how often to check the time. If you check too seldom, you might end up going over time anyway, but checking too often will slow down your program. Generally a good bet is to place the check just outside your innermost loop, but ultimately you need to decide what is best for each solution.

You also need to exit once you've determined that you've used enough time. It is often a good idea to user a timer in conjunction with an exit procedure. In this case, executing halt(0) will set the exit procedure in motion, and all your cleaning up can be done in there.

[Prev] [Next] [Up]

Last updated Sun Nov 28 22:32:52.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).