O sa incep eu cu cele simple

1) 9! / (3! * 3! * 3!) = 1680
sau
Comb(6,3) * Comb(9,3) = (tot) 1680
Comb(6,3) = in cate moduri poti interclasa 3 a-uri cu 3 b-uri
Comb(9,3) = in cate moduri poti interclasa un sir fixat de 3 a-uri + 3 b-uri cu un sir format din 3 c-uri

2) Fibonacci(n)  (considerand Fibonacci(0) = Fibonacci(1) = 1)

Le urez si eu celor 4 concurenti mult succes si medalii cat mai stralucitoare, caci au muncit mult pentru a ajunge la IOI.

As a side note, puteti citi aici (http://sirupsen.com/my-journey-to-the-international-olympiad-in-informatics/) cum se putea ajunge la IOI 2012 daca erati elevi in Danemarca

Hm... din pacate, email-ul cu anuntul datei schimbate a rundei 4 mi-a ajuns in Spam (pe gmail). Mi-ar fi placut sa particip, dar, intrucat nu verific site-ul suficient de des (si cum email-ul de la infoarena mi-a ajuns in spam), se pare ca am ratat data desfasurarii rundei (eu observasem doar data initiala, de 25 martie).

A fost un concurs frumos, cu probleme interesante (abia astept sa citesc descrierea solutiei la kgraf, caci ce am eu, desi polinomial, depaseste cu mult timpul de executie ).

De asemenea, mi se pare ca ati facut o treaba foarte buna cu doar 5 probleme distincte (la toate grupele). Eu cred ca ar fi bine daca ati mentine aceasta situatie si pe viitor, din urmatoarele motive:
1) probleme mai putine per runda inseamna mai putina munca pt echipa infoarena sau inseamna ca problemele pregatite pot fi testate mai bine, eventual de mai multe persoane (si stiti cat de mult e de munca cu pregatirea serioasa a unei probleme)
2) probleme mai putine per runda inseamna ca aceeasi problema ajunge la mai multe grupe de varsta si sunt mai multi oameni care vor incerca sa o rezolve ; in plus, apare si o mini-posibilitate de a compara (cel putin partial) capabilitatile concurentilor din grupe diferite (chiar daca nu in mod "oficial")

Ok, no problem. Referitor la schimbarea din feedback, nu prea aveam cum sa ne dam seama ce s-a schimbat in detailed feedback (ca feedback-ul initial a disparut o data cu reevaluarea - eu am crezut la inceput ca s-a schimbat rezultatul sursei mele la al 2-lea test din feedback). In acest caz. poate ca o solutie mai buna era, pur si simplu, sa adaugati si testul 13 la feedback (fara sa scoateti testul 6 - after all, unii dintre noi deja primisem feedback pe el).

Referitor la re-evaluari din astea in timpul concursului.. Poate ar fi bine sa va ganditi la o modalitate prin care concurentii sa afle mai usor ca s-a efectuat o re-evaluare (pe mine m-a deranjat destul de mult faptul ca, cu 5 minute inainte sa se termine concursul, ma uit pe submit-ul meu la "Egal" si vad ca al doilea test de feedback ia MLE, cand inainte mergea perfect).

Si ca sa fie o critica constructiva, o varianta care cred eu ar fi foarte simpla este ca in monitorul de evaluare, pe langa mesajul cu "rezultate partiale disponibile", sa fie afisat si scorul efectiv de la aceste rezultate partiale (astfel, s-ar fi observat mult mai repede ca in loc de 10p de la evaluarea partiala initiala, acum obtineam 5p).

In exemplu raspunsul este 4 si sunt date si cele 4 subsecvente care au numar egal de 0 si 1. Insa mai exista si subsecventa 1001, care nu este considerata ca solutie in exemplu. Asadar, raspunsul ar trebui sa fie (cel putin) 5.

1) Ciclul final obtinut trebuie sa contina toate cele N noduri ale arborelui ?


2) Este corect ca, in urma operatiilor efectuate. sa obtinem un ciclu format din K<N noduri, iar restul de noduri (N-K) sa ramana neconectate (adica fara nicio muchie adiacenta) ?

O sa indraznesc sa-mi arunc si eu o parere asupra acestui subiect, desi e probabil dintr-o perspectiva care nu o sa-l interesze prea tare pe autorul topic-ului.

