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:

O abordare ar fi sa folosim metoda divide and conquer. Pentru a rezolva subproblema curenta, putem gasi in timp cel mult liniar mediana celor 2 siruri. Astfel vom avea patru secvente A1 A2 B1 B2, unde elementele din A1 si B1 sunt mai mici decat mediana iar elementele din A2 si B2 sunt mai mari decat mediana. Trucul principal din problema este cum putem ajunge din starea A1 A2 B1 B2 in A1 B1 A2 B2 in timp liniar si folosind memorie suplimentara constanta. Pentru asta putem inversa ordinea elementelor din secventa A2 B1 ca sa obtinem o secventa B1' A2' unde B1' e secventa B1 inversata iar A2' e secventa A2 inversata. Apoi putem inversa secventele B1' si A2' pe rand pentru a obtine sirul format din secventele A1 B1 A2 B2. Toate elementele din A2 B2 sunt mai mari decat elementele din A1 B1, deci am obtinut doua subprobleme de lungime (m + n) / 2 similare cu problema initiala. Astfel obtinem un algoritm de complexitate O((n + m) log (n + m)) ce foloseste memorie suplimentara O(log (n + m)). Avem nevoie de memoria suplimentara pentru a tine starea stivei algoritmului recursiv. Pentru a obtine un algoritm ce nu are nevoie de stiva putem sa rezolvam tot timpul probleme si subprobleme ce au dimensiuni egale cu puteri ale lui doi. Alta idee sa parcurgem sirul nostru si sa aplicam trucul anterior fiecaror doua secvente crescatoare consecutive.

E interesant ca problema poate fi rezolvata si in O(n + m) timp si O(1) memorie suplimentara, dar o asemenea rezolvare e mult mai complicata. Daca gasiti o abordare usor de explicat o veti putea publica ca lucrare de cercetare.

Rezolvitori:

Singura rezolvare completa pe ideea de mai sus a fost a lui Cosmin Gheorghe. Andrei Dragus a venit cu o solutie in O((n + m) sqrt(n + m)). Au mai rezolvat problema fara a face pasul de O(log (n + m)) la O(1) memorie Mihai Lazari, Stefan Istrate, Daniel Dumitran si Ionut Fechete.

Probleme de inrudite:

1.(CLRS, interviu) Se dau doua siruri sortate de lungime m si n, sa se determine in O(log (n + m)) timp mediana sirului obtinut prin interclasarea celor doua siruri.

2.(interviu Microsoft) Se da un sir de caractere de dimensiune n, sa se roteasca la dreapta cu k pozitii in timp O(n) si folosind memorie suplimentara O(1). De exemplu pentru "abcdef", n = 6, k = 2 trebuie sa obtinem "efabcd".

3.(interviu Microsoft) Se da un sir de caractere ce contine cuvinte separate prin spatii. Se cere sa se inverseze ordinea cuvintelor din sir in timp liniar si folosind memorie suplimentara constanta. De exemplu "Ana are mere" -> "mere are Ana".

4.(interviu Facebook) Se da un sir de obiecte X ce au chei de valori 0 sau 1. Se cere sa se sorteze stabil sirul de obiecte in complexitate mai buna de O(n^2) folosind memorie suplimentara constanta.

5.(Oni 2004) Sortare cu inversari http://infoarena.ro/problema/invsort

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.

Din păcate ediţia OJI 2010 nu a fost lipsită de incidente. După cum am fost semnalaţi şi pe forum, au existat unele probleme cu citirea folosind streamuri. În plus, faptul că noul standard C++ este aproape gata ne face să ne gândim la schimbarea compilatorului cu o versiune mai nouă. În acest moment, nu există versiune stabilă mai veche de 4.4 (şi mai nouă de 3.4). Noi nu am reuşit să facem MinGW Developer Studio sau Dev-CPP să meargă cu noile compilatoare, şi astfel singura alternativă rămasă este Code::Blocks. Valentin Stanciu a făcut un nou kit de OJI pe care îl puteţi descărca de aici. Nu am avut timp să testăm prea mult pachetul, aşa că vă rugăm pe voi să o faceţi şi să ne raportaţi problemele întâmpinate. Nu vă recomandăm să aveţi instalată altă versiune de MinGW, deoarece kitul adaugă în PATH noua instalare şi s-ar putea să existe conflicte. Totodată, vă aducem la cunoştinţă faptul că librăriile C++ au fost restructurate, una dintre cele mai importante schimbări fiind renunţarea la o parte dintre librariile deprecated <fstream.h> şi <iostream.h>.

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.

