Blog infoarena

Problem: Shoe laces

Cosmin
Cosmin Negruseri
28 aprilie 2016

Here's a probability puzzle I've learned from Alex Ku:

There are N shoe laces in a bag. A move consists of randomly picking two shoe lace ends from the bag, tying them together and then placing them back in the bag. We keep going until we can't find any shoe lace ends to tie. What is the expected number of different shoe lace cycles we'll have at the end.

P.S. Please don't spoil the problem if you've seen it before.

 Comentarii (4)

Categorii:

ONIS 2016 Runda 1 Editorial

klamathix
Mihai Calancea
08 martie 2016

Prima rundă de calificare a concursului ONIS 2016 s-a încheiat. În cele ce urmează vom prezenta o scurtă analiză a concursului, însoţită de soluţiile oficiale ale problemelor propuse.

În primul rând, felicitări câştigătorilor! Mai exact, primelor cinci echipe de studenţi în ordinea clasamentului:

1. team_nameUPB Banu Popa Visan team_name

2. mafia_unibucMafia Unibuc mafia_unibuc

3. corul_barbatescUNIBUC Kira96 lockmihai corul_barbatesc

4. lookingForAChallengeUBB Cociorva Popoveniuc Salajan lookingForAChallenge

5. The_Viper_The_Mountain_And_The_ImpUNIBUC Impaler-009 Challenge costyv87 The_Viper_The_Mountain_And_The_Imp

De-asemenea, primelor 5 echipe de liceu:

1. geniucosOncescu Costin geniucos

2. tamionvTamio Vesa Nakajima tamionv

3. andreiiiiPopa Andrei andreiiii

4. enterpriseUVS Babalau Rochian Tarniceru enterprise

5. Spiromanii_MessiUNIBUCThrowTerror Spiromanii_Messi

Încă o rundă de felicitări pentru team_nameUPB Banu Popa Visan team_name, singurii care au reuşit să rezolve toate cele 9 probleme din set şi pentru geniucosOncescu Costin geniucos, care a reuşit să iasă de unul singur pe locul 2, după ce o bună perioadă din concurs a condus clasamentul.

Concursul a început după cum era de aşteptat cu submisii la problema A. MaxSubSum. Conform tradiţiei, surprinzător de mulţi concurenţi au trimis soluţii care nu foloseau tipuri de date pe 64 de biţi. Atragem atenţia aici şi asupra faptului că tipul long nu are 64 de biţi pe platforma noastră. După cum puteţi citi (spre exemplu) aici, este o soluţie mult mai bună să folosiţi mereu tipul long long, care nu variază la fel de mult în funcţie de arhitectură. Participanţii la OJI să ia aminte :)

A urmat problema F. Pokemon, ca dovadă că enunţurile lungi/complicate nu implică neaparat soluţii lungi/complicate, o lecţie valoroasă pentru majoritatea concursurilor de informatică. Pentru idei de optimizare, puteţi citi aici despre cum operaţiile pe mulţimi se împacă foarte bine cu operaţiile pe biţi.

Problema C. Minlcm avea nevoie de observaţia că e mai productiv să iterăm peste posibilii divizori comun, decât peste un membru al perechii şi de ideea folosirii unui ciur pentru a o implementa eficient. Mai avea nevoie şi de întregi pe 64 de biţi :).

Problema D. Unlock necesita în primul rând puţină imaginaţie pentru a crea un test în care soluţia brută chiar se comportă foarte prost (idei?). Apoi, era nevoie de o soluţie care se amortiza peste mărimile tuturor componentelor colorate şi o implementare grijulie. Nimeni nu a reuşit să rezolve aceasta problemă din prima submisie, deci ar fi cazul să ne şlefuim puţin abilităţile de implementare :).

Apropo de implementare, un skill care pare să lipsească aproape universal participanţilor este acela de a-şi simplifica ideile înainte de a le implementa sau de a căuta de la început idei care să permită o implementare concisă. În cazul de faţă, problemele G. Puzzle2, B. Avioane2, E. Min Max Store şi într-o anumită măsură D. Unlock se pretau la a fi "supra-implementate".

