Lambdabamserne slår til igen med sejr ved DM i programmering

De tre studerende fra DIKU blev også nummer to i det nordiske mesterskab, da der denne weekend blev afholdt programmeringsmesterskaber for studerende.

Jesper Stein Sandal@jespersandal Tirsdag, 4. oktober 2011 - 8:077

For andet år i træk kan Lambdabamserne fra Datalogisk Institut på Københavns Universitet, DIKU, kalde sig danske mestre i programmering. Det skriver DIKU på instituttets hjemmeside.

Holdet vandt DM-titlen i programmering i 2010 og vandt altså igen, da der denne weekend blev afholdt mesterskaber i programmering for studerende.

Læs også: Se C++-koden: Sådan blev Lambdabamserne danske mestre i programmering

Ud over titlen som danske mestre opnåede holdet også en placering som nummer to i det nordiske mesterskab, hvor holdet dog måtte se sig slået på tid af svenske Team Squirrel fra Chalmers universitetet.

I alt deltog 85 studerende fra Danmark i konkurrencen Nordic Collegiate Programming Contest, som i Danmark sponsoreres af Netcompany og afholdes på de datalogiske institutter ved Københavns Universitet, DTU og Aarhus Universitet.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk

Kommentarer (7)

Torben Mogensen Tirsdag, 4. oktober 2011 - 9:49 Blogger

Godt gået

Tillykke med Danmarksmesterskabet og andenpladsen i den nordiske turnering.

Sebastian Paaske Tørholm Tirsdag, 4. oktober 2011 - 11:47

Scoreboardet: http://ncpc2011

Scoreboardet: http://ncpc2011.contest.scrool.se/standings/?country=dk&icpc
Opgavesættet: http://ncpc2011.contest.scrool.se/ncpc2011problems.pdf

Thue Kristensen Tirsdag, 4. oktober 2011 - 13:20

Opgave B?

Hvordan løser man opgave B? Bare den simple n^3-løsning, hvor man bare skanner fra højre? Er der nogen tidsbegrænsning?

Sebastian Paaske Tørholm Tirsdag, 4. oktober 2011 - 13:28

Re: Opgave B?

Der er tidsbegrænsning på, ja. Jeg er dog ikke sikker på præcis hvor lang tid, men det ligger i omegnen af 1-3 sekunder.

Vores løsning til B'eren benyttede sig af Fenwick træer, og kan ses hér: Opgave B

Thue Kristensen Tirsdag, 4. oktober 2011 - 17:33

Re: Opgave B?

Til dem der er nysgerrige:

add(fenwick træ, position, antal) : tilføj antal til position (log n tid)

get(fenwick træ, position) : returner summer af indgangene 1..position i træet (log n tid)

N: antallet af tal

fenwick-træ p: Tallene, i omvendt rækkefølge.

fenwick-træ c: Antallet af tal mindre end p[i]

fenwick-træ a: Antallet af forekomster af tallet i er i position i

fenwick-træ aa: Antallet af a<b par mindre end i er på position i.

Plus at træerne bruger mens de bliver fyldt og brugt, så rækkefølgen af tal bliver respekteret, og fx indgangene i c-træet kun tæller tal som står til venstre for det tal man kigger på.

Fenwick-træ: http://michaelnielsen.org/polymath1/index.php?title=Updating_partial_sum...

Det er smart :). Havde i set det problem (og den løsning) før?

Thue Kristensen Tirsdag, 4. oktober 2011 - 17:36

Re: Opgave B?

Men vel egentligt unødvendigt at bruge fenwick-træer; ville almindelige lister ikke have været hurtige nok?

Thomas Dybdahl Ahle Onsdag, 5. oktober 2011 - 14:14

Re: Opgave B?

Thue: Almindelige lister ville have givet en n^2 algoritme. Med n op til 10^5 var der behov for nlogn.

Log ind eller Opret konto for at kommentere

Pressemeddelelser

Welcome to the Cloud Integration Enablement Day (Bring your own laptop)

On this track, we will give you the chance to become a "Cloud First" data integration specialist.

Affecto Denmark

15. nov 2017

Silicom i Søborg har fået stærk vind i sejlene…

Silicom Denmark arbejder med cutting-edge teknologier og er helt fremme hvad angår FPGA teknologien, som har eksisteret i over 20 år.

Silicom Denmark

22. sep 2017

Conference: How AI and Machine Learning can accelerate your business growth

Can Artificial Intelligence (AI) and Machine Learning bring actual value to your business? Will it supercharge growth? How do other businesses leverage AI and Machine Learning?

13. sep 2017