infoarena

S-a terminat Runda Finala (http://infoarena.ro/algoritmiada-2010/runda-finala) a concursului Algoritmiada 2010 (http://infoarena.ro/algoritmiada-2010/). Felicitari castigatorilor (http://infoarena.ro/algoritmiada-2010/clasament/runda-finala/5-8)!

Asteptam sugestiile si parerile voastre atat despre finala, cat si despre intreaga editie din acest an. In zilele urmatoare, finalistii vor primi prin email un chestionar de feedback pe care ii rugam sa-l completeze cu atentie. Astfel vom putea organiza editiile viitoare mai pe placul vostru!

Vom completa in curand si sectiunea de poze. Pana atunci puteti vedea pe s-a intamplat la Iasi pe pagina noastra de facebook (http://www.facebook.com/#!/infoarena?v=wall&ref=ts).

Au fost probleme frumoase runda asta, iar pentru asta meritati Felicitari!!!
Cand puneti problemele in arhiva ?  :-'

Frumoase problemele ! Mi-au placut in special datorita faptului ca admiteau mai multe abordari. La 11-12 problema produs mi se pare foarte interesanta, pacat ca nu a fost data si la 9-10 .  :P
Overall Algoritmiada e fara indoiala unul dintre cele mai importante concursuri pentru elevi, pe langa OJI si ONI. Keep it up !  :thumbup:

PS : Cand se vor updata ratingurile ?

Le-am updatat acum. :)

Felicitari pentru organizarea finalei, dupa parerea mea cel mai reusit concurs din anul acesta! Probleme frumoase, conditii bune, activitati din plin, premii mari si nu in ultimul rand distractie.
Nota 10 pentru echipa Infoarena!  :winner1:

Subscriu la ce a spus Cezar. A fost o experienţă super tare. :D

Nu se putea mai reusita(bine...singurul lucru mai putin reusit era ca ne-am plimbat cam mult prin Iasi :-')
Si daca dura mai mult... :shock:

Chiar a fost foarte tare finala. Distracție, probleme faine, condiții faine. Am avut activități din plin, și chiar și vremea a ținut cu noi :D. Felicitări echipei Infoarena. Ceea ce mi nu mi s-a părut tare a fost evaluarea live (ce-i drept am și avut o poziție din care nu vedeam mai nimic).


Când te-ai plimbat prin Iași, că singurele plimbări pe care le-am făcut au fost cămin - cantină - facultatea unde am dat proba. Plus o plimbare cu tramvaiul până la terenul de fotbal și până la clubul de biliard.

eu cel putin am facut un inceput de febra musculara :yahoo:
dar cred ca a meritat...conditiile au fost exelente

Conditiile de cazare foarte bune, setul de probleme bine ales, distractia de dupa proba si premiile mari au facut ca Algoritmiada sa fie dupa parerea mea cel mai fain concurs din ultimii ani.
Se pare ca echipa infoarena s-a ocupat cum trebuie de toate detaliile ( chiar si in ceea ce priveste vremea aparent :) ) si pentru asta merita felicitari.

keep up the good work  =D>

Va fi un scris un articol cu solutii ?   :roll:

Am creat articolul cu solutii (http://infoarena.ro/algoritmiada-2010/runda-finala/solutii). Ii invitam pe membrii comunitatii care au rezolvat corect problemele sa ne ajute la redactarea articolului. :thumbup:

au luat multi 100 pe probleme de ce nu scrie nimeni?

Imi poate da cineva hint-uri la problemele de a 9-a

Diagonala -> Dacă muți linia i (1 ≤ i ≤ N) cu i elemente mai la dreapta, respectiv mai la stânga, problema se reduce la determinarea celei mai lungi secvențe de 1 consecutivi de pe o coloană. Aste se poate rezolva cu 2 deque-uri, unu pentru capătul din stânga, unul pentru capătul din dreapta.

Inversări -> Ții o dinamică D[ i ][ j ] -> numărul de inversări din secvența de lungime i care are ca ultim element, elementul de pe poziția j. D[ i ][ j ] = D[ i-1 ][ j-1 ] + numărul de elemente din secvența (j-i+1, j) care sunt mai mari decât elementul de pe poziția j. Acest număr se poate calcula tot printr-o dinamică. Odată calculată matricea vom putea răspunde la query-uri în O(1).

Lkperm -> Consideri F(N) -> numărul de permutări cu N elemente care respectă proprietatea din enunț. La pasul actual încercăm să plasăm elementul maxim. Dacă îl plasăm pe prima poziție, el va afecta o singură secvență de lungime L => F(N-1) posibilități, dacă îl plasăm pe a doua poziție, el va afecta 2 secvențe de lungime L, iar pe prima poziție putem pune orice element în afară de cel actual => (N-1)F(N-2) posibilități,..., dacă îl plasăm pe a K-a poziție pe primele K-1 poziții putem așeza orice elemente => (N-1)(N-2)...(N-K+1)F(N-K) posibilități. Deci, în total, F(N) = F(N-1)+(N-1)(F(N-2) + (N-1)(N-2)F(N-3) +...+ (N-1)(N-2)...(N-K+1)F(N-K). Evident, dacă N < L, atunci F(N) = N!, iar dacă N < 1, F(N) = 0.
Această soluție obține 40 de puncte, pentru că are complexitatea O(N*K). Formula se poate exprima în funcție de doar 2 termeni.

Multumesc mult. Poti sa-mi explici mai detaliat la diagonala cum folosesti cele 2 deque-uri?

@wefgef, nu prea fac treaba membrii infoarena, s-a terminat concursul de ceva vreme, i-ati cazat pe la finala le-ati dat premii da nu au scris nimic la solutii :). Data viitoare dati-le premii doar dupa ce scriu solutia la problemele pe care le-au rezolvat de 100.

Acum nu prea are timp niciun membru care luat premiu ca urmeaza tabara a doua de pregatire.
Si nu e nimeni asa de fraier sa "iroseasca" timp cu asta :)

Nu cred că ești fraier dacă scri un articol.
Cât timp vrei să iei, trebuie să și dai ceva în schimb.

Ideea este că voi ține un deque pentru limitele din stânga sortat crescător și unu pentru limitele din dreapta sortat descrescător. În momentul în care introduci un interval nou, ai grijă ca cele doua deque-uri să respecte proprietățile menționate anterior. Acum, este posibil ca primul element din deque-ul pentru marginile din stânga să fie mai mare decât primul element din deque-ul pentru marginile din dreapta, caz în care vom elimina primele elemente din cele doua deque-uri până când primul element din stânga este mai mic sau egal cu primul element din dreapta.

Când citești un articol cu soluții te bucuri de munca "fraierului" care l-a scris.

Misu, de ce nu incerci sa redactezi solutiile la cateva probleme?

@Cosmin: Nici macar solutiile de anul trecut nu au fost terminate :P.

De ce să ştie şi alţii ce ştii tu, nu? Nu e nicio muncă degeaba, e ceva ce poţi face într-o comunitate.

Ar trebui să avem (mai multe) activităţi prin şcoală ca plantarea pomilor. :)

Scriu eu solutiile la a IX-a si la clasele mai mici daca reusesc sa rezolv problemele

În weekend am să încerc să redactez soluțiile ca câteva probleme pe care le-am rezolvat. :)

A mai rămas problema Dsip pe care, aparent, a rezolvat-o doar autorul.

Am completat articolul cu soluții, dar s-ar putea să mai fie ceva nevoie de niște retușuri :). De asemenea, au mai rămas două probleme de la gimnaziu pe care nu am apucat să le rezolv.

Super, bravo =D&gt;

Hai cu + la karma :yahoo:

Alta chestie e ca oamenii care fac chestii de genul asta ar trebui recunoscuti. In fiecare articol cu solutii am putea pune la probleme de acum incolo numele celui care a scris solutia respectiva.

Felicitări, o treabă excelentă !  =D&gt;