Experienta mea referitoare la universitati din tara -vs- universitati din afara este destul de restransa, si se reduce la urmatoarele: 1) in tara am absolvit fac. de automatica & calculatoare, din poli (bucuresti), apoi am facut tot acolo masteratul si doctoratul ; acum sunt asistent in cadrul acestei facultati si stiu cum merg lucrurile si "dinauntru" - adica am atat perspectiva studentului, cat si cea a cadrului didactic ; 2) pe perioada doctoratului am fost la vreo 3 stagii de cercetare la Univ. Tehnica din Delft (in Olanda), care au durat fiecare 2-3 saptamani (TU Delft este o universitate foarte tare in domeniul sistemelor distribuite, in special a sistemelor peer-to-peer) - aici am interactionat cu oameni care se ocupa toata ziua (aproape) de cercetare - doctoranzi, post-docs, assistant professors (cu profesori de grad mai ridicat am inetractionat mai rar).

Asadar, experienta mea este relevanta, mai degraba, doar in cazul in care, dupa absolvirea facultatii, te-ar interesa sa faci research si nu sa te angajezi in industrie. La TU Delft, in grupul cu care am colaborat, aproape toti lucrau cel putin 8 ore pe zi in cadrul a diverse proiecte de cercetare. Aveau intalniri periodice, discutau idei, rezultate, chiar si articole publicate recent in conferinte de top. Mediul este excelent pentru a face research in domeniile de interes ale acelui grup (sisteme p2p in special). De asemenea, aproape toti doctoranzii / post-doc-ii absolvisera universitati din afara Olandei (Rusia, China, India, Brazilia, Italia, etc.). O parte din ei trebuiau si sa tina ore (cursuri, seminarii, laboratoare) cateva ore pe saptamana. Insa faceau acest lucru doar pentru ca trebuia, si nu pentru ca aveau vreo pasiune pentru a preda - ceea ce ii interesa pe toti era partea de research. De asemenea, ideea de baza in partea de predare era ca studentii sa ramana cu cateva principii fundamentale de la fiecare curs (aceste principii erau explicate atat teoretic, cat si practic, prin intermediul unor exercitii/experimente/implementari, etc.)

In Romania se misca si aici lucrurile in domeniul cercetarii. Se colaboreaza mai mult cu universitati din afara (proiecte internationale cu mai multi parteneri) si invatam si noi de la ceilalti [ deoarece universitatile din afara au o experienta mult mai bogata in ceea ce priveste producerea de rezultate care sa poata fi publicate la conferinte sau in reviste de top ]. Numarul de ore de predare care trebuie tinute in Romania este, insa, mai mare decat la universitatile din afara, ceea ce reduce timpul dedicat cercetarii.

Ca sa nu divaghez prea mult si sa ma incadrez in subiect, parerea mea este ca, d.p.d.v. strict al cunostintelor, nu inveti mai mult la universitati din afara decat la universitati din Romania (exista chiar situatia inversa ; unele cursuri care se predau in poli studentilor de anii 1-4 sunt predate la master la alte universitati). Tot parerea mea este ca, daca dupa absolvirea facultatii te intereseaza sa faci si un doctorat (deci sa apuci o directie de cercetare), atunci nu esti dezavantajat daca faci universitatea in tara -- dar ar fi bine sa obtii note mari, deoarece o sa conteze (notele arata, printre altele, ca esti dispus sa faci ceea ce este necesar, nu doar ceea ce ai tu chef ; de asemenea, sunt folosite si pentru a estima in primii cati % esti din promotia ta - aceasta fiind o metrica care se ia in considerare ; de asemenea, vei avea nevoie de scrisori de recomandare din partea profesorilor din universitate, iar daca nu ai note bune - macar la cursurile lor - acestia nu o sa-ti scrie). Avantajul unei universitati din afara in acest caz este ca poti colabora cu un grup de cercetare puternic inca din timpul studentiei (colaborarea cu studentii pe teme de cercetare este mai redusa in Romania ; eu lucrez cu studenti pe niste subiecte interesante, insa abia cand acestia ajung in ultimul an si trebuie sa-si realizeze proiectul de licenta).

In ceea ce priveste angajarea in industrie, dupa cum am spus deja, nu consider ca ai fi dezavantajat din punctul de vedere strict al cunostintelor dobandite in cazul in care ai urma o universitate in tara. S-ar putea, insa, asa cum s-a mai mentionat deja, ca daca ai absolvit o universitate de top din afara (de ex., MIT), aceasta sa iti ofere un avantaj, macar in cazul in care ar trebui sa aleaga intre tine si cineva care nu s-a dovedit mult mai bun decat tine in urma interviurilor.

