Suntem încântaţi să anunţăm că Algoritmiada, cel mai important concurs Infoarena, se întoarce în sezonul 2014-2015!

Nou veniţi?

Algoritmiada este concursul tradiţional, de marcă, al Infoarenei. Este moştenitorul preONI-ului, primul concurs ţinut pe site (2004), care avea scopul de a pregăti elevii doritori pentru Olimpiada Naţională de Informatică. Între timp, concursul şi-a extins orizonturile şi a renăscut în anul 2009 sub numele de Algoritmiada, cu scopul declarat de a pregăti orice persoană pasionată de algoritmică şi concursuri de programare.

Arhiva concursurilor vă oferă acces la toate rundele preONI şi Algoritmiada desfăşurate până în prezent. Sunt mândria noastră şi vă invităm călduros să lecturaţi şi să rezolvaţi problemele din anii trecuţi!

De-ai casei?

Ei bine, avem de discutat şi cu voi! Începând cu această ediţie Algoritmiada îşi schimbă formatul, după cum vom explica în continuare.

Doar două grupe de vârstă

Din acest an Algoritmiada va avea doar două grupe de vârstă.

- Juniors. Dedicată elevilor de gimnaziu şi elevilor de clasa a 9-a începători, care aleg să participe la această grupă. Numărul de concurenţi care se vor califica la runda finală este de 15. Vă invităm să studiaţi criteriile de calificare aici.

- Seniors. Dedicată în primul rând elevilor din clasele 9-12, dar şi studenţilor, profesorilor şi pasionaţilor de algoritmică în general. Numărul de concurenţi care se vor califica pentru Runda Finală este de 25. Din nou, vă invităm să citiţi regulile de calificare în detaliu aici.

De ce?

- Credem că un set echilibrat de probleme poate fi o provocare adecvată atât pentru un concurent începător cât şi pentru unul experimentat, tematica atinsă nefiind un impediment. Considerăm, din acest punct de vedere, nenaturale limitele impuse de programa tradiţională a Olimpiadei.

- Ridicarea acestor limite stimulează în timp creşterea calităţii problemelor, o temă prioritară din punctul nostru de vedere.

- Vasta majoritate a ţărilor care au o cultură puternică în informatică au adoptat acest model chiar în cadrul Olimpiadelor Naţionale. Exemplul cel mai accesibil şi relevant pe care îl oferim este Polonia. Rusia, China, SUA, Japonia şi Croaţia continuă lista ţărilor care nu separă Olimpiada Naţională în funcţie de clasă.

Concluzii

Suntem încrezători că acest nou format reprezintă un pas în direcţia bună. În acelaşi timp, suntem conştienţi că această tranziţie trebuie realizată cu grijă. Echipa Infoarena vă stă la dispoziţie pentru orice fel de întrebări, comentarii şi sugestii pe această temă şi vă doreşte succes în noul sezon competiţional!

Here's a neat problem I've heard from Christian Szegedy:

N cars are moving in the same direction with different speeds on an infinite straight road. The cars can't pass each other so clusters form. What's the expected number of clusters?

Feel free to discuss in the comment section. Don't forget to vote on Sunday!

Rating

Infoarena a trecut prin multe schimbari in ultimii ani, iar din pacate procesul de update al rating-ului nu a fost adaptat in mod corespunzator. Ne referim in primul rand la:

1. Formula imperfecta, care de-a lungul vremii a cauzat cresteri/scaderi controversate.
2. Decizia nefericita de a mentine un rating unic pentru toate concursurile Infoarena, indiferent de formatul acestora.

