Torben Mogensen
Blogger
Godt gået
Tillykke med Danmarksmesterskabet og andenpladsen i den nordiske turnering.
Lambdabamserne slår til igen med sejr ved DM i programmering
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.
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)
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?
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
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?
Re: Opgave B?
Men vel egentligt unødvendigt at bruge fenwick-træer; ville almindelige lister ikke have været hurtige nok?
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 en konto for at skrive kommentarer
I samarbejde med
Version2 er en del af Jobfinder - Danmarks største job- og karrieresite for ingeniører og it-professionelle.
Version2 er en del af Jobfinder - Danmarks største job- og karrieresite for ingeniører og it-professionelle.
- 18 KMD og den omvendte bug bounty
- 14 Statens digitaliseringshøvding: It-leverandører maler skønmalerier af egne evner
- 13 Ny dansk platform vil give borgerne fuld kontrol over egne data
- 12 Sikkerhedsprodukt advarer om 'risk of access hijacking' og 'critical code error' i MobilePay
- 1 Firefox bringer privatlivsbrowser til Android
- Sikkerhedsprodukt advarer om 'risk of access hijacking' og 'critical code error' i MobilePay
- KMD og den omvendte bug bounty
- Statens digitaliseringshøvding: It-leverandører maler skønmalerier af egne evner
- Ny dansk platform vil give borgerne fuld kontrol over egne data
- Google Glass er pludselig tilbage - får opdatering ud af det blå
Pressemeddelelser
Affecto Denmark reaches highest Microsoft Partner level
Affecto Denmark, a leading provider of data-driven solutions, has reached the highest level in the Microsoft partner ecosystem: Managed Partner.
22. jun 13:45
Innovate your business with Affecto's IoT Explorer Kit
Are you unsure if Internet of Things fits your business strategy?
31. maj 2017
Big Data Lake Summit: Fast and Trusted Insights
If you want to outpace, outsmart and outperform your competition in a digital world, you need trusted data that can be turned into actionable business insights at speed.
24. apr 2017