In saptamana 7-11 decembrie, Mihai Patrascu va sustine 2 prezentari (sub forma de cursuri), una la Universitatea Politehnica din Bucuresti (UPB), si una la Universitatea din Bucuresti (UNIBUC). Sunteti invitati sa participati la cele 2 prezentari daca sunteti interesati de subiectele abordate, de alte subiecte conexe, sau pur si simplu pentru a-l vedea pe Mihai la treaba (care sigur va va trezi interesul pentru informatica teoretica in general, si pentru subiectele abordate in cursuri, in particular). Intrarea este libera. Titlurile si rezumatele celor 2 prezentari le gasiti mai jos. Iar in caz ca nu ati auzit de Mihai Patrascu pana acum  , aveti la sfarsitul post-ului si o (foarte) scurta biografie a sa (alternativ, puteti sa-l cautati pe Google  ).


1) Talk UPB

Cand: luni, 7 decembrie 2009, ora 18:00

Unde: Facultatea de Automatica si Calculatoare, sala EC 101

Titlu: Funcţii de hash tabulare

Rezumat: Implementarea tabelelor de hash folosind căutare liniară (linear
probing) este mai eficientă decât alte implementări dacă funcţia de
hash este suficient de alteatoare. Din păcate, linear probing se
comportă foarte prost în conjuncţie cu funcţiile de hash bazate pe
înmulţire (cele mai folosite în practică), şi ca atare, acest algoritm
este deseori evitat.

Voi descrie o funcţie de hash foarte simplă, care este la fel de
rapidă ca înmulţirea pe procesoarele actuale, dar se bazează pe
indexarea în tabele precalculate. O analiză matematică ne demonstrează
că această funcţie garantează timp de rulare constant pentru tabelele
de hash.



2) Talk UNIBUC

Cand: vineri, 11 decembrie 2009, ora va fi stabilita in curand

Unde: in cadrul UNIBUC (locatia exacta va fi stabilita in curand)

Titlu: Rezultate negative pentru structuri de date

Rezumat: Cum demonstrăm că anumite rezultate algoritmice sunt imposibil de
obţinut? Spre exemplu, cum demonstrăm că nu există nicio structură de
date cu spațiu liniar care poate suporta range queries în timp
constant? În acest curs, voi descrie o demonstrație completă a acestui
rezultat, trecând prin mai mulți pași simpli, dar interesanți.




Biografie Mihai Patrascu:

Mihai Pătraşcu lucrează în prezent în departamentul de cercetare al
AT&T (în New York). Domeniul lui de cercetare este informatica
teoretică (structuri de date, algoritmi, lower bounds). În trecut, a
efectuat studiile universitare (2006) și doctorale (2008) la MIT,
urmate de un an în laboratorul IBM din San Jose, California.
Mihai a obţinut câteva premii de cercetare, cât şi mai multe medalii
la olimpiadele internaţionale de informatică (în timpul liceului).

1) Cuvintele sunt formate doar din litere mici ale alfabetului ? ('a'-'z')

2) Un cuvant poate contine acelasi caracter de mai mute ori ?

3) 2 cuvinte din dictionar se considera diferite, chiar daca sunt scrise la fel (sau, eventual, unul e o permutare a celuilalt) ?

Si mie mi-au placut problemele (nu le-am citit decat pe cele de la grupa Studenti). S-a simtit clar ca au fost mai usoare decat cele de la runda anterioara, dar a fost fun sa le implementez. Eu am calculat numarul de intersectii de segmente la Patrulatere, in O(N^3), deci se poate rezolva problema de 100p si asa (folosind un mic smen care e necesar adesea pt a obtine o complexitate buna la diverse probleme de dinamica cu puncte in plan).

Sunt de parere ca organizatorii au facut o treaba excelenta (la toate cele 3 runde), din toate punctele de vedere (calitatea problemelor, evaluare pe perioada concursului, imbunatatirea feedback-ului la evaluare -- mi-a placut foarte mult faptul ca s-au putut vedea niste rezultate partiale la problema Patrulatere). Asadar, felicitari! si va urez succes la organizarea rundei finale (care, fiind on-site, este mult mai complicat de organizat).

