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

Tillykke med Danmarksmesterskabet og andenpladsen i den nordiske turnering.

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

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?

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

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?

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

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