Revizia anterioară Revizia următoare
Arhiva educationala 
5/5
Se propune construirea unei noi arhive de probleme care sa aiba exclusiv scop educational. Spre deosebire de probleme de concurs in care se imbina mai multi algoritmi si rezolvarea de obicei nu este evidenta, problemele din aceasta arhiva vor fi create special pentru cei care vor sa invete cum sa implementeze un algoritm sau o metoda de rezolvare anume. Se va permite accesul la teste, surse si se vor da si link-uri catre documentatie. Mai multe despre acest proiect gasiti aici.
De ce m-as baga?
1. Vei invata cum se creeaza probleme pe infoarena
2. Vei deveni cunoscut
3. Poti invata mai multe despre subiectele care le abordezi, lucrand alaturi de veteranii din echipa infoarena
4. Munca ta va ajuta mii de persoane sa invete informatica, si intreaga comunitate iti va fi rescunoscatoare
5. Toate cele de mai sus
Cum pot sa contribui?
1. Contacteaza unul din responsabilii pentru acest proiect pe forumul infoarena:
Filip Cristian Buruiana •filipb
Paul-Dan Baltescu •pauldb
Airinei Adrian •astronomy
Adrian Diaconu •DITzoneC
Andrei Grigorean •wefgef
2. Precizeaza in mesajul tau de intentie ce problema doresti sa pregatesti. Problema pe care ai ales-o trebuie sa se regaseasca in tabelul de mai jos sau poti veni cu un algoritm nou care nu e trecut in tabel, iar acesta se va completa corespunzator. Problemele nu trebuie sa fie repartizate nimanui in momentul in care sunt alese. La un moment dat un utilizator poate alege maxim o problema.
3. Dupa ce ai obtinut acordul unui responsabil de proiect, vei obtine statutul de helper. Pe langa acest statut ti se va repartiza o persoana "de legatura" din echipa infoarena, cu experienta, care sa te indrume si sa te sfatuiasca astfel incat rezultatul sa fie unul pe masura asteptarilor. Va trebui sa comunici cu persoana care te va supraveghea astfel incat sa ajungeti la un acord in privinta enuntului, structurii testelor, algoritmilor folositi. Persoana de contact din echipa iti va oferi feedback.
4. Dupa ce ai fost facut helper si ai aflat persoana care te va supraveghea, vei putea incepe sa editezi problemele. Va trebui sa redactezi enuntul, sa faci teste si eventual un evaluator. Documentatia necesara se gaseste aici.
5. In momentul in care ai finalizat o problema, ea va fi adaugata de catre un administrator in arhiva educationala. Mii de utilizatori infoarena iti vor multumi pentru initiativa ta!
Voluntari
Gabriel Bitis •gabitzish1
Florian Marcu •Florian
Tabara Mihai •Tabara
Bondane Cosmin •cos_min
Bogdan-Cristian Tataroiu •bogdan2412
Ionescu Vlad •Dastas
Sima Cotizo •sima_cotizo
nash mit •nash
Stefan-Alexandru Filip •Prostu
Tudorica Constantin Alexandru •tudalex
Cezar Mocan •CezarMocan
Bogdan-Alexandru Stoica •fireatmyself
Gavrila Vlad •GavrilaVlad
Serban Andrei Stan •savim
Florin Ghesu •floringh06
Flaviu Pepelea •Pepelea_Flaviu
Documentatie
Problemele din arhiva educationala se creeaza la fel ca orice alta problema de pe infoarena. Pentru a afla cum poti crea o problema, consulta materialele de aici. Deosebirea dintre o problema obisnuita de pe infoarena si o problema din arhiva educationala este modul in care sunt formatate.
Astfel, o problema din arhiva educationala trebuie sa respecte in plus urmatoarele reguli:
- Toate testele si sursele trimise vor fi vizibile oricarui utilizator.
- Enuntul problemei va contine o sectiune speciala numita Indicatii de rezolvare, in care vor fi precizate link-uri catre diferite articole ce trateaza tema respectiva sau carti in care este prezentat subiectul in cauza.
- Pentru problemele in care exista mai multe rezolvari, se va preciza la sectiunea Restrictii sau eventual la Indicatii de rezolvare, punctajul orientativ obtinut de fiecare complexitate sau metoda in parte. De exemplu, pentru algoritmul de drumuri minime a lui Djikstra, se poate preciza ca un algoritm de complexitate O(N2) obtine 50 de puncte, in timp ce o abordare O(Mlog2N) conduce la obtinerea punctajului maxim.
- Fiecare problema va avea si un link catre sursa oficiala, scrisa de unul din membrii echipei infoarena sau de unul din responsabilii de proiect. Linkul va fi introdus in enuntul problemei de autorul sursei sau de voluntarul pe problema.
- Optional, se pot preciza o serie de probleme de pe site-uri cu evaluator automat (infoarena, sgu, uva, timus, etc), a caror rezolvare se bazeaza pe algoritmul in cauza. Link-urile catre aceste probleme vor aparea la sectiunea Probleme suplimentare.
- De asemenea, tot optional, evaluatorul pentru problema trebuie sa returneze mesaje cat mai diverse pentru ca utilizatorii sa isi poate descoperi usor eventualele greseli.
- Aproximativ 20%-30% din testele folosite la evaluare vor trebui sa aiba dimensiuni mici astfel incat sa poata fi verificate manual.
- In momentul in care sursa oficiala este finalizata si problema este verificata de un administrator, ea va fi introdusa in arhiva educationala.
Exemple de probleme pentru aceasta arhiva gasiti mai jos:
Continutul arhivei
In tabelele de mai jos se afla cei mai importanti algoritmi care trebuie sa se gaseasca sub forma de probleme in arhiva educationala. Pentru fiecare problema este trecut si un responsabil. Responsabilul pe problema va fi cel care s-a oferit prin voluntariat sa o introduca in arhiva. El va fi cel care va scrie enuntul, va crea testele si eventual un evaluator.
Puteti veni oricand cu propuneri si sugestii de probleme noi pe forum!
Matematica:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Algoritmul lui Euclid | filipb | filipb |  1/1 |
| Algoritmul lui Euclid extins | Bogdan2412 | filipb | 1/1 |
| Ciurul lui Erathostenes | filipb | filipb | 1/1 |
| Algoritmul lui Gauss | - | - |  0/1 |
| Principiul includerii si excluderii | - | - | 0/1 |
Backtracking:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Permutari | CezarMocan | filipb | 1/1 |
| Combinari | CezarMocan | wefgef | 1/1 |
| Submultimi | CezarMocan | - | 0/1 |
Programare dinamica:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Cel mai lung subsir comun | filipb | filipb | 1/1 |
| Cel mai lung subsir crescator | Florian | - | 0/1 |
| Knapsack | gabitzish1 | - | 0/1 |
| Subsecventa de suma maxima | GavrilaVlad | - | 0/1 |
Algoritmi pe grafuri:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Parcurgere BFS | Florian | - | 0/1 |
| Parcurgere DFS - componente conexe | gabitzish1 | DitzoneC | 1/1 |
| Componente biconexe | - | - | 0/1 |
| Componente tare-conexe | Tabara | - | 0/1 |
| Sortare topologica | Tabara | DitzoneC | 1/1 |
| Lant hamiltonian | - | - | 0/1 |
| Ciclu eulerian | pepelea_flaviu | - | 0/1 |
| Arbore partial de cost minim | Tabara | - | 0/1 |
| Algoritmul lui Djikstra | Dastas | filipb | 1/1 |
| Algoritmul Floyd-Warshall/Roy-Floyd | gabitzish1 | filipb | 1/1 |
| Algoritmul Bellman-Ford | Dastas | - | 0/1 |
| Flux maxim | fireatmyself | - | 0/1 |
| Flux maxim de cost minim | fireatmyself | - | 0/1 |
| Cuplaj maxim | fireatmyself | - | 0/1 |
| Cuplaj maxim de cost minim | fireatmyself | - | 0/1 |
| Lowest Common Ancestor | devilkind | - | 0/1 |
| 2SAT | - | - | 0/1 |
Siruri de caractere:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Potrivirea sirurilor | Bogdan2412 | filipb | 1/1 |
| Arbori de sufixe | - | - | 0/1 |
| Trie | - | - | 0/1 |
Structuri de date:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Heapuri | floringh06 | - | 0/1 |
| Hashuri | - | - | 0/1 |
| Arbori de intervale | cos_min | DitzoneC | 1/1 |
| Arbori de intervale aplicatie 1 | - | - | 0/1 |
| Arbori de intervale aplicatie 2 | - | - | 0/1 |
| Arbori de intervale aplicatie 3 | - | - | 0/1 |
| Arbori de intervale aplicatie 4 | - | - | 0/1 |
| Algoritmi O(sqrtN) | - | - | 0/1 |
| Arbori indexati binar | cos_min | - | 0/1 |
| Range Minimum Query | devilkind | - | 0/1 |
| Double ended queue (deque) | - | - | 0/1 |
| Structuri de multimi disjuncte | - | - | 0/1 |
| Treapuri | Bogdan2412 | filipb | 1/1 |
Geometrie:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Intersectia a doua drepte | nash | - | 0/1 |
| Aria unui poligon | - | - | 0/1 |
| Punct in poligon | - | - | 0/1 |
| Infasuratoare convexa | nash | - | 0/1 |
| Diagrame Voronoi | - | - | 0/1 |
| Distanta minima intre doua puncte in plan | - | - | 0/1 |
| Distanta maxima intre doua puncte in plan | - | - | 0/1 |
Diverse:
| Denumire problema | Voluntar | Responsabil IA | Finalizat |
|---|---|---|---|
| Cautare binara | Florian | - | 0/1 |
| Ridicare la putere in timp logaritmic | tudalex | filipb | 1/1 |
| Evaluare de expresii | sima_cotizo | DitzoneC | 1/1 |
| Sprague-Grundy(Teoria jocurilor) | - | - | 0/1 |
| Statistici de ordine | - | - | 0/1 |
| Operatii pe numere mari | savim | - | 0/1 |
