Blog infoarena

Problem: Resource hog

Cosmin
Cosmin Negruseri
08 ianuarie 2016

During this winter break I've spent some time reading through 'Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices' by George Varghese. Thanks Vlad Balan for recommending the book. It's fun to see how algorithms are heavily used in real world networking. I've stumbled upon a cute problem that I'd like to share (I might have seen it CLRS as well). Here it is:

IDENTIFYING A RESOURCE HOG

A software or hardware module needs to keep track of resources required by various users. The module needs a cheap way to find the user consuming the most resources. Since ordinary heaps are too slow, the device designers are willing to relax the system requirements to be off by a factor of 2. Can this relaxation in accuracy requirements be translated into a more efficient algorithm?

To paraphrase, the problem asks for a data structure with the following operations

  • use_resources(name, quantity) which does resources[name] += quantity (quantity can also be negative)
  • get_approximate_max() which returns name1 such that max(resources[name]) / 2 <= resources[name1] <= max(resources[name])

Using a map in combination with heap gives us a solution with O(log n) time for each of the two operations. Can we do better?

 Comentarii (7)

Categorii:

Retrospectiva anului 2015

GavrilaVlad
Gavrila Vlad
31 decembrie 2015

Anul 2015 s-a încheiat si m-am gândit ca ar fi potrivit să facem o trecere în revistă a celor mai importante momente din 2015 ale comunităţii informatice din România. Lista următoare este pur subiectivă, şi vă invit să o completaţi în comentarii cu alte fapte, evenimente sau experienţe pe care le consideraţi importante, fie şi din punct de vedere pur personal.

Rareş

Performanţa lui darrenRares Buhai darren de a ajunge pe locul 2 în Hall of Fame-ul IOI este fără îndoială de luat în seamă. Am ales să o trec pe prima poziţie a retrospectivei deoarece consider că Rareş va rămâne multă vreme cel mai bun performer al României la Olimpiada Internaţională de Informatică (poate fi doar egalat având în vedere regulile actuale ale Olimpiadei Naţionale). De asemenea, mediatizarea de care a beneficiat ajută la atragerea mai multor elevi spre domeniul informaticii, iar parcusul lui îi va inspira să muncească pentru a obţine, la rândul lor, rezultate frumoase. Tot ce mai putem dori acum este ca Rareş să continue colaborarea cu comunitatea din România, atât cât îi va permite timpul, pentru că sunt sigur că poate contribui cu mai mult decât medalii.

Juniorii

Deşi performanţele României la JBOI au fost dintotdeauna foarte bune, hrazvanHarsan Razvan hrazvan , alexpetrescuPetrescu Alexandru alexpetrescu , killer301Ioan Andrei Nicolae killer301 şi alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu sunt cei care au adus acasă cel mai bun rezultat din istoria competiţiei - 3 medalii de aur (inclusiv primul loc) şi una de bronz. Tot juniorii ne-au salvat onoarea şi la Shumen , obţinând 2 medalii de aur, 3 de argint şi 3 de bronz. Şi, judecând după curajul unora dintre ei de a participa la categoria Seniori a Algoritimiadei şi, mai mult, după punctajele bune obţinute la această categorie, aş zice că viitoarele rezultate ale României la competiţiile internaţionale vor fi la înălţimea aşteptărilor. Această previziune se va adeveri desigur doar dacă cei menţionaţi mai sus, alături de ceilalţi membri ai lotului, se vor pregăti în continuare cu aceeaşi seriozitate şi nu se vor mulţumi cu medaliile obţinute în anii junioratului.

Demn de menţionat şi plăcut surprinzător este şi că jumătate din lotul restrâns de juniori a fost compus din fete. Le felicităm pentru performanţele obţinute şi le dorim succes pe mai departe.

Seniorii

Nu putem încheia această listă fără a menţiona pe toţi cei care au obţinut medalii din partea echipelor oficiale ale României la competiţiile internaţionale din acest an. Aceştia sunt:

Îi felicităm pe toţi în egală măsură şi le dorim succes în anul care urmează.

2016

La ce ne putem aştepta deci în 2016? Cu plecarea lui Rareş Buhai, Alex Velea şi a lui Valentin Hârşan, lupta pentru calificarea la IOI devine foarte deschisă. Ne dorim desigur ca figurile vechi să îşi îmbunătăţească rezultatele, şi ca cele noi să producă surprize frumoase. Nu în ultimul rând, CEOI 2016 va avea loc în România, iar numărul de locuri rezervat ţării noastre va fi desigur mărit. Aş zice că momentul ales este cum nu se poate mai bun, deoarece lasă loc multor concurenţi cu potenţial de a se afirma la primul lor concurs internaţional de seniori.