Problema I. Nucleul Valoros 2 avea nevoie de o optimizare subtilă a recurenţei descrise în enunţ. Puteţi găsi aici un blogpost în care sunt enumerate mai multe metode utile de a optimiza anumite tipuri de recurenţe.

În continuare, aveţi soluţiile problemelor în detaliu :).

A. MaxSubSum

Algoritmul general de determinare a submatricei de sumă maximă este prea încet pentru această problemă, având complexitate O(N ^ 3). Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile (x1, y1, x2, y2), observăm că suma sa este (x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2], unde prin T[a...b] am notat suma T[a] + T[a + 1] + …. T[b]. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

În schimb, este adevărat că dacă submatricea optimă va avea X linii şi Y coloane, ne intereseaza doar subsecvenţele de lungime X, respectiv Y care au suma maximă posibilă în A şi B. Putem precalcula uşor şirul bestA[Length] = “suma maximă a unei subsecvenţe din A de lungime Length ” în timp O(N2), analog pentru şirul bestB[]. Apoi vom itera peste toate cele N2 dimensiuni posibile ale submatricei şi vom reţine maximul expresiei LineCount * bestB[ColumnCount] + ColumnCount * bestA[LineCount].

Numarul de echipe care au rezolvat problema: 73
Prima echipa care a rezolvat problema: geniucosOncescu Costin geniucos

B. Avioane2

Construim 3 tipuri de evenimente:

  • Decolare: Decoleaza avionul cu indicele X din aeroportul A la timpul Td
  • Aterizare: Aterizeaza avionul cu indicele X din aeroportul B la timpul Ta
  • Query: Raspundem la un query pentru aeroportul C, timpul Tq

Sortam evenimentele in functie de timp si simulam un algoritm de drum minim, pas cu pas in functie de ce evenimente apar. La orice moment de timp, tinem pentru fiecare nod X costul minim de a junge din nodul 1 in nodul X.

  • Eveniment query (aeroportul C): raspunsul este costul minim curent de a ajunge din 1 in C, pur si simplu trebuie afisat.
  • Eveniment de Decolare (aeroportul A): costul minim de a ajunge intr-o anumita destinatie poate sa fie modificat cu costul minim de a ajunge in momentul de fata in nodul din care decolam (nodul A) + pretul biletului pentru acest avion. In cazul in care aceasta varianta se va dovedi a fi mai buna, vom actualiza costul minim pentru destinatie in momentul aterizarii
  • Eveniment de Aterizare (aeroportul B): selectam pentru nodul in care aterizam (nodul B) cea mai buna varianta (ori pastram costul minim de pana acum, ori costul obtinut prin intermediul avionului care tocmai a aterizat, cost calculat la evenimentul de tip Decolare)
    Problema poate fi vizualizata ca si un caz particular al algoritmului de Bellman-Ford. Din moment ce avem si axa timpului, este suficient sa trecem o singura data prin muchii deoarece o muchie cu un cost mic la un anumit moment de timp nu poate afecta alte configuratii la timpi mai mici

Numarul de echipe care au rezolvat problema: 29
Prima echipa care a rezolvat problema: geniucosOncescu Costin geniucos

C. MinLcm

Folosim proprietatea: cmmmc(a, b) = a * b / cmmdc(a, b)
Din moment ce a, b <= 100.000, avem garantia si ca cmmdc(a, b) <= 100.000
Se observa faptul ca pentru un cmmdc fixat D, ne intereseaza cele mai mici 2 elemente din sir care au acest D drept divizor (pentru a minimiza a * b / D). Aceste 2 numere se pot calcula simplu pentru fiecare divizor D cu ajutorul ciurului lui Eratostene.

Obsevatie: Algoritmul fixeaza in realitate doar un divizor al celor 2 numere (fără a avea vreo garanţie că este cmmdc-ul real), dar dacă divizorul respectiv nu este într-adevăr cel mai mare posibil al celor două numere, va produce un rezultat mai mare decât cel real, deci răspunsul problemei nu va fi afectat.

Numarul de echipe care au rezolvat problema: 32
Prima echipa care a rezolvat problema: forsakenAweUNIBUC Suditu Cornoiu Chihai forsakenAwe

D. Unlock