Din aceste motive, am hotarat in cadrul echipei sa schimbam rating-ul pentru concursurile ce vor urma in continuare. Am considerat ca cea mai echitabila solutie este ca formula noua sa se aplice pe rating-urile curente, lasandu-le in timp sa se stabilizeze intr-o distributie conforma cu noile standarde. Rating-ul curent va ramane valabil doar pentru concursuri stil olimpiada (Algoritmiada + altele), urmand sa apara rating-uri separate pentru celelalte stiluri majore de concurs (ACM ICPC + altele). De-asemenea, userii care nu vor participa la niciun concurs pentru o perioada lunga de timp vor fi scosi temporar din clasamentul oficial, redevenind activi o data cu o noua participare.

Detaliile tehnice nu sunt inca stabilite, va dura o vreme pana vom finaliza schimbarea. Deocamdata, am dat un update mai mult decat necesar pentru rundele recente (dupa formula veche) :).

Java

Dupa cum unii dintre voi probabil ati observat, puteti acum submita solutii in Java pe infoarena! Proiectul este in faza Beta, fiind posibil sa intampinati unele dificultati, in special cu fisierele si limitele de timp si memorie. Momentan limitele sunt aceleasi pentru Java si C++. Va rugam sa semnalati orice problema in acest topic si vom incerca sa gasim o solutie. Pana atunci, spor la codat!

Andrei, Octav si Vlad de la stanga la dreapta

Il stiu pe Vlad de la concursurile de programare. Mai apoi am vorbit mai mult cu el si cu Andrei la Google in Mountain View unde faceau un internship pe vara. La terminarea facultatii au facut echipa cu Octav si au luat drumul strainatatii, incepand un startup in Canada. Le-am luat un interviu despre traseul lor.

1. Spuneti-ne putin despre voi si despre Talentbuddy.

Andrei: Primul meu contact cu programarea a fost in clasele 5-8, cand memoram programe Pascal ca sa nu raman corigent. In liceu programele au devenit mai mari, astfel incat am fost fortat sa le inteleg. Am descoperit ca imi place foarte mult sa programez si am inceput sa ma pregatesc cot la cot cu olimpicii la informatica.

Am continuat studiile la Politehnica Bucuresti, timp in care am lucrat pentru GNOME (in cadrul Google Summer of Code), Nokia (Berlin) si Google (San Francisco). In San Francisco am cunoscut multi antreprenori si am fost atras de lumea startup-urilor, asa ca imediat dupa terminarea facultatii am pornit la drum impreuna cu Vlad si Octav.

Vlad: In primul an de liceu am inceput sa invat programare si algoritmica destul de sistematic iar pentru urmatorii 4 ani infoarena.ro mi-a fost homepage. Ulterior, am mers la Universitatea Politehnica din Bucuresti si in prima vacanta de vara am facut un internship ca software developer la BitDefender. Pentru urmatoarele doua veri m-am alaturat echipei de Statistical Machine Translation din cadrul Google Research, Mountain View ca software engineer intern.

In final, am decis sa aleg o alta traiectorie in cariera si impreuna cu prietenii mei Andrei si Octav am pornint un startup in Vancouver, Canada.

Octav: Am studiat stiinta calculatoarelor si inginerie electrica la Jacobs University Bremen in Germania si am absolvit in anul 2007.

Prima mea interactiune cu un calculator a avut loc in clasa a 5-a, in 1995, in timpul primelor cursuri de informatica. Asa am invatat sa programez in Basic pe calculatoare CoBra si HC.

Am inceput sa folosesc calculatorul acasa incepand cu 1997 (clasa a 7-a) pentru a crea diverse proiecte pentru familie, rude, colegi si cateva firme din Romania. Am inceput cu design grafic (carti de vizita, brosuri, postere, etc) si am continuat cu site-uri si aplicatii web.

In 2007, dupa absolvirea facultatii, m-am intors in Romania si am inceput sa lucrez la aplicatii web comerciale (kmbio, Trigwee), iar in 2011 am plecat in Canada impreuna cu Andrei si Vlad unde am lucrat la Sunnytrail, Talentguide. In prezent lucram la Talentbuddy.

