OLYMPIADS IN INFORMATICS, 2009, Vol. 3, 132-143
© Institute of Mathematics and Informatics,
ISSN 1822-7732
Improving the Automatic Evaluation of Problem Solutions in Programming Contests
Pedro RIBEIROa, Pedro GUERREIROb
aDepartamento de Ciência de Computadores, Faculdade de Ciências, Universidade do Porto Rua do Campo Alegre, 1021/1055, 4169-007 Porto, Portugal E-mail: pribeiro@dcc.fc.up.pt
bUniversidade do Algarve 8005-139 Faro, Portugal E-mail: pjguerreiro@ualg.pt
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
To preview full
article text in PDF format click here
You
could obtain free Acrobat Reader from Adobe
Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2009