O primă soluţie posibilă este cea de a itera pe rând prin toate cele K culori şi a efectua câte o parcurgere a matricei pentru a verifica dacă celulele libere sunt conexe. Această soluţie are complexitate worst-case O(N * M * K), iar date fiind limitările lui K, este echivalentă cu O((N * M) 2). Deşi la prima vedere ar părea că este puţin probabil ca atât K cât şi zonele atinse de fiecare parcurgere să fie de mărime Θ(N * M) simultan, există teste în care acest lucru se întâmplă, iar soluţia descrisă depăşeşte cu mult limita de timp, care, mai mult, este calibrată pentru a procesa 25 de teste, nu unul singur.

Pentru a obţine o soluţie mai rapidă, vom încerca ca pentru fiecare culoare fixată să depunem efort (i.e număr de operaţii) proporţional cu numărul total de celule de această culoare. Deoarece în total acest număr este limitat de N * M, complexitatea ar fi şi ea proporţională cu această valoare. Pentru a construi o asemenea soluţie, vom face pentru început nişte parcurgeri care vor identifica zonele conexe de celulele libere. Apoi, pentru fiecare culoare fixată, fie ea C, vom face o parcurgere pentru fiecare componentă conexă de culoare C şi vom reţine cu ce zone conexe libere este vecină fiecare astfel de componentă. Dacă o anumită componentă Comp de culoare C este vecină cu zonele libere “x1, x2 .. xT”, atunci aceste zone vor deveni conectate în momentul în care o facem pe Comp accesibilă. Astfel, pentru fiecare componentă îi putem uni vecinii cu o structură de date eficientă (de tip păduri de mulţimi disjuncte), iar la final trebuie ca toate zonele libere iniţiale să fie conexe. Pentru a justifica faptul că numărul de operaţii este proporţional cu mărimea componentelor de culoare C, observăm faptul că fiecare zonă liberă vecină cu o anumită componentă trebuie să fie adiacentă cu componenta respectivă pe cel puţin o latură a unei celule din componentă. Deoarece numărul de laturi al unei componente conexe este limitat de 4 * (mărimea componentei), rezultă că numărul maxim de vecini distincţi posibili este limitat de aceeaşi valoare.

Este nevoie de o implementare atentă pentru a menţine complexitatea dorită. Spre exemplu, reiniţializarea completă a pădurilor de mulţimi disjuncte pentru fiecare culoare poate duce din nou la timp O((N * M)2), chiar dacă restul algoritmului este eficient.

Numarul de echipe care au rezolvat problema: 15
Prima echipa care a rezolvat problema: UNIBUC_Costan_Iordache_MagureanuGangster Teddy Bears Trio UNIBUC_Costan_Iordache_Magureanu

E. MinMaxStore

Se observa faptul ca proprietatea este independenta pentru minim si maxim.

Initial consideram ca toate cele N valori sunt posibile minime. In momentul in care avem o operatie Store(A, B), aplicam urmatorii pasi:

  • Daca A este posibil minim, ramane posibil minim
  • Daca A nu este posibil minim, acesta devine posibil minim doar daca B este posibil minim.
  • B nu mai poate sa fie minim orice ar fi

La sfarsit proprietatea este adevarata daca avem un singur posibil minim si acesta se afla pe pozitia indicata. Analog facem si pentru maxim si raspundem la fiecare din cele 4 cazuri in functie de corectitudinea celor 2 raspunsuri.

Numarul de echipe care au rezolvat problema: 30
Prima echipa care a rezolvat problema: echipa_BoSSilorUNIBUC Harsan Bicsi Baltatu echipa_BoSSilor

F. Pokemon3

În ciuda enunţului mai complex, aceasta este una dintre cele mai simple probleme la nivel algoritmic. Deoarece numărul de tipuri de pokemon este mic, putem itera prin toate submulţimile posibile de pokemoni şi verifica pentru fiecare submulţime dacă aceasta asigură victoria. Pentru a se încadra în timp, soluţia trebuie să codeze submulţimile ca măşti de biţi şi să facă verificarile folosind operaţii pe biţi pe aceste valori. Complexitatea finală este O(2 N * N).

Numarul de echipe care au rezolvat problema: 69
Prima echipa care a rezolvat problema: team_nameUPB Banu Popa Visan team_name

G. Puzzle2