Zilele acestea va avea loc Think Online, un proiect dedicat tinerilor interesaţi de mediul de afaceri online. Pentru că aveţi cunoştinţe solide de algoritmică şi sunteţi programatori talentaţi, ne-am gândit că v-ar ajuta să aruncaţi un ochi şi la partea de business din domeniu.

 
Iată mesajul organizatorilor:

 
Business Club te invită în perioada 19-23 Aprilie să participi la proiectul Think Online. Într-un moment critic al economiei, domeniul afacerilor pe Internet devine unul din ce în ce mai atrăgător pentru antreprenori. Think Online, cel mai nou proiect marca Business Club, este o şcoală de antreprenoriat care va pregăti un număr de studenţi pentru a îşi deschide o afacere on-line. Ne adresăm studenţilor sau masteranzilor care sunt interesaţi de domeniul acesta, care şi-au deschis o afacere/site sau care au de gând să facă acest lucru în viitorul apropriat. Studii de caz, workshop-uri, simulări de management, networking şi un concurs inedit de idei, totul într-o atmosferă plăcută şi optimă pentru a genera idei de succes. Proiectul va avea loc la Bucharest Hubb, primul club de work&fun din România dedicat antreprenorilor online.

Participând la eveniment, vei avea ocazia să întâlneşti oameni interesaţi de afaceri online, să îţi formezi o echipă şi să creezi un plan de afaceri sub îndrumarea celor mai de succes antreprenori. Vei cunoaşte investitori, vei face networking, vei învăţa de la oameni care au o experienţă bogată în start-up-uri. Vei invăţa cum să prezinţi un pitch unui investitor şi vei primi feedback. Dar, cel mai important, dacă planul de afaceri pe care îl vei dezvolta în cadrul proiectului va fi unul atractiv, vei avea ocazia să primeşti finanţare de la un investitor important.

Şi nu uita, la sfârşitul proiectului, după aproximativ o lună, cei mai buni participanţi vor avea ocazia să participe la un teambuilding alături de o parte din speakerii evenimentului pentru a îi cunoaşte mai bine, a îşi prezenta ideile şi a lega eventuale colaborări.

La proiect, vei avea ocazia să îi cunoşti pe Vlad Stan (SeedMoney), Sergiu Biriş (Trilulilu), Vladimir Oane (UberVU), George Lemnaru (Erepublik), Daniel Enache (Investitor), Marius Deak (GreenPixel) şi mulţi alţii!

Pentru a aplica la proiect accesează site-ul www.thinkonline.ro .

Algoritmiada se îndreaptă cu paşi repezi spre runda finală. Ne-am distrat, dar n-am încetat să facem şi treabă serioasă, v-am pregătit probleme frumoase şi v-am pus serios la încercare în repetate rânduri. Între timp, ca bonus pentru interesul vostru, am "redesenat" pe ici, pe colo monitorul de evaluare. Şi i-am mai pus nişte combustibil, acum se mişcă mai repede şi mai bine. :)
Ce a ieşit aţi văzut şi voi. De plăcut, credem că v-a plăcut, deoarece aţi revenit la fiecare rundă.

 
Iar ca să nu dezminţim ceea ce a devenit deja tradiţie, să tragem puţin cu ochiul la rezultatele din weekendul acesta, când s-a jucat ultima carte pentru calificare:

În rândul celor mici, la gimnaziu, punctajele au fost din păcate mai timide. La nivel de dificultate, problema uşoară a fost Binar, cea medie Copii, iar cea grea Cuburi5. În mod surprinzător, problema Binar nu a fost rezolvată decât de un singur concurent; majoritatea a ales să implementeze QuickSort, nereuşind să observe soluţia O(N * M). Cu toate acestea, în rândul primilor 3 concurenţi s-au înregistrat şi punctaje maxime pe problemă. Îi felicităm astfel pe •liana tucar şi pe •Taloi Bogdan Cristian, ocupanţii locurilor 2, respectiv 3, pentru scor maxim la problema Copii, şi mai ales pe •Eugenie Daniel Posdarascu, singurul care a găsit soluţiile optime pentru Binar şi Cuburi5!

