Intrerupatoarele din fisierul de intrare sunt plasate in camere distincte.

Xor max-marfa ideea cu trie-ul
tri2 - problema frumoasa care imbina geometria cu algoritmii
gard-dinamica super tare, care se optimizeaza frumos
telegraf-un exemplu mai aparte de dinamica, idee foarte neevidenta
sortnet-pentru solutia cu codul lui gray foarte originala

Tin minte ca am cumparat aceasta carte de la Teora acum cativa ani. Daca vrei poti sa incerci www.teora.ro.

Va aparea un articol pe http://info.devnet.ro cu solutiile de la problemele de la finala.

Aici puteţi discuta despre problema Secventa Farey.

Exista mai multe posibilitati de a rezolva problema. Eu am rezolvat-o in O(3^(N / 2) + 2^N).

Complexitatea solutiei mele e O(N log LMAX + M log N * LMAX), unde N e lungimea vectorului, M e numarul de cuvinte si LMAX e lungimea maxima a unui cuvant. Mie imi intra fara nici o problema in timp...

Cand accesezi un element dintr-o matrice mare, timpul nu este tocmai neglijabil. La multe probleme de pe infoarena trebuie sa optimizezi destul de mult algoritmul pentru ca sa iei punctaj maxim:)

Aici puteţi discuta despre problema Caraibe.

Pai daca iei 0 puncte nu e clar ca e gresit? Poate doresti sa iti spunem ce ai gresit:)

Nu cred ca la aceasta problema se poate lua punctajul maxim cu o rezolvare incorecta... Totodata, arhiva de probleme nu este tocmai un concurs la care sa fie nevoie de o departajare, deci nu vad nici o problema daca o solutie mai simplista va lua 60-70 de puncte. Totusi, daca doriti sa rezolvati problemele, trebuie sa atingeti 100 de puncte, nu mai putin:).

Nu cred ca scopul principal pentru care ne-am bagat in acest proiect este castigul. Cred ca mult mai mult au de castigat utilizatorii obisnuiti decat noi. Este adevarat ca noi am putea vedea sursele. Uite, acum scrie asta aici:). Dar crezi ca sta unul din noi sa se uita pe sursele care le trimit concurentii? Deci pana la urma sursele lor nu sunt vazute. Nu uita ca totusi cel care ne trimite noua sursele sunt utilizatorii, nu le luam noi din creierul lor. Cand trimite o sursa utilizatorul da acces cel putin evaluatorului la ea...

Spui ca daca am publica sursele utilizatorilor am avea doar de pierdut. Ce am avea de pierdut, ca eu nu vad... Consider ca nu se realizeaza asta pentru ca nu cred ca ar putea fi util, si nu am vazut nici un alt site unde sa se foloseasca. Clasamentul de la arhiva este pur orientativ, nu e o competitie acolo. La orice site propunatorii de probleme isi rezolva si problemele lor... nu mai dau exemple acum. Eu nu vad totusi cum sa iti evaluam noi sursa fara ca tu sa nu ne dai acces la ea... In plus e normal ca sursele sa fie stocate undeva. Uite, se schimba evaluatorul, se repara un test... trebuie recorectat.

Clasamentul de la arhiva este pur si simplu orientativ, acolo nu e nici un fel de competitie. La fel se face un clasament la orice site de pregatire(acm.timus.ru, acm.sgu.ru, etc). Eu nu inteleg ce ar putea insemna un clasament "corect" la arhiva... Nu cred ca cineva dintre membrii infoarena nu au lucrat problemele pe care figureaza ca le-au facut. In plus la majoritatea problemelor de acolo teste se gasesc si pe net, deci oricine are acces la ele.

Am observat in ultimul timp o serie de pareri asemanatoare cu parerea ta. Vad ca in ultimul timp tot mai multi informaticieni sunt preocupati de ce se va intampla cu sursele lor. S-a discutat asta si la ONI, si la baraj fapt pentru care nu s-a mai dat accesul la surse. Eu unul nu am absolut nici un motiv pentru care sa nu las pe cineva sa imi vada sursa. Toata discutia asta mi se pare ca deviaza de la scopul pe care il are orice utilizator la infoarena, si orice olimpic la info. Eu va sfatuiesc sa lucrati problemele si sa lasati gandurile si parerile astea in legatura cu sursele... Chiar nu imi dau seama de ce va intereseaza viitorul surselor voastre.
Tot ce am scris aici este doar parerea mea personala.