Problema admite multe soluţii, care variază mai ales ca dificultate a implementării. O soluţie rezonabilă vine din observaţia că o dată ce am aflat prima linie a matricei, restul matricei se poate reconstitui cu uşurinţă, linie cu linie. Pentru a construi prima linie, putem începe dintr-un colţ (un nod cu 2 vecini) şi parcurge numai noduri de margine (care au 3 vecini) până găsim un alt colţ. Dacă alegem să facem acest lucru, trebuie să tratăm special cazul matricelor cu 2 linii (sau coloane), deoarece în acest caz parcurgerea nodurilor de margine poate alterna haotic între cele două linii, fără ca lanţul obţinut în final să fie o linie reală a matricei. Cazul se tratează uşor, observând că acum un colţ este vecin direct cu cel puţin un alt colţ. Cele două colţuri vor forma singure prima linie, iar acum putem reconstitui restul matricei ca în cazul general. Un alt caz particular, dar foarte simplu, este cazul unei matrice cu o singură linie.

Numarul de echipe care au rezolvat problema: 21
Prima echipa care a rezolvat problema: geniucosOncescu Costin geniucos

H. Subpermutari

Consideram toate cele N2 subsecventele are permutarii noastre. Observam faptul ca daca pentru o secventa [a,b] determinam cea mai lunga subpermutare care este atat prefix, cat si sufix a secventei noastre, putem foarte usor marca sufixul ca fiind o secventa care a mai aparut deja si crestem frecventa prefixului.
Pentru a determina cea mai lunga subpermutare care este atat prefix, cat si sufix, vom aplica un algoritm foarte asemanator KMP-ului:
Fixam pozitia de start a subsecventei noastre si pornim algoritmul de KMP de acolo.
Presupunem ca avem calculat pentru o subsecventa [a,b] acest cel mai bun prefix-sufix (il notam identic ca la KMP cu pi[b]). Cand vrem sa trecem la urmatorul element, b + 1, avem aceleasi 2 cazuri de luat in considerare ca si la KMP:

Cazul in care elementul inserat b + 1 are aceelasi indice in subpermutarea sufixului ca si urmatorul element in subpermutarea prefixul: pur si simplu pi-ul creste cu 1
Daca indicele difera, micsoram pi-ul (mergem in pi[pi[b]]) si repetam procedeul pana avem o potrivire

Pentru a determina al catelea element se afla o valoare intr-o secventa putem usor precalcula cu un simplu aib.
Complexitate: O(N2 log N)

Numarul de echipe care au rezolvat problema: 2
Prima echipa care a rezolvat problema: geniucosOncescu Costin geniucos

I. Nucleul Valoros Season 2

Pornim de la solutia brute, programare dinamica in O(N3).
D[i][j] = costul minim al secventei [i,j]. Recurenta este data in enunt: fixam un k de la i la j - 1 si luam cea mai buna varianta
Notam pentru un interval [i,j], valoarea k pentru acest interval drept optim[i][j].

Prima proprietate foarte importanta este faptul ca: optim[i][j - 1] <= optim[i][j] <= optim[i + 1][j]
Intuitiv este foarte usor de vizualizat acest lucru:
Daca am secventa [i, j - 1] si adaug un element nou in dreapta, k se poate muta doar la dreapta
Daca am secventa [i + 1, j] si adaug un element nou in stanga, k se poate muta doar la stanga
O sa demonstram ca daca facem for dupa k de la optim[i][j - 1] pana la optim[i + 1][j], in loc sa il facem de la i la j, obtinem complexitate O(N2).

Demonstratie: Consideram toate intervalele de lungime x. Avem proprietatea optim[a][b - 1] <= optim[a][b] <= optim[a + 1][b] si optim[a + 1][b] <= optim[a + 1][b + 1] <= optim[a + 2][b + 1], unde b - a + 1 = x. Observam ca sfasitul unui interval de lungime x este inceputul urmatorului interval de lungime x. Amortizat, obtinem O(N) pentru fiecare lungime x de interval, O(N2) in total.

Numarul de echipe care au rezolvat problema: 13
Prima echipa care a rezolvat problema: team_nameUPB Banu Popa Visan team_name

 Comentarii (0)

Categorii:

AGM 2016

xtreme77
Patrick Sava
05 martie 2016

Am placerea de a anunta faptul ca povestea merge mai departe ! Dupa o prima editie in care initiativa unui grup restrans de oameni (si in special de elevi) din Colegiul National "Spiru Haret" din capitala a fost sustinuta de Youth Bank, Concursul National de Informatica "Adolescent Grigore Moisil" revine cu o a doua editie, de data aceasta cu mentiunea ca acum este inclus acum în Calendarul Concursurilor Naţionale Şcolare ale MECS. Cea de-a doua editie va avea loc pe 26 martie..

De mentionat este faptul ca acum, la sustinerea concursului, contribuie patru mari companii din Romania : Emag (prin Fundatia Emag), Siveco Romania , Qualitance si Rodl & Partner. Evident, invariantul in toata aceasta poveste este comunitatea Infoarena care continua sa sprijine organizarea concursului si sa incurajeze initiativele similare!

Acest concurs se desfasoara pe format ACM-ICPC, noutatea fiind data de faptul ca se adreseaza elevilor de liceu. Echipele pot fi de maxim 3 elevi (toti membrii unei echipe fiind, obligatoriu, legitimati la acelasi liceu).

Neconventional este si modul in care concurentii vor fi cazati: acestia vor beneficia de cazare in familile voluntarilor din Colegiul National "Spiru Haret", acest lucru insemnand conditii mult mai bune decat ceea ce am fi putut obtine la un camin din Bucuresti cat si garantia sigurantei concurentilor pe toata durata desfasurarii concursului.

Legat de numarul de echipe participante, pot spune ca acesta este unul mai mult decat generos, in concurs fiind primite 25 de echipe. Din cauza faptului ca laboratoarele liceului nu permit un numar mai mare de echipe participante, concursul va fi si online, gazduit de Infoarena.

Link-ul pentru inscriere este : http://goo.gl/forms/WIXIU3SsyP

Termenul limita pentru inscriere este 15 martie.

Site-ul competitiei este : http://agminformatica.wix.com/agminfo

Tin sa le multumesc sponsorilor (Siveco Romania si Fundatia Emag), lui freak93Adrian Budau freak93, klamathixMihai Calancea klamathix si eudanipEugenie Daniel Posdarascu eudanip (care ne-au sarit in ajutor cand a venit vorba de organizarea concursului si care ne-au sprijinit initiativa), dar si celor 6 membrii ai comisiei stiintifice din care fac si eu parte : florin.elfusFlorin Chirica florin.elfus, retrogradLucian Bicsi retrograd, ericptsStavarache Petru Eric ericpts, george_stelianChichirim George george_stelian, teoionescuIonescu Teodor teoionescu si PlayLikeNeverB4George Marcus PlayLikeNeverB4. De asemenea, un merit important in organizarea concursului il are directiunea Colegiului National "Spiru Haret" care s-a implicat foarte mult in dezvoltarea acestui proiect.

Numai bine si keep coding!

 Comentarii (0)

Categorii:

Problem: Marble Game - Solution

Cosmin
Cosmin Negruseri
21 februarie 2016

Here's the statement again:

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

Solution:

The state with all marbles in the first cup can always be reached. (1)

While we can find another cup with marbles, we apply one move on that cup. Marbles will move around the circle and from time to time fall into the first cup. Since we never make a move on the first cup, eventually all the marbles will end up in it. You guys figured this part in the comments.

Every state A has n outgoing edges (they can be self edges). (2)
We can apply one move on each cup.

Every state A has n incoming edges (self edges included). (3)
Here's an example: Let A be 0 1 2 1 0 0.
We can reach this state from 0 1 2 1 0 0 applying a move on cup 1 (self edge), 3 0 1 0 0 0 applying a move on cup 1, 2 0 1 1 0 0 applying a move on cup 1, 1 0 2 1 0 0 applying a move on cup 1, 0 1 2 1 0 0 applying a move on cup 5 (self edge), 0 1 2 1 0 0 applying a move on cup 6 (self edge)

From (2), (3) the graph is Eulerian, from (1) the graph is also connected. It follows that we have an Eulerian cycle that goes through all edges and nodes. Which means we can reach any state from any other state.