În loc de încheiere, reiterez invitaţia de a ne scrie cele mai importante momente ale lui 2015 pentru voi în secţiunea de comentarii, şi adaug o listă de "New Year's Resolutions" cu specific informatic:

  • Participaţi la cât mai multe concursuri. Algoritmiada, Codeforces, USACO, COCI, TopCoder şi Mindcoding vă sunt prieteni.
  • După ce terminaţi de participat la un concurs, rezolvaţi problemele care nu v-au ieşit în timpul competiţiei, eventual după ce aţi citit soluţiile oficiale. Majoritatea site-urilor oferă această posibilitate, şi doar aşa puteţi progresa.
  • Updataţi-vă profilul pe infoarena. Poate că vi se pare inutil, dar din punctul de vedere al unui începător, este mult mai uşor să discute cu un utilizator experimentat atât online cât şi în viaţa reală dacă ştie despre el mai mult decât numărul de probleme rezolvate şi ratingul. Aşa DA: freak93Budau Adrian freak93 , eudanipEugenie Daniel Posdarascu eudanip ; aşa NU: andreiiiiPopa Andrei andreiiii , klamathixMihai Calancea klamathix .
  • Nu mai participaţi de pe conturi fantomă: e o dovadă de maturitate să vă asumaţi pregătirea, succesele şi eşecurile în faţa altora. În plus, dacă toţi procedaţi aşa, puteţi obţine sugestii de probleme pe care să le lucraţi urmărindu-i pe ceilalţi.

Nu în ultimul rând, La Mulţi Ani 2016!

 Comentarii (4)

Categorii:

Hour of Code

klamathix
Mihai Calancea
04 decembrie 2015

Hour of Code reprezinta sansa de a accesa domeniul IT intr-un mod interactiv si oportunitatea de a cunoaste si controla tehnologia prin tutoriale simple, cu personaje cunoscute tuturor ca Minecraft sau Star Wars.

Acest eveniment sta la baza evolutiei educatiei IT din Romania si alte tari au inteles deja asta: Italia are inregistrate 11.000 de evenimente in timp ce Romania are inregistrate doar 700 de evenimente.

Pentru ca industria IT de maine este responsabilitatea noastra, a tuturor, va invitam sa organizati un eveniment Hour of Code in cadrul institutiei dumneavoastra de invatamant. Nu trebuie decat sa va inscrieti evenimentul pe hourofcode.com/ro, sa alegeti o zi in intervalul 7-13 decembrie si sa parcurgeti impreuna cu elevii tutorialele de pe site-ul ro.code.org .

De asemenea, elevii/studentii la informatica pot sa se transforme in mici profesori si sa predea o Ora de Programare colegilor de la alte profile sau specializari.
Fiecare organizator va primi cate un premiu garantat oferit de partenerii internationali si solutii de securitate software din partea Bitdefender Romania. ADFABER va pune la dispozitie gratuit materialele de care aveti nevoie, efortul organizatorilor fiind unul minim.
Haideti sa facem cunoscut evenimentul Hour of Code si sa promovam Romania ca tara IT!

Link-uri utile:
Materiale necesare aici: bit.ly/Materiale
Facebook (sharing is caring): facebook.com/HourofCodeRo
Inregistrare eveniment Hour of Code (hourofcode.com/ro) - pana pe 4 Decembrie
Participare eveniment ro.code.org

 Comentarii (2)

Categorii:

Algoritmiada 2016

klamathix
Mihai Calancea
26 noiembrie 2015

Prima rundă a concursului Algoritmiada 2016 va avea loc Duminica, 6 decembrie, ora 10:00. Mai multe detalii despre formatul şi regulamentul concursului, cât şi despre programul complet al rundelor de calificare puteţi găsi aici.

Vă aşteptăm în număr cât mai mare, cu intenţia ca problemele să fie interesante pentru orice participant, indiferent de vârstă sau nivel de experienţă. Baftă!

 Comentarii (3)

Categorii:

Membri noi în echipa infoarena

klamathix
Mihai Calancea
20 octombrie 2015

Suntem încântaţi să anunţăm extinderea echipei infoarena cu doi noi membri! Aceştia sunt dariusdariusMarian Darius dariusdarius şi andreiiiiPopa Andrei andreiiii. Andrei şi Darius sunt veterani ai olimpiadelor de informatică, iar în curând vor fi şi veterani ai comisiilor :). Le urăm bun-venit şi o perioadă cât mai fructuoasă în cadrul echipei, atât pentru ei cât şi pentru comunitatea infoarena.

 Comentarii (4)