La clasele 9-10 problemele s-au împărţit după cum urmează: cea uşoară a fost Copii, cea medie Reţea, iar cea grea Matrice3. Felicitări lui •Andrei Purice pentru că a obţinut cel mai mare punctaj, şi laude speciale lui •Serban Andrei Stan, singurul care a rezolvat problema grea şi care, de altfel, a fost la un pas de punctajul maxim. Îl tragem virtual şi părinteşte de urechi pentru că a greşit tocmai la problema uşoară, dar sperăm să ia aminte la runda finală :). Nu îl uităm nici pe •Voroneanu Radu Stefan şi îl felicităm pentru a treia poziţie în clasament!

Clasele 11-12 au avut un set greu de probleme, probabil mai dificil ca în celelalte runde. La această grupă savoarea a fost dată de lupta strânsă pentru ultimele locuri de calificare, care a făcut aşteptarea mai interesantă. Ca grad de dificultate, Reţea a fost problema mai uşoară, Piraţi cea medie şi Compact problema grea. Cu toate că notăm câteva punctaje maxime în rândul celei din urmă, se pare însă că nimeni nu a ieşit victorios în lupta cu Piraţii. Podiumul a fost ocupat, în ordine, de •Andrei-Bogdan Antonescu, •Andrei Poenaru, •Cazacu Alexandru şi •Andrei Parvu, ultimii doi aflându-se la egalitate. Felicitări!

Nu în cele din urmă, punem sub lupă şi studenţii, care au avut un set de probleme mai uşor ca altădată (Cuburi5 uşoară, Tree medie şi Compact grea). Îi spunem bravo din nou veteranului nostru, •Mugurel-Ionut Andreica, singurul concurent care a obţinut punctaj maxim! El se situează (iar) pe primul loc, atât runda aceasta cât şi în clasamentul final, unde a obţinut un remarcabil scor de peste 1000 de puncte. Felicitările noastre merg şi către al doilea clasat, •dragus marius, dar şi către ocupanţii locului 3, unde avem iar egalitate: •Tudose Vlad şi •Vlad Saveluc.

În ceea ce priveşte comisia ştiinţifică, aceasta şi-a făcut bine treaba, cu aceeaşi rigurozitate cu care v-a obişnuit. O mică scăpare a avut loc la problema Piraţi, unde enunţul nu a fost suficient de clar asupra modului în care trebuie afişată soluţia. Mulţumim concurenţilor pentru că au sesizat cu promptitudine situaţia, pe care am remediat-o imediat pentru a ne asigura că nu defavorizăm pe nimeni. De asemenea, trebuie menţionat faptul că nu s-au putut diferenţia in mod corespunzător soluţiile O(N) şi O(NlogN) la problema Compact şi comisia a preferat să lase limita de timp mai largă pentru a-i păstra calitatea (diferenţa între concurenţi să nu se facă la nivel de implementare sau în funcţie de diverse trucuri de optimizare). Din păcate, acest lucru a permis ca unii concurenţi să obţină punctajul maxim şi fără să rezolve problema optim.

 
Ca să nu vă trădăm aşteptările, iată şi statisticile, după cum v-am obişnuit la fiecare rundă:

 
Vă aşteptăm şi la Finală: cu mic cu mare, în dulce târgul Ieşilor (da, aţi văzut bine, bătălia cea mare se dă la Iaşi). Şi pentru cei care nu veţi veni, vă aşteptăm, ca de obicei, la competiţia online, cu aceeaşi (inter)faţă prietenoasă, cu un set de probleme cât se poate de interesante şi cu la fel de multă dedicare: nu fiţi dezamăgiţi de rezultate, ultima şi cea mai importantă rundă vă oferă ocazia să arătaţi că locul vostru este undeva mai sus!

Până atunci, vă rugăm nu uitaţi să vă completaţi paginile de profil: vrem să vă cunoaştem, atât noi cât şi tot restul lumii, că doar ne mândrim cu voi. :)

 
Aşteptăm impresiile voastre de până acum, dar şi gândurile cu care întâmpinaţi Finala. În plus, să ştiţi că n-am uitat cât v-a plăcut fotbalul la Braşov. O să revenim cu surprize!

