Improving the automatic evaluation of problem solutions in programming contests
- Article: Improving the automatic evaluation of problem solutions in programming contests
- Author(s): Pedro Ribeiro, Pedro Guerreiro
- Journal: Olympiads in Informatics 3 (2009), 132-143
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
Download: http://www.mii.lt/olympiads_in_informatics/htm/INFOL048.htm (free)