Categorii:

Finala Algoritmiada 2015

freak93
Budau Adrian
28 august 2015

Finala Algoritmiada 2015 va avea loc la Cluj în perioada 11 - 13 septembrie.

Noi am alcatuit o lista provizorie cu participantii calificati la finala. Am dori sa trimitem invitatiile cat mai repede asa ca va rugam sa ne ajutaţi cu finalizarea ei. Dacă credeţi că vedeţi vreo greşeală în acesată listă, vă rugăm să comentaţi la această postare şi să ne contactaţi printr-un mesaj privat. În verificarea listei, vă rugăm să consultaţi regulamentul Algoritmiadei.

La juniori s-a intamplat ca locurile 2, 3 si 4 de la clasele a 6-a sa se califice cu acelasi scor. Îi vom invita pe toti 3 si vom mari numarul de participanti de la juniori (in caz ca vor participa toti 3) la 16.

Calificati JunioriNume CompletClasa
1Greaca Albert5
2Ionescu Andrei5
3Tran Bach Nguyen6
4Alexandru Ioan Moise6
5Gheorghe Armand Liviu6
6Tudor Coman6
7Eftime Andrei Horatiu9
8Petrescu Alexandru8
9Niculae Alexandru Vlad9
10Laura Georgescu8
11Bogdan Sitaru8
12Cristina Borza8
13Livia Magureanu9
14Moise Gabriel9
15Emanuel Adrian7
16Matei Staicu 7

Si pentru Seniori avem un caz exceptional, locurile 3 si 4 pentru clasa a 11-a sunt la egalitate. II vom invita pe amandoi si vom invita tot 13 elevi in afara celor calificati automat la fiecare clasa (deci un total de 26). Menţionăm că Rareş Buhai, Mihai Popa şi Mihai Enache au confirmat deja că nu vor participa, iar această listă nu îi ia în considerare.

Calificati SenioriNume CompletClasa
1Costin Oncescu9
2Anca Anghel9
3Alex Tatomir9
4Andrei Popa10
5Andrei Costin Constantinescu10
6Ioan-Bogdan Iordache10
7Radu Muntean11
8Paul Gramatovici11
9Patrick Sava11
10Marilena Bescuca11
11Alex Velea12
12Denis Mita12
13Alex Cociorva12
14Vlad GavrilaOpen
15Mihai NituOpen
16Dragos RistacheOpen
17Visan RaduOpen
18George MarcusOpen
19Mircea Popoveniuc12
20Tudor Costin Razvan 10
21Andrei Stanciu10
22Bogdan Dobre10
23Dan Alexandru Bodnariuc12
24Darius Marian10
25Alexandru Valeanu12
26Razvan Nicolescu10

 Comentarii (12)

Categorii:

Interviu cu Matei Zaharia

Cosmin
Cosmin Negruseri
14 august 2015

Matei Zaharia e o celebritate in domeniul sistemelor distribuite. El este fondatorul Spark, solutia de procesare big data cu cresterea cea mai mare din ultimii ani. Acum e assistant professor la MIT si CTO al firmei DataBricks. El cauta programatori ce vor sa lucreze la un startup pe domeniu de sisteme distribuite in San Francisco. Puteti sa il contactati la adresa [email protected] El a raspuns la cateva intrebari pentru blogul infoarena.

Matei are un parcurs interesant pentru comunitatea infoarena. Familia lui s-a mutat in Canada in 1996 cand Matei avea 11 ani. In liceu a facut parte din echipa Canadei la Olimpiada Internationala de Informatica. A luat doua medalii de argint. A urmat cursurile de informatica a univestitatii Waterloo. Echipa lui s-a clasat pe locul 15 in 2004 si pe locul 4 in 2005 la finala concursului ACM ICPC.

A urmat un doctorat la UC Berkeley in sisteme distribuite. Acolo l-a avut ca si coordonator pe profesorul Ion Stoica. El are o activitate de cercetare impresionanta, lucrarile lui fiind citate de alte 15664 lucrari de cercetare. Acum are o pozitie de assistant profesor la MIT in grupul care e probabil cel mai puternic gup de cercetare de sisteme distribuite din lume (fiind la competitie cu grupul de la UC Berkley de unde vine Matei).