Dupa cum am scris intr-un post anterior, rezultatul echipelor din UPB a fost afectat de terminarea prematura a concursului pe infoarena. Din acest motiv, maine va avea loc pe TJU un mini-baraj pentru echipele clasate pe locurile 3 si 4, pentru a fi selectata si a 3-a echipa ce va reprezenta UPB la etapa regionala ACM ICPC (primele 2 echipe s-au calificat detasat). Adresa concursului este: UPB - ACM ICPC Mini-Qualification Contest. Cei interesati pot participa si la acest concurs.  Diferenta fata de concursul de pe infoarena este ca problemele sunt selectate din arhiva TJU, nefiind probleme noi. Ora de inceput a concursului este 12:00 (duminica, 14 septembrie).

Intr-adevar, concursul a durat doar 5h 40. Se pare ca exista o desincronizare intre ora reala si ora sistemului pe care era setat concursul (care a considerat ca s-a ajuns la ora 16:00 mai devreme). Problema a fost observata imediat si s-a incercat extinderea suplimentara a duratei concursului, pana la ora "reala" 16:00. Din pacate, site-ul a devenit inaccesibil imediat dupa identificarea acestei probleme si nici la 30 min dupa ora 15:40 nu s-a putut realiza modificarea dorita.

Imi cer scuze pentru toate problemele aparute pe durata acestui concurs (au fost multe si variate ). Dupa cum vad eu lucrurile, Infoarena este un proiect in continua dezvoltare si anumite aspecte vor trebui, probabil, imbunatatite candva. Asa ca daca sunteti interesati de partea de development infoarena, luati legatura cu Cristi.

Partea cea mai neplacuta a acestui final "abrupt" este ca a afectat rezultatul echipelor din UPB care participau "oficial" la concurs. Una dintre echipe mi-a trimis o sursa de 100p, pe care nu au mai apucat sa o trimita, deoarece concursul s-a terminat prea devreme. Cu acea 100p, ar fi fost 2 echipe din UPB la egalitate, cu cate 4 probleme rezolvate (asta daca nu cumva echipa care a ajuns la 4 probleme in timpul concursului nu ar fi ajuns, intre timp, la a 5-a problema) -- sursa este aproape identica cu ce au trimis in timpul concursului (si nu lua 100p atunci), realizand doar modificari minore.

nu prea inteleg intrebarea.

in orice caz, in cazul problemei, fiecare valoare de pe cate o pozitie este o cifra in baza B. nu stiu daca asta are vreo legatura cu intrebarea pusa, dar m-am gandit ca poate nu e clar acest aspect.

asadar, prin concatenare se intelege interpretarea ca numar in baza B a numarului format din "cifrele" de pe pozitiile x, x+1, ..., y .
restul cerut, insa, este un numar "normal" in baza 10.

Scrie in enunt, la date de intrare: "Cuvintele nu sunt neaparat distincte".

Nu, P nu este neaparat un numar prim.

O mica clarificare: Doua secvente se considera distincte daca reprezinta portiuni diferite ale sirului dat. Pot exista subsecvente cu aceeasi "valoare" (de ex: aabaabaab), dar localizate in portiuni diferite (nu neaparat complet disjuncte) ale sirului -- in acest caz, ele se vor considera diferite.

Datorita multiplelor probleme aparute (evaluator care a pornit prea tarziu, perioada in care site-ul a fost accesat greu, test gresit la una dintre probleme), am decis sa extindem durata concursului la 6 ore. Consideram ca este solutia cea mai corecta fata de concurenti.

Mult succes in continuare !

Well.. se pare, intr-adevar, ca testul 19 era gresit. L-am modificat si am pornit reevaluarea tuturor surselor trimise la problema "pp".

Imi cer scuze pt deranjul cauzat. Mi-am dat seama prea tarziu de un bug micut pe care il aveam in sursa "oficiala".

Mult succes in continuare.

Te referi la cazul N=0, nu ?  In acest caz, da: arborele trebuie sa contina cel putin nodul radacina.

O clarificare: daca N=0 de la inceput, atunci primul jucator pierde jocul.

Pt cazul N=0, cele 2 afirmatii referitoare la cine castiga jocul nu erau chiar echivalente, asa ca aceasta clarificare este necesara.

Pare ca evaluarea merge acum.

da

nu trebuie afisate neaparat in ordine crescatoare