Problema saptamanii curente a fost rezolvata de 13 cititori. Ea nu e asa dificila ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.

Rezolvitori:

Andrei Grigorean, Radu Berinde, Andrei-Marius Teodorescu, Delia David, Andrei Dragus, Adrian Carcu, Ovidiu Gheorghioiu, Adrian Vladu, George Nachman, Laura Draghici, Paul Dan Baltescu, Mihai Feier si Mihai Calancea.

Solutie:
Notam umem sirul de U pozitii cu memoria neinitializata. Cum avem nevoie de operatii in timp constant am putea tine 1 sau 0 pe pozitia v din umem daca elementul v este in set sau nu. Din pacate memoria nu este initializata si astfel pot exista deja 0 si 1 prin sir care sa ne pacaleasca.

Initializarea memoriei ajunge, in cazul unor algoritmi eficienti, sa incetineasca timpul total de executie. Saptamana asta incercam sa gasim o metoda ce evita aceasta problema.

Gasiti o structura de date ce reprezinta o submultime a multimii {0, 1, ... , U - 1}. Operatiile de initializare, adaugare si verificare a incluziunii trebuie sa se execute in timp constant in cazul cel mai nefavorabil (daca am cere timp constant pe cazul mediu, o solutie este sa folosim un hash table). Aveti la dispozitie o zona de memorie continua in care incap U intregi ce nu e initializata, deci contine valori oarecare. Puteti folosi memorie suplimentara O(N), unde N este numarul de intregi ce vor fi adaugati in multime.

Ca de obicei puteti trimite solutii sau propuneri de probleme pe adresa cosminn at gmail.com

Saptamana asta am avut o problema de matematica, dar care avea nevoie de cunostinte elementare.

Rezolvitori:
Dumitru Daniliuc, Andrei Dragus, Mihai Damaschin, Adrian Vladu si Andrei Marius Teodorescu.

Solutie:
Proiectam segmentele pe Ox si pe Oy. Suma lungimilor proiectiilor va fi mai mare sau egala cu 18. Asta inseamna ca cel putin una dintre cele doua sume a lungimilor proiectiilor verticale sau a lungimilor proiectiilor orizontale va fi mai mare sau egala cu 9. Presupunem fara a restrange suma aceasta este realizata pe axa Ox.

In cazul in care o suma este strict mai mare decat 9, vom avea un punct pe Ox unde au fost proiectate puncte de pe 10 sau mai multe segmente si putem astfel duce prin acel punct o dreapta paralela cu Oy ce va intersecta cel putin 10 segmente.

Daca stiti probleme interesante care s-ar potrivi la "Problema saptamanii" va rog sa mi le trimiteti pe email. Problema saptamanii ar trebui sa nu fie foarte cunoscuta, sa aiba o rezolvare ingenioasa dar care nu are multi pasi si prefer sa fie legata cat de cat cu programarea, dar poate fi si de matematica.

Continuam cu urmatoarea problema:

Patratul [0, 1] x [0, 1] contine niste segmente cu suma lungimilor egala cu 18. Sa se demonstreze ca exista o dreapta ce intersecteaza cel putin 10 din aceste segmente.

Puteti trimite solutii sau propuneri de probleme la adresa cosminn at gmail.com

Am aflat problema anul trecut de la Mihai Patrascu. Ea e pe stilul multor intrebari din interviuri de joburi de programare. Are aplicatii in multe contexte cum ar fi in baze de date unde vrem sa detectam obiecte duplicate, pentru motoare de cautare unde vrem sa detectam pagini ce se repeta in index sau la monitorizarea traficului pe retele unde se incearca detectarea de anomalii. Ea a fost abordabila, fiind solutionata de 16 cititori.

Rezolvitori:
Dumitru Daniliuc, Andrei Grigorean, Tiberiu Savin, Andrei Dragus, Alex Mosoi, Marius Pungaru, Adrian Vladu, Marius Andrei, Daniel Dumitran, Marius Dragus, Andrei Marius Teodorescu, Laura Draghici, Delia David, Adrian Airinei, Armand Rotaru si Stefan Istrate.