Thanks Andrei Dragus for the neat problem.

 Comentarii (2)

Categorii:

Our bad :(

klamathix
Mihai Calancea
11 februarie 2016

Regretăm să vă anunţăm că soluţia oficială a problemei Tembelizor de la Runda 2 a Algoritmiadei este greşită. Mai mult decât atât, nu am reuşit să găsim o soluţie corectă care să rezolve problema pentru restricţiile date în concurs. Ne-am aflat astfel într-o poziţie dificilă, întrucât orice decizie ar fi afectat negativ anumiţi concurenţi. În final, am decis să scoatem problema complet din clasament, runda are astfel un punctaj maxim de 300 de puncte şi nu va influenţa ratingul. În acelaşi timp, pentru a atenua pe cât posibil efectele acestei decizii asupra calificărilor în finală, am hotărât să organizăm şi Runda 4 a concursului, într-o perioadă ce urmează a fi determinată.

Suntem foarte dezamăgiţi de ce s-a întâmplat şi ne cerem scuze tuturor participanţilor pentru dificultăţile create :(.

 Comentarii (9)

Categorii:

Problem: Marble Game

Cosmin
Cosmin Negruseri
31 ianuarie 2016

Andrei Dragus told me this cute puzzle a year or two ago.

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.

 Comentarii (3)

Categorii:

Central European Olympiad in Informatics 2016 - Call for Tasks

klamathix
Mihai Calancea
29 ianuarie 2016

Punem în atenţia voastră anunţul comisiei CEOI 2016 în legătură cu propunerea subiectelor, anunţ publicat iniţial pe olimpiada.info.

CEOI 2016 - Call for tasks !

Comisia stiintifica a CEOI va invita sa propuneti probleme pentru competitia ce va avea loc in 2016, la Piatra Neamt! Problemele propuse trebuie sa fie de natura algoritmica, dar pot fi de orice tip: clasice, interactive sau output-only. Pentru a asigura o competitie cinstita, problemele propuse trebuie sa respecte urmatoarele reguli (similare cu cele de la IOI):

- Problemele trebuie sa nu fie sau sa fi fost vazute de vreun potential participant la CEOI 2016.
- Problemele trebuie sa nu fi fost propuse intr-o competitie similara (online sau on-site).
- Problemele trebuie sa fie rezolvabile de concurenti intr-un timp de maxim 5 ore.
- Enunturile trebuie sa fie clare si usor de inteles.
- Problemele trebuie sa fie originale si/sau inovative.

Pentru a fi acceptata, o propunere de problema trebuie sa contina urmatoarele:

- Enunt in limba romana, in plain-text sau PDF;
- Descrierea solutiei care obtine punctaj maxim (preferabil si solutii partiale);
- Adresa de email a autorului;
- CV-ul autorului, care sa contina si un scurt rezumat al activitatii acestuia in domeniul informaticii.

Toate aceste fisiere trebuie arhivate in format .zip (o singura arhiva !)
Daca submisia va trece de selectia initiala, propunatorul va fi rugat sa trimita si:

Sursa care implementeaza solutia optima + surse care obtin punctaje partiale
Teste si generator de teste
Va asteptam sa trimiteti problemele pe adresa ceoi-2016-call-for-tasks [at] googlegroups [dot] com.

Termenul limita este 31 mai pentru CEOI. Problemele trimise inainte de 30 aprilie vor fi luate in considerare pentru CEOI si loturi, in timp ce problemele trimise inainte de 31 martie vor fi luate in considerare pentru CEOI, loturi, ONI si baraj.

Spor la compus! :)

 Comentarii (0)

Categorii:

Problem: Prime Number Generator

Cosmin
Cosmin Negruseri
25 ianuarie 2016

A while back Ovidiu Gheorghioiu told me this neat problem:

How would you build an efficient prime number generator?

Let the generator be an object G with the method nextPrime(). When we call it G.getNextPrime() the first time it returns 2. Every time we call it again it returns the next prime number.

So if we do:
G = PrimeGenerator()
print G.nextPrime()
print G.nextPrime()
print G.nextPrime()

We'll get
2
3
5

 Comentarii (11)

Categorii:

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: freak93Adrian Budau 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 (3)

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