Mai am de lucru pana voi atinge nivelul de succes pe care mi-l doresc, insa fiecare dintre aceste proiecte, a fost un pas inainte. Am invatat multe lectii valoroase despre ce inseamna sa creezi, finantezi si distribui un produs.

Talentbuddy: este o platforma educationala pentru programatori. Oferim aplicatii web si mobile cu ajutorul carora un programator isi poate testa abilitatile precum si programe de educatie mentorate de experti.

2. Ati refuzat traseul corporatist si ati ales sa fondati un startup. Cum ati luat decizia?

Octav: Am hotarat sa incep un business in 2007, dupa ce am terminat facultatea in Germania. Cautam un mediu de activitate cu autonomie mare. Imi doream sa pot lucra direct cu oamenii care beneficiaza de serviciul / produsul meu si sa imi creez propriile responsabilitati. Nu am reusit sa gasesc joburi care sa ofere un astfel de mediu asa ca am decis sa creez un business in toamna lui 2007.

Andrei: Imi place sa creez produse noi, care sa ajute oamenii. La o companie ca Google sau Facebook sansele de a fi implicat in conceptualizarea si implementarea unui produs nou de la zero sunt foarte mici. Este posibil, bineinteles, dar cea mai sigura si rapida cale a fost sa infiintez o companie noua.

Vlad: Imi place sa programez, dar intotdeauna am fost fascinat de tot ceea ce inseamna business si organizatii de oameni. Nu vedeam totusi de unde ar trebui sa incep.

Ulterior, cunoscandu-i mai bine pe Andrei si Octav am realizat ca ei sunt punctul de start si sunt pus in fata unei oportunitati unice. Nu am avut nicio ezitare in a porni la drum cu ei si a lasa in urma Google sau alte companii interesante. Echipa a fost cel mai important element al deciziei.

3. De ce Canada, nu Romania sau Europa?

Din 2 motive:

a) Acces la investitori: in Europa sunt mult mai putini investitori si in general sunt mai reticenti sa investeasca in startup-uri early-stage. A fost si un factor de spontaneitate - tocmai ce ne fusese recomandat un accelerator nou in Vancouver care ne oferea $175,000. In Europa nu exista un astfel de program care sa ofere o investitie comparabila in conditii legale la fel de bune.

b) Acces la o piata mare: Europa este formata din multe tari, fiecare cu limba si cultura lor, ceea ce creste dificultatea de a scala un business. In acelasi timp, North America ne pune la dispozitie o piata mare de oameni cu aceeasi cultura si cu putere de cumparare mare. Ne este mult mai usor sa scalam afacerea pe o piata mare si omogena.

Numarul ridicat de investitori si potentiali clienti cresc sansele de succes ale unui startup semnificativ. Desigur am fi putut porni un business si in Romania sau Europa, dar prin definitie sansele de success sunt foarte mici pentru un startup. Am avut oportunitatea sa crestem sansele si nu am ezitat.

4. Cum ati ajuns acolo?

Totul s-a intamplat destul de repede. Cu cateva luni inainte sa terminam facultatea am participat toti 3 la un concurs de business organizat de Ixia in Bucuresti. Am castigat premiul de $20,000. Ulterior am aplicat la Growlab, am fost acceptati si am decis sa ne mutam in Vancouver.

5. Cum a fost partea de fundraising?

Am reusit sa obtinem finantare de la Version One Ventures, BDC si Initio Group - conexiuni pe care le-am legat pe parcursul Growlab.

Nu am avut acces la acelasi numar de investitori pe care il pune la dispozitie YCombinator, iar compania nu a fost evaluata la acelasi nivel ca o companie care participa la YC - dar optiunile au fost mai bune ca in Europa.

Per ansamblu, am avut acces la oportunitatile necesare pentru a trece la urmatorul nivel de dezvoltare si comercializare.

6. De ce se ocupa Talentbuddy? Ce problema rezolva?