Solutie:
Fie x = [sqrt n]. Tinem un sir de x pozitii F[i] cu frecventele elementelor pe intervalul [i * x + 1, (i + 1) * x]. Din principiul cutiei rezulta ca un interval va avea mai mult de x elemente in el. Prin o parcurgere al sirului aflam un astfel de interval. Cu o a doua parcurgere aflam frecventele exacte ale elementelor din intervalul respectiv folosind un sir de dimensiune x. Am determinat astfel un element duplicat folosind doua parcurgeri si memorie O(sqrt(n) log n) biti.

Continuam cu alta problema ceva mai simpla.

Se da un stream pe care il putem citi de un numar constant de ori. El contine n + 1 numere intregi de la 1 la n. Evident unul sau mai multe elemente apar de mai multe ori. Se cere sa se gaseasca un algoritm care gaseste un element duplicat in stream, parcurgand streamul de un numar constant de ori si folosind memorie mai mica decat O(n) biti. Un stream are metodele bool hasNext() si int getNext(), si e o abstractizare a unui set de date ce poate fi citit secvential.

Puteti trimite solutiile pe adresa cosminn at gmail.com

Problema Interclasare a dat ceva bataie de cap membrilor comunitatii infoarena. Ma asteptam sa stie lumea ceva mai bine ce inseamna sortare stabila sau memorie suplimentara.

Solutie:

Revenim dupa o pauza considerabila cu problema saptamanii. Problema s-a dat la un interviu de job in Cluj.

Se da un sir A de n + m numere intregi. Numerele de la 1 la n sunt in ordine crescatoare si numerele de la n + 1 la n + m sunt si ele in ordine crescatoare. Se cere sa se sorteze sirul in ordine crescatoare. Algoritmul trebuie sa foloseasca memorie suplimentara constanta, ordinea numerelor sa fie stabila, adica oricare doua numere egale din sir sa apara in aceeasi ordine dupa ce sirul a fost sortat, iar complexitatea algoritmului trebuie sa fie mai buna de O((n+m)^2).

Trimiteti solutii la adresa cosminn at gmail.com

Anul 2010 a marcat prima ediţie e Olimpiadei Judeţene de Informatică în care s-a renunţat la evaluarea sub mediile Borland, acestea fiind înlocuite de FreePascal şi MinGW. Suntem bucuroşi că am putut contribui şi noi la această binevenită şi mult aşteptată schimbare, echipa infoarena fiind responsabilă de alcătuirea noului pachet OJI. Dacă în privinţa limbajului Pascal situaţia părea destul de clară, nu acelaşi lucru se poate spune şi despre C/C++. Între cele două pachete importante de compilatoare, MinGW şi Visual C++, am ales MinGW-ul, în primul rând datorită legăturii mai strânse cu GCC. În privinţa IDE-urilor, decizia nu a fost atât de uşor de luat. Puteţi vedea pe pagina dedicată alternativelor mai multe detalii. Până la urmă am ales MinGW Developer Studio în dauna Code::Blocks şi Dev-CPP.

Cine isi mai aduce aminte de preONI? Concursul cu un inceput modest, avand 2 grupe si 2 runde in 2004, a crescut cu anii intr-unul dintre cele mai importante concursuri de informatica, avand 4 grupe si 4 runde si finala cu premii. Dar oricat de mic sau mare ar fi fost, preONI a fost cu siguranta concursul cu cele mai interesante probleme. Stramosul Algortmiadei de astazi, si-a lasat puternic amprenta asupra multor concurenti ce se pregateau atunci pentru ONI. Marturisim ca si noi, membrii mai tineri ai echipei infoarena, ne-am batut capul serios cu problemele de la preONI si am invatat o multime de lucruri din ele.

Pentru ca cele mai interesante probleme merita sa fie lucrate si studiate, am decis sa facem publice sursele tuturor problemelor propuse la editiile preONI (din 2004 pana in 2008). Speram ca veti avea ce sa invatati din ele si ca va vor fi de folos. Spor la treaba.