Portal de Periódicos da CAPES

Programming contest strategy

2006; Elsevier BV; Volume: 50; Issue: 3 Linguagem: Inglês

10.1016/j.compedu.2006.08.008

1873-782X

Andrew Trotman, Chris C. Handley,

Game Theory and Applications

Each year the ACM hosts a truly international programming contest – the International Collegiate Programming Contest (ICPC). Dating back to a contest held by Texas A&M University in 1970, this annual event, along with the associated regional contests, has grown to 5606 teams from 1733 universities in 84 countries (in the year 2006). Despite the maturity of the event, and the number of competitors, there has never been a systematic examination of contest strategy. Herein several strategies are proposed and examined to determine whether a team can gain an advantage by choosing a good strategy; and, if so, then what that strategy should be. We show that a team can gain an advantage by choosing a good strategy, but that there is no one best strategy. A team must choose between winning by number of solved problems and winning by points. Finding the optimal strategy to win by problems is shown to be NP-complete, while to win by points a team must solve problems in order from easiest to hardest.