Lambdabamserne vinder DM i Programmering 2010

Tre københavnske datalogistuderende vandt DM i Programmering 2010. Holdet 'Lambdabamserne' slog konkurrencen af banen med fire ud af 11 korrekte besvarelser.

Tre datalogistuderende fra København vandt lørdag den 2. oktober konkurrencen DM i Programmering og en præmie på 10.000 kroner efter fem timers programmeringsdyst mod 26 andre danske hold studerende.

De tre studerende, Søren Dahlgaard, Mathias Bæk Tejs Knudsen og Sebastian Paaske Tørholm, har deres daglige gang på Datalogisk Institut ved Københavns Universitet, DIKU.

De var tilmeldt konkurrencen under holdnavnet 'Lambdabamserne', og det lykkedes dem at programmere korrekte løsninger til fire af de i alt 11 algoritmiske problemer, deltagerne blev præsenteret for.

»Det var det højeste antal korrekte løsninger i Danmark, mens tallet i Sverige var syv. Men svenskerne har også en længere tradition for at deltage i konkurrencen,« siger seniorkonsulent Kristian Staalø Knudsen fra it-virksomheden Netcompany, der arrangerer konkurrencen herhjemme.

Opdateret: Det var det finske hold Bubble Sorters, der som det eneste hold opnåede syv korrekte besvarelser. De svenske hold Nada og Lag Ekorre fulgte efter med henholdvis seks og fem korrekte besvarelser.

DM i Programmering 2010 er en del af Nordic Collegiate Programming Contest (NCPC) for studerende i hele Norden, der har været afholdt siden 2005. Lørdagen bød dermed også på tilsvarende konkurrencer i Sverige, Norge og Finland.

**LÆS OGSÅ **Er du klar til DM i Programmering 2010?

Konkurrencen begyndte klokken 11 lørdag den 2. oktober og sluttede fem timer senere klokken 16.

Deltagerne kunne frit vælge mellem programmeringssprogene C, C++ og Java og havde i løbet af de fem timer mulighed for at uploade koden til afprøvning på NCPC's automatiserede testserver.

Alle holdene kunne undervejs følge med i, hvordan det gik de andre hold.

»Det gav et øget element af konkurrence mellem holdene, at de løbende kunne afprøve deres kode og se status over, hvor langt de andre hold var kommet i konkurrencen,« siger Kristian Staalø Knudsen.

Ifølge Kristian Staalø Knudsen agter 'Lambdabamserne' at bruge præmien på 10.000 kroner til at dække rejseudgifterne til den kommende europæiske udgave af programmeringskonkurrencen.

I alt deltog 27 hold på 2-3 personer i DM i Programmering 2010. 14 af dem dystede på DTU i Lyngby, mens de resterende 13 indfandt sig på konkurrencens anden lokation på Datalogisk Institut ved Aarhus Universitet.

Det har ikke været muligt at få en kommentar fra de tre studerende bag vinderholdet 'Lambdabamserne'.

De 11 problemer havde følgende overskrifter:

A Succession
B Connect
C Borg Boogie
D Dirty Driving
E Doodling
F Help a PhD candidate out!
G Great Geek Game-show 3000!
H Polyomino Powers
I Statisticians
J Skyline
K Around the track

Eksempel på problemet 'Succession'

The king in Utopia has died without an heir. Now several nobles in the country claim the throne. The country law states that if the ruler has no heir, the person who is most related to the founder of the country should rule.

To determine who is most related we measure the amount of blood in the veins of a claimant that comes from the founder. A person gets half the blood from the father and the other half from the mother. A child to the founder would have 1/2 royal blood, that child's child with another parent who is not of royal lineage would have 1/4 royal blood, and so on. The person with most blood from the founder is the one most related.

Input specifications

The first line contains two integers, N (2 <= N <= 50) and M (2 <= M <= 50).

The second line contains the name of the founder of Utopia.
Then follows N lines describing a family relation. Each such line contains three names, separated with a single space. The first name is a child and the remaining two names are the parents of the child.

Then follows M lines containing the names of those who claims the throne. All names in the input will be between 1 and 10 characters long and only contain the lowercase English letters 'a'-'z'. The founder will not appear among the claimants, nor be described as a child to someone else.

