Improving the Automatic Evaluation of Problem Solutions in Programming Contests

Pedro Ribeiro and Pedro Guerreiro

2009

Abstract

Automatically evaluating source program files is a crucial part of programming contests. The evaluation aims at discriminating programs according to their correctness and efficiency. Given the performance of today's computers, in order to be able to distinguish the complexity of solutions, it is often necessary to use very large data sets. This is awkward, because it is against the nature of the stated problem and puts an unintended burden on the input operations. Besides, by advertizing a limit for the size of the input, the problem description gives away information with which the contestants may guess the algorithmic complexity that their solutions must attain. It would be more realistic to omit that information and let the contestants discover the limits by analyzing the problem, using a scientific approach. The complexity of the solution can then be estimated automatically by measuring the execution time of the function that solves the problem in incremental test cases, and plotting it against the size of the input. By calling the function multiple times and taking the overall time, we may use only data files the size of which is related to the nature of the problem being solved.

Keywords

programming contests; computer science education; automatic evaluation; asymptotic complexity; IOI; International Olympiads in Informatics

Reference (text)

Pedro Ribeiro and Pedro Guerreiro. Improving the Automatic Evaluation of Problem Solutions in Programming Contests. In Olympiads in Informatics, Vol. 3, pp. 132-143, 2009.

Bibtex

@article{ribeiro-IOI2009,
  author = {Pedro Ribeiro and Pedro Guerreiro},
  title = {Improving the Automatic Evaluation of Problem Solutions in Programming Contests},
  journal = {Olympiads in Informatics},
  volume = {3},
  pages = {132-143},
  year = {2009}
}