Nu se poate zice ca minimul se poate extrage in log N si update-ul tot in logN ? Cine e pasionat si vrea mai mult [ lumea de pe infoarena ] va invata si M log N.

Exista o posibilitate ca sa nu stergi minimul in O(logN) si complexitatea sa fie curat O(m log N)? Complexitatea la dijkstra cu heap nu e de fapt O((n + m) log N)?

Problema 'distante' a fost considerata pb. medie la XI-XII ... era prea usoara pt. sector in forma actuala ...

Eu nu cred ca distante trebuia sa fie mai grea. A fost gandita ca problama usoara, nu ca problema medie si cred ca daca un dikstra cu heap lua 80p sau chiar 100 nu este nici o problema. Bineinteles, sunt multe probleme pentru care putem gasi mai multe solutii, unele elegante altele mai putin elegante, care sa ia punctajul maxim.
Nu stiu daca la clasele 11-12 nivelul ar trebui sa fie cu mult mai dificil decat a fost acum. Nu a luat nimeni 300, si noi am considerat ca este un concurs usor... Probabil ca nivelul de dificultate din viitor nu va fi foarte diferit de runda aceasta.

Nu cred ca punctajele ar trebui sa fie diferite pentru fiecare problema. Gandeste-te cati pot rezolva o problema grea. Asa s-ar ajunge ca la ONI sa iei mentiune lejer cu 70-80 de puncte... ceea ce nu ar fi tocmai placut.
Eu cred ca daca testele sunt bine alese pe fiecare problema departajarea e asa foarte buna. Desi pot fi putine puncte intre locul 1 sau 2 (de exemplu 30 sau 40 de puncte) ele pot face diferenta de la o solutie in O(n log n) la o solutie in O(n), deci asa punctele valoreaza mai mult decat crezi:).

Incearca sa cauti in cartea "Introducere in algoritmi". E publicata la editura Agora, dar casesti si versiunea in engleza pe net. Linkul il poti gasi la http://info.devnet.ro la sectiunea resurse web cred...

Eu nu cred ca publicarea anumitor surse ar fi o idee de proiect pentru viitor. Si asa sursele de la ONI, baraje se mai gasesc si din anii trecuti si se poate invata de acolo. In plus, fiecare isi perfectioneaza implementarea cu cat rezolva mai multe probleme.
Totusi, sunt pentru descrierea anumitor solutii pe forum. In fond, ideea de rezolvare e mult mai importanta decat implementarea in sine.
Nu cred ca afirmatii de tipul "Unii nu ar putea rezista tentatiei sa dea paste sau sa citeasca solutia de pe forum" pot fi argumente pentru publicarea/nepublicarea surselor. Pana la urma, fiecare e liber sa faca ce vrea.

Bineinteles ca functiile care lucreaza cu memoria sunt sigure. Verifica daca vectorul b nu e mai mare cunva decat vectorul a, astfel poti sa scrii peste marginea superioara a lui a. Altceva nu stiu ce ar putea fi...

Incercati sa va uitati pe exemple inainte de a posta. Sunt sigur ca va veti clarifica majoritatea nelamuririlor.

Nu stiu daca am inteles prea bine solutia ta. Merge pe exemplul urmator?

* . . *
. . . .
. . . .

Aici '.' reprezinta o zona ce poate fi acoperita. Daca tu acoperi prima posibilitate, ai:
* \ \ *
. \ \ .
. . . .

Unde '\' reprezinta o zona acoperita. Iata o solutie corecta:

* . . *
/ / \ \
/ / \ \

Vezi ca am pus 2 placi de 2 * 2.

Daca vrei indicatii la problema cauta problema Bugs de la CEOI 2002 parca.