Output specifications

A single line containing the name of the claimant with most blood from the founder. The input will be constructed so that the answer is unique. The family relations may not be realistic when considering sex, age etc. However, every child will have two unique parents and no one will be a descendent from themselves. No one will be listed as a child twice.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (13)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#1 Torben Mogensen Blogger

Et stort tillykke til de tre DIKU studerende!

Jeg går ud fra, at problemerne var i stigende sværhedsgrad, for [i]Succession[/i] problemet er i hvert fald nemt.

Jeg er dog lidt skuffet over, at sprogene er indskrænket til C, C++ og Java. Lidt mere moderne sprog såsom ML, Scala, Python og Haskell havde været på plads.

  • 0
  • 0
#2 Sebastian Paaske Tørholm

Der er forskellig sværhedsgrad på problemerne, men den følger ikke nødvendigvis nummereringen af dem.

Opgave F, A og D var de nemmeste opgaver.

Vi løste A, D, F og G, men er ret sikker på at vi havde en løsning til opgave I klar; vi havde bare misset stedet i opgaveteksten hvor der stod at vi skulle outputte med 3 decimaler, hvilket gjorde at den blev afvist en del gange.

Scoreboardet kan ses hér: http://ncpc2010.scrool.se/standings/?icpc

Opgavesættet kan ses hér: http://ncpc2010.scrool.se/ncpc2010problems.pdf

  • 1
  • 0
#5 Torben Mogensen Blogger

De fleste af dem, der slet ikke løste nogle problemer, har slet ikke indsendt nogen svar, så det er muligt, at de var tilmeldt men alligevel ikke deltog. At 24 hold (som tilsyneladende lavede et seriøst forsøg på at deltage) kun løste kun et problem, synes jeg er mere pinligt.

Det er i øvrigt flot, at DIKU, der kun stillede op med et enkelt hold, slår både DTU og Århus, som stillede op med hhv. 7 og 6 hold. Vi burde nok sende flere hold næste år.

  • 0
  • 0
#8 Lasse Lindgård

Ja, det forstår jeg heller ikke. Er det noget med tiden. De brugte jo 1014 minutter på 6 opgaver, mens lambdabamserne kun brugte 188 minutter på 4 opgaver.

Et andet spørgsmål er at hvis det kun brugte 188 minutter på 4 opgaver, hvorfor så ikke løse nogle flere?

  • 0
  • 0
#9 Jakob Kragelund

Konkurrencen er for studerende, men alle kan deltage. Det er således kun studerende der har studeret under et vidst antal år der officielt kan vinde konkurrencen, og dermed få de 10.000 og mulighed for at gå videre i den europæiske konkurrence.

  • 0
  • 0
#12 Søren Dahlgaard

@Lasse Det er sandt vi brugte 188 minutter (dvs. 70 rigtige minutte) på de første 4 opgaver (og vores computer var endda crashed i et kvarter). Dernæst løste vi opgave C og I og brugte resten af vores tid på at debugge dem, da graderen gav os "Wrong Answer". Det viser sig dog, at vi skulle have brugt "%.3f" i stedet for "%f" i opgave I, og der har været en anden ligeledes dum fejl i opgave C. Hvis vi havde set det havde vi nok også kunne løse de lidt lettere B og J.

@Baldur De to hold fra århus med 5 og 6 opgaver var ikke "ICPC eligible" og Netcompany vil selvfølgelig helst give penge til folk der kan bruge dem på andet end sprut og piger :)

@Torben Det er muligt, at nogle af holdene ikke løste særligt meget, men jeg ved også at i hvert fald AU bruger meget mere energi på denne konkurrence end KU (der bruger præcist ingen energi). De har interne konkurrencer og anbefaler folk at tage til det, da det er yderst lærerigt og man møder en masse nice mennesker. Det betyder selvfølgelig også, at der er nogle hold, der måske ikke har evnerne, men har gåpåmodet, hvilket jeg da synes, at man skal anerkende!

  • 2
  • 0
Log ind eller Opret konto for at kommentere