Initial, Talentbuddy rezolva problema de training pentru interviuri la companii precum Google. Interviurile tehnice sunt dificile si e nevoie sa fii pregatit sa rezolvi anumite categorii de probleme inainte sa aplici. Talentbuddy ofera seturi de probleme, un IDE, un sistem care testeaza calitatea solutiilor automat si o modalitate de a accesa solutiile create de alti programatori la aceeasi problema.

Pe masura ce numarul de utilizatori ai platformei a crescut, scopurile in care este folosita s-au diversificat. Astazi platforma este folosita de profesori si studenti la cursuri de CS, de programatori profesionisti pentru distractie sau pentru a invata un limbaj de programare nou.

In mai 2014 am introdus doua programe de mentorat online pentru oamenii fara experienta in programare dar si pentru profesionistii care nu au timp sa mearga la cursuri de training offline sau nu au reusit sa capete experienta practica pe care si-o doresc prin alternative educationale precum Coursera, Udacity, Treehouse sau Lynda.

Majoritatea alternativelor mentionate mai sus se concentreaza pe predarea si aplicarea conceptelor in situatii izolate. Spre deosebire de alternativele existente, programele noastre de mentorship te ajuta sa inveti intr-un context foarte similar cu un job real. Am publicat recent un articol care explica in detaliu diferentele intre un program de mentorship si alte alternative pe care le poti gasi pe Internet.

7. Ce sfaturi aveti pentru programatorii din comunitatea infoArena?

Recomandam oricarui programator din comunitate sa fie atent la problemele care apar in mediul in care traieste si in loc sa le ignore, sa ia initiativa pentru a le rezolva. Nu gasesti un fotograf bun pentru o petrecere? Creaza un loc unde poti gasi fotografi usor. Nu iti place experienta de shopping online? Creaza una mai buna - si asa mai departe.

8. Cateva cuvinte de final?

Daca vrei sa schimbi felul in care oamenii isi dezvolta abilitatile de programare si daca stapanesti foarte bine fundamentele programarii, alatura-te echipei de mentori de la Talentbuddy. Esti platit, poti lucra in timpul liber, de oriunde din lume, impreuna cu fosti ingineri Google si Youtube.

Asteptam un email de la tine la adresa [email protected]

Edit: 110 nume de interni! Am extins spreedsheet-ul si la alti ani. Avem pagini diferite pentru anii trecuti. Adaugati cu incredere!

Edit: Impresionant, am ajuns la 80 de nume de interni! Dati share la prieteni si pe liste interne la univeristati poate mai gasim cativa!

Vreau sa fac un experiment similar cu cel din tabelul cu olimpici romani. Daca sunteti interni sau stiti vreun intern roman in strainatate anul asta, va rog sa adaugati un rand in tabelul din linkul urmator:

tabel

Mersi fain si bafta la internship!

Edit E ok si daca sunteti interni inafara Romaniei dar nu in Silicon Valley, adaugati cu incredere.

Cosmin

Here's a set of probability problems. Try to solve them in the comments section.

1. (von Neumann’s biased coin) You’re given a biased coin. It falls heads with an unknown probability p and tails with the probability 1 - p. Can you come up with a way to generate fair 0 and 1 results?
2. A rand5() function gives uniform integer results between 1 and 5. How can you use it to build a rand7() function? (microsoft interview)
3. Build a function rand(x, y, r) that returns a uniformly random point in the circle given by the (x,y) center and the r radius. (dropbox interview)
4. Build an algorithm that returns a uniform random permutation of numbers 1 to n. (google interview)
5. (Reservoir sampling) Given a stream of integers build an algorithm that returns a uniform random sample of size k using O(k) memory. (google interview)
6. (Coupon collector’s problem) Suppose a kid wants to collect all the cartoon characters in a kinder surprise series. Given that there are n different characters in total and they are distributed uniformly random. What's the average number of kinder eggs he has to buy so that the selection is complete. (twitter interview)
7. (Balls and bins problem) m balls are thrown into n bins. Each ball has 1/n probability of falling into each bin. What’s the expected number of empty bins? (twitter interview)
8. What’s the average number of times line 4 is executed if p is a random permutation of numbers 1 to n. (pinterest interview)