In ultimele doua saptamani membrii echipei infoarena au muncit pe branci pentru a imbunatati calitatea site-ului. Am organizat doua "coding camp-uri" in care am reusit sa facem urmatoarele:

• Am optimizat baza de date. Cel mai nou membru al echipei, Savin Tiberiu •devilkind, impreuna cu Bogdan-Cristian Tataroiu •bogdan2412 au reusit sa creasca performanta site-ului. La ultima runda a concursului Algoritmiada s-a putut observa acest lucru spre finalul concursului, cand nu a mai murit infoarena, doar s-a miscat putin mai greu :D.
• Am adaugat functionalitate de acordat note problemelor. Gheorghe Cosmin •gcosmin si cu mine, Andrei Grigorean •wefgef, am creat o interfata prin care adminii pot acorda note problemelor din arhiva. Deasemena, helperii pot observa ca este mult mai usor sa editeze enuntul, parametrii si tagurile problemelor printr-o interfata cu taburi user-friendly.
• Victor Rusu •victorsb si Stefan-Alexandru Filip •Prostu au lucrat la probleme de backend

Intreaga echipa infoarena a contribuit la notarea primelor 100 de probleme din arhiva. Probabil ca multi dintre voi vor avea pareri diferite legate de dificultatile anumitor probleme. Nu avem pretentia ca valorile stabilite de noi sa fie absolute, am vrut doar sa oferim un indiciu orientativ utilizatorilor. Speram sa nu incepa polemici pe aceasta tema printre utlizatorii nostri. Notarea problemelor s-a facut conform IAP 16.

Puteti gasi mai multe detalii despre ce am facut aici si aici.

P.S.: In timp ce scriam acest post am aflat ca am depasit 1000 de probleme publice in arhiva! Go, go, go!

Pe data de 21 februarie a avut loc cea de-a treia rundă a concursului Algoritmiada 2010. La două luni de la de la runda a doua concurenţii au revenit să îşi măsoare forţele cu problemele propuse de infoarena.

Statisticile primelor 3 runde arată in felul următor:

Din statistici observăm ca numărul de concurenţi de la runda a treia este comparabil cu cel de la runda a doua. Este un lucru îmbucurător deoarece in anii trecuţi tendinţa a fost de descreştere de la rundă la rundă şi sperăm că la fel de mulţi concurenţi o să participe si la runda a patra.

Concurenţii de la gimnaziu au avut parte de un set de probleme dificil. Pe primul loc s-a situat •Eugenie Daniel Posdarascu cu 200 de puncte, pe locul al doilea •Mihai Gheorghe cu 170 de puncte iar pe locul al treilea, la egalitate, cu 110 puncte •cont cu nume gresit sau fals şi •Marius Gavrilescu.

Elevii de la clasele 9-10 au avut punctajele cele mai mari, iar la finalul rundei, 6 concurenti aveau punctaje mai mari sau egale cu 200 de puncte. Astfel, punctajul cel mai mare al rundei a treia, de 270 de puncte, a fost obţinut de •Adrian Budau. Poziţia a doua in clasament a fost ocupata de •Radu Zernoveanu cu 250 de puncte iar a treia de •Gavrila Vlad cu 240 de puncte.

La clasele 11-12 numarul de participanţi a fost semnificativ mai mare decat la celelalte grupe de varstă, însă problemele le-au pus mici probleme participanţilor. La finalul rundei numai 3 concurenti aveau un punctaj mai mare de 110 puncte, ei fiind •Andrei Parvu cu 200 de puncte, •Ungureanu Ilie cu 170 de puncte si •Cosmin-Mihai Tutunaru cu 160 de puncte.

Stundentii au avut parte de un set de probleme echilibrat. Toate problemele au fost rezolvate dar nici un concurent nu le-a rezolvat pe toate de 100 de puncte. Cel mai aproape a fost •Mugurel-Ionut Andreica care a obtinut 240 de puncte, el a fost urmat de •Florea Mihai Alexandru cu 200 de puncte si de •Jurca Razvan cu 170 de puncte.

Seturile de probleme propuse la runda a treia au fost bine structurate, reuşind sa departajeze in mod clar concurentii din varful clasamentelor si in acelasi timp oferindu-le tuturor participantilor cate o provocare.

Mult succes in runda a patra care are loc duminica, 21 martie, de la ora 9:00.

