På billedet ses holdet "Eager", der bestod af Erik Søe Sørensen, Kasper Dupont og Jesper Torp Kristensen.
Daimiposten er internt meddelelsesorgan for studerende og medarbejdere ved Datalogisk Institut, Aarhus Universitet. Indlæggene er ikke udtryk for afdelingens officielle holdning.
Mange er nok ikke bekendt med, at Århus de seneste 2 år har været repræsenteret ved en international programmeringskonkurrence. Begge år lykkedes det alligevel Bartek Klin, der selv tidligere har deltaget som finalist, at udtage to hold til at konkurrere med over 40 hold fra hele Nordvesteuropa.
HISTORIEN
Konkurrencen, der arrangeres af ACM, tog sin oprindelse som en lille
lokal konkurrence i Texas i 1970, men udviklede sig snart til et
verdensomspændende foretagende. I de seneste 10 år har konkurrencen
været i en rivende udvikling; antallet af deltagende hold er vokset
fra omkring 500 til over 2700 og involverer nu over 70 lande. Det kan
således være med berettigelse, at den er blevet kaldt olympiaden i
datalogi. I 1989 kom der en lignende konkurrence på gymnasieplan og
dette har bl.a. været med til at øge interessen omkring konkurrencen.
Man har delt konkurrencen op i 6 divisioner, der så yderligere er opdelt i en række regioner. Århus hører naturligt under regionen Nordvesteuropa, der er en af de 6 regioner, Europa- divisionen er delt op i. Konkurrencen foregår i to trin. I hver af regionerne afholdes en lokal konkurrence, hvor et af formålene er at udtage et eller flere hold til en samlet finale. På verdensplan udtages blot 64 af de over 2700 deltagende hold til finalen, hvor verdensmestrene bliver fundet. Herudover bliver det bedst placerede hold i hver division kåret som mestre for regionen. Finalen dette år afholdes i marts på Hawaii, hvilket naturligvis gjorde det ekstra attraktivt at kvalificere sig.
Inden holdene når til selve konkurrencen, har de fleste været igennem indledende konkurrencer ved deres universiteter, og nogle har også været gennem nationale konkurrencer. Flere steder bliver studerende trænet specielt hen imod konkurrencen, og på enkelte universiteter i USA har man endog inddraget dette i den sædvanlige undervisning og tilbyder kurser, der har træningen som formål.
På billedet ses holdet "Eager", der bestod af Erik Søe
Sørensen, Kasper Dupont og Jesper Torp Kristensen.
ARRANGEMENTET
Dette års regionale konkurrence foregik den første weekend i november
i byen Darmstadt. Byen er lidt mindre end Århus, men ligger i et
tætbefolket område lidt syd for Frankfurt, kendt for dets mange
teknologiske industrier. Arrangementet begyndte officielt om
lørdagen. Efter registrering og velkomst var en præsentation af Merck,
der som sponsor sørgede for de praktiske rammer omkring
konkurrencen. En af de mere interessante dele var en beskrivelse af
deres arbejde inden for bioinformatik.
Herefter blev vi kørt i bus til kantinen hos Merck for at spise frokost - lidt spøjst når den kun var et par hundrede meter væk. Grunden var åbenbart deres sikkerhedskontrol. Konkurrencen skulle først foregå om søndagen, så der var afsat tid til en række forskellige aktiviteter. Som noget nyt var den sædvanlige foredragsrække udskiftet med forskellige ture. Man kunne bl.a komme på virksomhedsbesøg hos den sponsorerende Merck, besøge en kunstnerkoloni, Mathildenhöhe, kendt for sin Jugendstil eller få en guided tur rundt i byen.
Resten af eftermiddagen gik med en prøvekonkurrence, hvor man fik mulighed for at afprøve computerne ved at løse et par lette opgaver. Lige så vigtigt var det, at arrangørerne fik afprøvet deres systemer og havde mulighed for at få rettet praktiske problemer.
Her ses holdet "Lazy", der bestod af Kristoffer Hansen, Rune
Zedeler og Thomas Kragh.
KONKURRENCEN
Selve formen af konkurrencen er lidt uvant, første gang man prøver
den. Man er 3 personer på et hold og råder kun over en enkelt
computer. Målet er at løse så mange opgaver som muligt inden for 5
timer, helst så hurtigt som muligt. Disse spænder vidt fra algoritmisk
orienterede problemer over til problemer, hvor man selv skal finde
frem til en fornuftig metode. Arrangørerne imponerer hver gang med at
finde nye udfordrende og sjove opgaver. De er dog alle beskrevet
(forklædt) i mere eller mindre virkelighedsnære termer. Tit er en stor
del af opgaven at gøre sig helt klart, hvad problemet går ud på. Dette
år skulle man bl.a. hjælpe de allierede under 2. verdenskrig med at
bryde Enigma, finde en vindende strategi i et talspil og løse den
handelsrejsendes problem for en speciel slags grafer. En opgave løses
ved, at man konstruerer et program, der kan håndtere kravene i opgaven
og løse det beskrevne problem. Programmet løser en opgave, hvis det
svarer rigtigt på nogle hemmelige testdata. Man indsender sine
løsningsforslag under konkurrencen, og får kort efter at vide, om
opgaven er løst. Er den det, modtager man en ballon i en farve
svarende til opgaven. Ellers modtager man 20 strafpoint, men kun hvis
man i et senere forsøg løser opgaven.
At man kun har en computer på hvert hold, gør det nødvendigt, at holdet kan samarbejde godt. Dels skal arbejdet fordeles rigtigt, dels skal holdet kunne arbejde parallelt, så computertiden udnyttes optimalt. De sidste uger op til konkurrencen trænede vi netop i denne form, ved at forsøge os på opgaver, der er brugt ved andre regionale konkurrencer. Resultaterne her viste, at palmerne og de hvide strande på Waikiki beach ikke var helt uopnåelige.
Århus stillede to hold: "Eager", der bestod af Kasper Dupont, Jesper Torp Kristensen og Erik Søe Sørensen, og "Lazy", der bestod af Kristoffer Hansen, Rune Zedeler og Thomas Kragh. Vinderne løste 6 opgaver, mens andre hold måtte tage hjem uden balloner. Begge Århus-hold klarede sig pænt og løste hver 4 opgaver. Dette rakte hhv. til en 8. og en 11. plads.
Konkurrencen var sat til at starte kl. 10. Konvolutterne med opgaverne blev delt ud og nedtællingen startet. Konkurrencen var igang, og de næste minutter blev brugt til at skabe sig et hurtigt overblik over opgaverne. Målet var at udpege de letteste opgaver og derved komme i gang med at bruge computeren så hurtigt som muligt. Allerede efter 7 minutter havde et hold løst deres første opgave, og de modtog en sort ballon som tegn på dette. I de næste minutter dukkede flere balloner op i salen, alle sorte. Så kom der en rød ballon og kort efter endnu en. Dette viste at begge Århus hold også havde fået en god start, selvom vi startede med en anden opgave end alle andre hold.
Herefter skulle vi forsøge at holde samme gode arbejdsrytme som under træningen. Den sidste time blev stillingen holdt hemmelig, så kun holdene selv vidste hvor mange opgaver, de havde løst. Herved blev spændingen holdt indtil præmieoverrækkelsen. De to vindende hold havde inden sidste time hhv. 5 og 3 balloner. De to Århus hold havde også 3 balloner hver, men var kommet lidt i vanskeligheder med de sidste opgaver.
Derfor var det med lettelse og jubel at begge hold klarede at løse en sidste opgave få minutter før tid. Faktisk på præcist samme tidspunkt kunne vores træner Bartek fortælle bagefter. Herefter kunne vi blot vente på resultat-erne samt en præsentation af løsnings-forslag.
På adressen icpc.tu-darmstadt.de/contest/ er det muligt at se billeder taget under arrangementet, herunder holdbilleder. Desuden er der en sammenpresset udgave af en web-transmitteret video af konkurrencen. Det er her muligt at skimte ”Lazy”, hvis man holder øje med den første røde ballon.
Næste år må vi desværre sige farvel til vores træner Bartek, som har lagt et stort arbejde i bl.a. at udtage og træne holdene. Konkurrencen flytter også næste år, og vil blive afviklet i Delft, Holland.
Der er en regel om, at mindst to deltagere på hvert hold endnu ikke må have opnået en bachelorgrad. Derfor er der næste år behov for nye kræfter, da de fleste af dette års deltagere falder under denne regel. Vi håber, at nye deltagere måtte have fået lyst til være med i konkurrencen.
Sidste ændring: 5. december 2001
Daimiposten