In paperul Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing Matei introduce o noua metoda de a procesa seturi de date mai flexibila si mai rapida decat metoda Mapreduce popularizata de Google.

In 2013 a fondat compania DataBricks care pune in productie aceasta metoda si o face mai accesibila analistilor. Compania are acum 47 de milioane de dolari finantare. Spark e cea mai activ proiect open source pe domeniul big data.

1. Matei ne poti spune ce utilitate au avut pentru tine concursurile de programare?

Matei Am invatat foarte mult in concursuri. Pe de o parte, am invatat algoritmi, dar in plus am invatat si cum sa scriu solutii in mod minimal si sa anticipez cat mai multe cazuri posibile. In general, un lucru important in programare este sa anticipezi si sa minimizezi starile posibile ale aplicatiei.

2. Care a fost tranzitia de la concursuri de programare la cercetare?

Matei Multe lucruri pe care le-am invatat la concursuri au fost aplicabile direct. In cercetare, vrei sa testezi o idee noua cat mai repede, si iti trebuie agloritmi si cod eficient. Totusi, pentru proiecte mari ai nevoie nu doar de algoritmi si optimizari ci si abstractizari care sa ajute la organizarea buna a acestora.

3. Cum se compara activitatea de cercetare cu cea de a fi Chief Technical Officer pentru un un startup in crestere?

Matei La startup, avem aceiasi nevoie sa dezvoltam idei in mod rapid, dar trebuie si stabilitate pentru un produs care merge direct la clienti si pentru o echipa de ingineri care creste repede. Noi am reusit sa atragem o echipa foarte buna cu background similar cu mine, deci putem sa atacam problemele noi repede. Ca CTO am incercat sa tin un standard ridicat pe partea de inginerie si sa stabilesc procese si o infrastructura care ne permit sa construim software fantastic in mod rapid.

4. Cum sari intre rolurile de coordonator pentru o comunitate open source foarte populara si cea de coordonator tehnic al unei companii private?

Matei Nu e foarte greu, pentru ca procesele sunt similare. In ambele cazuri, avem un grup mare de programatori care contribuie si procese de code review si de testare automata similare. Noi dezvoltam toate modificarile noastre la Spark in open source, deci sunt foarte bine aliniate cu comunitatea de utilizatori.

5. Ce sfaturi ai pentru programatorii din comunitatea infoarena?

Matei Daca aveti o sansa sa participati in open source, deschide multe usi pentru o cariera in software. Va incurajez sa participati la niste proiecte sau sa va publicati proiectele voastre ca sa invatati intregul ciclu de software engineering si sa aveti projecte interesante de a arata pe CV.

Multumim pentru interviu!

 Comentarii (1)

Categorii:

Balance

Cosmin
Cosmin Negruseri
29 iulie 2015

Here's a neat problem I've seen again recently.

Given A, a set of n points in the plane, each point having integer coordinates. Come up with an algorithm that colors some of the points in the set red and the remaining points white in such a way that for any straight line L parallel to either one of the coordinate axes the difference (in absolute value) between the numbers of white point and red points on L is not greater than 1.

 Comentarii (2)

Categorii:

Statistici pentru probleme (beta)

Vman
Duta Vlad
27 iulie 2015

Daca nu ati observat inca, pe pagina fiecarei probleme in partea dreapta sus avem acum un link catre statisticile problemei. Statisticile includ cele mai bune 5 rezultate obtinute pentru timpul de executie, memorie si lungimea codului sursa, precum si o histograma cu distributia punctajelor. Speram ca aceste statistici sa va ajute sa evaluati mai bine dificultatea problemelor si totodata sa va motiveze sa lucrati cat mai cu spor :)

Intreg meritul pentru lansarea statisticilor ii apartine lui PlayLikeNeverB4George Marcus PlayLikeNeverB4, drept pentru care ii multumim pentru efortul depus in implementarea acestui nou feature (round of applause). Ne bucuram cand membrii comunitatii se implica voluntar in dezvoltarea infoarena si speram ca exemplul sau va fi urmat si de alti membrii care doresc sa imbunatateasca "arena".

Ca de obicei asteptam sugestii, pareri, comentarii pe forum in topicul asociat. Spor la codat!

 Comentarii (17)

Categorii: statistici

Biografii olimpici

klamathix
Mihai Calancea
23 iunie 2015

Blogul merita o vizita. Veti recunoaste nume pe care le stiti deja, dar ale caror povesti poate nu le stiati inca.

 Comentarii (0)

Categorii:
Vezi pagina: 123 45678... 3536373839 (382 rezultate)