Echipa infoarena vă mulţumeşte pentru sprijinul acordat şi în 2009 prin direcţionarea a "2%" din impozitul pe venit! Înseamnă foarte mult pentru noi ajutorul şi implicarea directă a comunităţii - e o dovadă că munca noastră are un impact crescând in rândul utilizatorilor!

În 2009 fondurile primite prin sistemul "2%" au însumat 7.892 RON, ceea ce reprezintă o contribuţie cu peste 70% mai mare decât cea din 2008, când am înregistrat un total de 4.620 RON. Creşterea spectaculoasă ne bucură cu atât mai mult cu cât strângerea fondurilor necesare pentru organizarea concursurilor şi activităţilor infoarena a reprezentat întotdeauna o dificultate. Ajutorul vostru este deosebit de important deoarece bugetul infoarena este format din banii primiţi prin sistemul "2%", prin sponsorizari şi prin donaţii. În ultimii ani, sumele obţinute prin programul "2%" au fost printre cele mai importante două contribuţii primite anual de Asociaţia infoarena.

Faptul că programul "2%" prevede confidenţialitatea contribuabililor ne-a împiedicat să obţinem o listă nominală a acestora, însă le mulţumim tuturor cu sinceritate şi ne bucurăm că ne-au fost alături!

Având în vedere că sprijinul financiar din partea comunităţii devine din ce în ce mai semnificativ, ne intrebăm, ar putea un ONG cum e Asociaţia infoarena să fie finanţat integral printr-un astfel de sistem?

Ce este “2%”?

Pe scurt, "2%" este un sistem prin care orice contribuabil poate direcţiona, gratuit, "2%" din impozitul pe venit către o entitate non-profit, asigurând o mai bună transparenţă a sistemului fiscal şi ajutând la buna dezvoltare a organizaţiilor apropiate fiecăruia. Pentru mai multe informaţii puteţi vizita pagina infoarena dedicată sistemului "2%" sau pagina de informare doilasuta.ro.

Cum vor fi folosite fondurile primite?

Principala cheltuială a Asociaţiei infoarena o reprezintă organizarea finalei concursului Algoritmiada. Fondurile vor fi folosite pentru a asigura cazarea, masa si premiile celor mai buni concurenţi, elevi si studenţi. Anul acesta bugetul rundei finale porneşte de la 30.000 RON, ceea ce inseamnă că sprijinul vostru reprezintă peste 25% din costuri.

O altă investiţie a Asociaţiei infoarena constă in organizarea de coding-camps. În 2009 ne mândrim cu două asemenea întruniri în care s-au implementat numeroase facilităţi noi şi s-a dezvoltat site-ul, ceea ce a dus la lansarea versiunii infoarena 2.3. Cele mai importante componente implementate anul trecut le reprezintă concursurile virtuale şi tag-urile.

De asemenea, costuri apar şi pentru organizarea şedinţelor, in cadrul cărora ne impărţim responsabilitaţile şi “punem ţara la cale”. De-a lungul timpului, membrii echipei au discutat numeroase idei de proiecte pentru dezvoltare, pornind de la cele cu rol de a întări sau de a extinde comunitatea şi până la cele care ţin de development. Din lipsă de resurse însă, multe dintre ele au rămas doar la stadiul de idei. Sprijinul vostru ne poate ajuta să le punem in practică!

“2%” in 2010

infoarena are nevoie sa îi fii alături şi în 2010!

"2%" din impozitul aferent salariului tău, al părinţilor sau prietenilor poate însemna cazarea unui participant la finala Algoritmiada, costul unei şedinţe sau o parte din premiul acordat unui concurent remarcabil. Fiecare contribuţie contează!

Problema critică pentru răspandirea proiectului "2%" o reprezintă lipsa de informare. Ar fi de mare ajutor să le vorbeşti apropiaţilor despre beneficiile aduse unui ONG prin redirecţionarea procentului amintit din impozitul lor pe venit. Fii ambasador infoarena şi informeaza-ţi cunostinţele asupra sistemului "2%".

Sustineţi-ne şi in 2010! Procedura este simplă şi constă în depunerea unei declaraţii la administraţia financiară de care aparţine domiciliul tau. Termenul limită pentru depunderea cererilor este 15 mai 2010!

Vă mulţumim încă o dată pentru sprijin!