min = p[0]
 for x in p:
   if min > x:
     min = x

Astazi, 5 iunie 2014, se implinesc doi ani de la plecarea lui Mihai Patrascu pe drumul fara intoarcere, cunoscut in comunitatea informatica romaneasca pentru rezultatele lui impresionante la olimpiadele internationale de informatica (4 medalii de aur si 3 de argint) si pentru problemele lui originale.

Ca student la MIT, in 2005, a obtinut premiul pentru cel mai bun student in cercetare din SUA si Canada, iar cu lucrarea de doctorat a obtinut premiul pentru cea mai buna teza de la MIT. In 2012, Asociatia Europeana de Informatica Teoretica i-a acordat premiul Presburger pentru revolutionarea domeniului de structuri de date.

Mihai a fost un apropiat al comunitatii infoarena, a fost presedintele Comisiei Stiintifice a Balcaniadei (2011) si a Olimpiadei Europei Centrale (2009), membru al Comitetului Stiintific al Olimpiadei Internationale de Informatica (2011), s-a implicat in comisiile stiintifice ale mai multor olimpiade si concursuri nationale si a sustinut conferinte la universitati romanesti pe marginea rezultatelor sale in cercetare.

Rog toti utilizatorii infoarena sa pastreze un moment de reculegere in memoria lui Mihai.

Odihneasca-se in pace.

In acest weekend, la Bucuresti a avut loc runda finala a primei editii a Olimpiadei Nationale de Informatica pentru Studenti. Au participat peste 20 echipe din tara, doua zile de concurs, aceleasi taste apasate si multe pizza consumate. Felicitari tuturor participantilor si multumiri sponsorilor si partenerilor nostri pentru implicare: Fundatia eMAG, Bitdefender, TechHub, Asociatia Studentilor la Matematica si Informatica, Facultatea de Matematica si Informatica, Universitatea din Bucuresti. Speram ca a fost o experienta placuta pentru toti si va asteptam si la anul, in numar cat mai mare!

Clasament Runda Finala

Clasament ACM-ICPC Faza Nationala

Poze

What is bisection search? The bisection method or bisection search is a numerical algorithm for finding a value x such that f(x) = 0, for a given continuous function f. It works by repeatedly bisecting an interval and choosing a subinterval that contains x. It's pretty simple and robust, but it has few gotchas.

Let's solve the following problem:

For a given number c find it's cubic root using the +, -, *, / operations.

Try solving the problem on your own, before reading below.

Let's choose f(x) = x³ - c. f is continuous and x is the cubic root of c, when f(x) = 0. Thus, we can apply the bisection method.

def cubicRoot(c):
  lo, hi = 0.0, c
  while lo * lo * lo != c:
    mid = (lo + hi) / 2
    if mid * mid * mid < c:
       lo = mid
    else:
       hi = mid

  return lo

Any bugs? Well, quite a few. Try to spot as many as you can, before reading on.

You may notice the precision issue right from the start. We'll discuss it a bit later.

What else? The code doesn’t work for negative values of c. This is easily fixable:

def cubicRoot(c):
  lo, hi = 0.0, c
  while lo * lo * lo != c:
    mid = (lo + hi) / 2
    if mid * mid * mid < c:
       lo = mid
    else:
       hi = mid

  return lo

def cubicRoot(c):
   if c < 0:
       return - _cubicRoot(-c)
   else:
       return _cubicRoot(c)
}

What else? This code doesn't work for c = 1/1000. Why is that? We’re setting the cubic root upper limit to c (line 3). But, the cubic root of c in (0, 1) is larger than c, meaning the upper bound we’re setting is wrong.

Let's fix it:

def _cubicRoot(c):
    lo, hi = 0.0, max(1, c)

    while lo * lo * lo != c:
        mid = (lo + hi) / 2
        if (mid * mid * mid < c):
            lo = mid
        else:
            hi = mid

    return lo

def cubicRoot(c):
    if c < 0:
        return -_cubicRoot(-c)
    else:
        return _cubicRootABS(c)

Going back back to the precision issue:

If you've read nearly all binary searches and merge sorts are wrong you know that mid = (lo + hi) / 2 has an overflow problem. So we change that line to mid = lo + (hi - lo) / 2.

Testing for equality doesn't work with floating point numbers. The first idea that comes to mind is to use an absolute error comparison (|a - b| < eps).

Instead of:

while lo * lo * lo != c:

switch to

while abs(c - lo * lo * lo) > 1e-3:

This doesn't work. For large numbers like 1e37 the code goes into an infinite loop. Try to figure out why. Discuss it in the comment section. Let’s try using the relative error (|(a - b) / b| < eps). There are some weird cases when a and b are close or equal to 0. Can the code be cleaner?

After each while loop iteration we learn something new about x’s range. A double has only 64 bits of precision. So instead of a tricky floating point stopping criteria we can run the loop a fixed number of times so that the interval is as small as the precision of our floating point numbers allows.

Tomek Czajka(of topcoder fame) pointed out that my final version was buggy as well. I chose the number of iterations to be 120 but that’s way too small. It doesn't work for c = 1e60.

A double is represented by the mantissa which consists of 52 bits and the exponent which contains 11 bits(signed). One loop iteration either decreases the exponent of our interval by 1 or we find out a new bit of the mantissa. The maximum value of the exponent is 2¹⁰ and the mantissa has 52 bits. Thus we need about 1100 steps to figure out the answer.

def _cubicRoot(c):
    lo, hi = 0.0, max(1, c)

    for iter in range(0, 1100):
        mid = lo + (hi - lo) / 2
        if (mid * mid * mid < c):
            lo = mid
        else:
            hi = mid

    return lo

def cubicRoot(c):
    if c < 0:
        return -_cubicRoot(-c)
    else:
        return _cubicRoot(c)

No more epsilon! But now, because of cases with large exponents, the code runs pretty slow on all cases. An idea is to stop as soon as we don't decrease the lo..hi interval, instead of doing a constant number of iterations. So here’s this faster version:

def _cubicRoot(c):
    lo, hi = 0.0, max(1, c)
    prev_range_size = hi - lo
    while True:
        mid = lo + (hi - lo) / 2
        if (mid * mid * mid < c):
            lo = mid
        else:
            hi = mid
        if hi - lo == prev_range_size:
            break
        prev_range_size = hi - lo

    return lo

def cubicRoot(c):
    if c < 0:
        return -_cubicRoot(-c)
    else:
        return _cubicRoot(c)

This is still slow when we’re dealing with large numbers. To address it one can binary search first on the exponent, or get close to the real exponent by dividing the original exponent by 3. Try it out in the comment section.

I'm curious, did your solution have any of these problems?

notes:

• Thanks Tomek for pointing out the iteration problem and possible efficient solutions.
• When c is large, mid * mid * mid will overflow but the algorithm still works.
• We’ve addressed negative numbers, numbers in (0, 1), overflow problems, absolute and relative error problems.
• Some tests for your own code -1, 0, 1, 2, 8, 0.001, 1e30, 1e60
• In practice faster methods like Newton Rapson method are used.

Figure out an algorithm for each of the following problems. What’s the complexity? Code it.

1. Given A, a sorted int array of length n. How many times does the value x occur in A.
2. Given a real number x, find out it’s cubic root.
3. Given A a sorted array of distinct integers, find out an i such that A[i] == i.
4. Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2(x).
5. Given an array A such that A[ 0] > A[ 1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
6. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
7. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
8. Given two sorted arrays of length n and m, find out the kth element of their sorted union.
9. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.
10. Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.