infoarena

In pagina proiectului (http://infoarena.ro/implica-te/arhiva-educationala), apare o lista de probleme ce urmeaza sa fie adaugate in arhiva educationala. Aceasta lista este incompleta.
In acest topic, sunteti invitati sa aduceti idei pentru completarea listei.

Va reamintesc ca arhiva educationala pune accent pe algoritmi, metode de programare, structuri de date, etc., nu pe rezolvarea problemelor de informatica. Pentru a contribui cu probleme de informatica, documentati-va aici (http://infoarena.ro/implica-te/extinde-arhiva).

Ati putea baga niste probleme pt jmenuri... (optimizari de memorie.. timp.. etc).

Cred ca mai degraba ar merge facuta o sectiune speciala: "C++ pentru concursuri" - unde sa inveti sa implementezi. Aici s-ar potrivi si probleme de optimizari. Poate ca daca vom avea timp vom face asa ceva :)

Mi-a trecut si mie prin cap cateva idei de probleme clasice:

- Coduri Prufer: cum faci cod Prufer din arbore; cum obtii arborele din cod Prufer; ambele O(N)
- DFS cu timpi de intrare/iesire. Query-uri de stramosi. Asta e deja in arhiva though (de pe Lista lu' Francu).
- Dinamici clasice: parantezare optima, bitonic sequence (alea de prin Cormen in principiu); una sa exemplifice si memoizarea.
- Sortari: sortare prin numarare, radix sort

Ca o idee generala, problemele din Cormen (cele explicate in text si aplicatiile de la sfarsit de capitol) sunt o buna sursa de inspiratie de probleme clasice. Trebuie filtrate/impartite alea care implica mai multe lucruri deodata. Oricum  am vazut ca deja e ditai lista de idei, deci nu duceti lipsa de material de lucru :)

Keep up the good work!

Silviu

Multumim pentru completari. Asteptam idei noi!

Imi poti explica ce e bitonic sequence? Eu n-am auzit de ea si pe google gasesc alte chestii.

O sa luam si Cormenul la puricat cand ramanem fara idei. :)

Ciclu bitonic nu secventa bitonica. E problema in care trebuie sa gasesti ciclu de cost minim in plan care trece prin n puncte date cu restrictia sa mearga intai de la stanga la dreapta si apoi de la dreapta la stanga. S-a dat si la IOI in 93.

Asa, zice bine Cosmin. S-a dat si la o regionala de-a noastra mai recent.

E o problema draguta de PD care, cred eu, a devenit clasica.

Este in Cormen problema ciclului bitonic :)

@andrei, pai ce zicea silviu

Am vorbit cu Filipb despre următoarea problemă, dar postez și aici: să se determine câte cuplaje maxime sunt într-un graf bipartit. Se rezolvă cu programare dinamică în O(2^N N²).

E mai bun exemplul clasic cu cel mai scurt ciclu hamiltonean in O(n^2 2^n)

Chiar dacă în secțiunea de articole există Probleme de acoperire (http://infoarena.ro/probleme-de-acoperire-2) nu cred că ar fi rău să existe o problemă care combină programarea dinamică cu backtrackingul. Un exemplu ar fi „În câte moduri se poate acoperi o tablă cu dominouri / alte piese”. Sau poate o altă problemă, nu știu.

Nu ar merge și numerele lui Stirling, implementate cu modulo sau cu numere mari? Cred că ar fi util de știut ce semnifică ele.

Poate ar trebui adaugata si problema postasului chinez? http://en.wikipedia.org/wiki/Route_inspection_problem (ftp://http://en.wikipedia.org/wiki/Route_inspection_problem)
Astazi am intalnit-o din nou dupa ce am facut-o in semestrul intai la facultate si ma gandeam ca ar intra la "clasice". Daca vreti ma ocup eu, ca oricum sunt in vacanta.

Exista deja problema acolo http://infoarena.ro/problema/traseu

Cred ca ar trebui sa fiti atenti ce probleme adaugati la arhiva educationala.

In principiu vrem algoritmii de baza ce sunt prin carti de algoritmica nu si aplicatii ceva mai complicate ale lor. Nu vrem sa fie arhiva prea mare, ci sa fie mica si utila pentru cineva care vrea sa invete algoritmii de baza.

De exemplu numerele stirling nu cred ca au super multe aplicatii prin problemele de info sau sunt o notiune asa de importanta deci ar fi o problema ce nu e esential sa fie in arhiva educationala.

In schimb un articol despre subiecte ca problema postasului chinez sau numerele stirling ar fi interesant.

 Sau ar mai putea fi adaugat si Principiul lui Dirichlet sau Taietura minima intr-un graf cu costuri. :D

M-am gandit pentru inceput sa facem o problema cu numerele mari, gen -, +, /, *. Pneutr inceput cam atata am, o sa revin si cu alte propuneri

As putea sa adaug aho-corasick
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

nu cred ca are rost adaugat aho corasik, cate probleme din arhiva se rezolva cu el?

Din cate stiu o problema care se rezolva complet cu acest algoritm s-a dat la ONI 2008 : Virus (http://infoarena.ro/problema/virus). Eu sunt pro!

Problema Virus se putea rezolva de 100 si cu Suffix Arrays in O(n log n).
Cred ca Suffix Arrays sunt mult mai folositori decat Aho Corasik.
Virus e singura problema pe care o stiu cu Aho Corasik, in schimb probleme
cu Suffix Arrays sunt mai des intalnite.

Mai exista problemele care se rezolva cu Aho CoharisiK. On the top of my head:
- strigat de pe infoarena
- censored de pe TIMUS

Eu nu vad ce ar cauta un algoritm atat de avansat precum Aho Corasik in arhiva educationala. In concursuri oricum nu il intalnesti prea des si pana la urma scopul arhivei este sa ii ajute in principal pe cei aflati la inceput de drum sa invete lucrurile de baza.

P.S.: Eu nu stiu Aho Corasik :P

Da,corect,in mare parte arhiva educationala contine algoritmi de baza si este pentru cei aflati la inceput. Dar atunci unde este "arhiva pentru olimpici (pentru cei care au cam depasit stadiul de inceput)" ?  :)


Ar fi foarte frumos daca s-ar realiza ce a spus Mircea Pasoi in discutia Monopol (http://infoarena.ro/forum/index.php?topic=5977.0) :thumbup:

O găsești în stînga, sub numele de ”Arhiva de probleme” ;)

Bun  :shock: Eu ma refeream la o arhiva cu probleme clasice care se rezolva cu acei algoritmi,cu explicatia algoritmilor data,la fel ca la Arhiva educationala  :)

Stie si wef probabil la ce te refereai. Ideea e ca nu prea gasesti tutoriale care te invata 'sa fii bun'. Gasesti tutoriale care sa te introduca in diverse subiecte si acopera anumite domenii particulare. Problemele grele nu imbina 3 algoritmi dintr-o arhiva. Daca ajungi la nivelul la care simti ca-ti mai lipseste doar sa stii Aho sau orice alta chestie marginala care apare o data la 4 ani la lot, fii sigur ca il poti invata si fara sa il ai in arhiva educationala.

Vad ca majoritatea lumii e impotriva adaugarii in arhiva. Pentru ca am primit acordul eu am terminat-o de adaugat. Am observat printre olimpici curentul: ,,Nu-mi trebuie la oni nu invat". Din pacate si eu gandeam asa dar eu zic ca nu era bine (cel putin pentru mine). Nu cred ca e vorba de a invata doar aho corasick ci trebuie sa intelegi ideea din spatele algoritmului  si astfel sa-ti dezvolti gandirea (eventual mai vezi si frumusetea ideii). De exemplu daca intelegi kmp poti sa intelegi foarte usor si aho. Mie nu mi se pare nimic complicat, din contra vezi ca trie-ul mai poate fi folosit la altceva decat aplicatia clasica.

Eu zic ca unii trateaza gresit arhiva educationala. Nu mi se pare ok sa faci toata arhiva(aici am gresit si eu) doar ca sa stii sa aplici toti algoritmii de acolo dar daca se schimba ceva in datele problemei sa nu fii in stare sa mai rezolvi problema. Si chiar daca invatarea de pattern-uri ar fi o strategie buna tot s-ar pierde din frumusetea informaticii si te-ai transforma intr-un robotel de recunoastere de pattern-uri.

Cred ca ar fi o idee foarte buna impartirea arhivei educationale in mai multe sectiuni pentru ca fiecare sa stie ce sa lucreze. Am cautat destul de mult pe net si n-am gasit nici un material in romana despre aho iar nici cel de pe wikipedia nu mi se pare foarte bine explicat.

Pot sa ma ocup de decodificarea din Cod Pruffer in Arbore, am vazut ca e pe lista de TO DO.

Dupa mine, decodificarea din Cod Pruffer e exact genul de lucru care nu are ce cauta in Arhiva Educationala. E mult mai folositor daca te gandesti la ea ca puzzle, singur, decat sa-l iei de-a gata ca ceva ce se presupune ca e basic knowledge, aparent.

Arhiva educationala si-a construit imaginea unei colectii de algoritmi clasici. Se impune ideea ca sunt si foarte folositi, dar si destul de greu de gasit fara ajutor (Intr-adevar, nu trebuie sa reinventam roata si sa incepi sa cauti algoritm pentru flux. O sa dureze.).

Decodificarea din Cod Pruffer nu e nicuna din chestiile astea. Nu e deloc vorba ca 'nu-mi trebuie fiindca nu se da la ONI'. E vorba ca daca muti un algoritm de la categoria 'obscuritati descoperite facand problema 24565 de pe PKU' la categoria 'Algoritmi clasici' lumea pur si simplu nu o sa-l digere cum trebuie. E o exagerare bineinteles, dar catre asta se tinde.

Poti invata un copil de a 7-a formule de integrare. Dar daca crede ca a invatat analiza, n-ai rezolvat nimic.

http://infoarena.ro/training-path

Lista asta e foarte buna  :) Iei contactul cu lucruri de care nu ai auzit si poti sa faci putin research.

P.S Codurile Pruffer si ideea de a realiza bijectii in scopul numararii in general sunt foarte tari. Google'em.

Cu aho corassick poti face pattern match 2d in N^2. Nu cred ca poti face altfel atat de repede. E oarecum util dar singura noastra problema de pattern match 2d se poate rezolva in N^3.

<rant>
Ar trebui filtrata arhiva educationala nu sa contina prostii care nu sunt utile.

Exista valoare in filtrarea informatiei bune nu doar in volum.
Daca faci o problema pentru cei 4 oameni care se duc la IOI nu ai prea ajutat infoarena mult, doar ai facut siteul mai greu de folosit.

Numere stirling are 0 aplicatii da e bagata acolo.
Aho Corasic a fost la un concurs sau 2 in ultimii 5 ani.
Problema cu elemente majoritare, e scris deja un articol, nu apare in nici un concurs, eventual ar merge ca problema de interviuri nu problema  in arhiva educationala.
Suma si numarul divizorilor, o aplicatie.
Cele mai apropiate puncte in plan are o singura aplicatie care e o problema propusa de mine la codejam. Nu cred ca o sa vedeti alta problema inrudita cu asta prea curand la un concurs sau ideea aplicata in alt context, desi solutia in sine e misto.

Daca stiti probleme misto, mai bine organizati un concurs. Daca o idee apare de destule ori poate ajunge destul de importanta de adaugat in arhiva educationala.

E ok sa adaugi ceva care are putine aplicatii, dar poti face asta prin un articol, prin un blog post nu prin facutul arhivei educationale de la ceva de un ordin digerabil de oricine in o vacanta de iarna ca 50 de probleme la 1000 cum e acum arhiva principala.

Sa faci un lucru doar pentru ca poti, sau doar ca sa ai si tu o problema pe infoarena nu e un motiv extraordinar.

Siteul are multa informatie si problema esentiala e cum poate fi folosit mai bine, nu ca un continut obscur nu e deja acolo.
</rant>

Cosmin, vom discuta la urmatoarea sedinta aspectele enuntate de tine.

Pomenise la un moment dat Robert despre introducerea in arhiva educationala a unei probleme care sa fie axata pe operatii cu numere mari. Ar fi foarte utila ... s-a mai facut ceva?

Nu stiu cat de utila ar fi, avand in vedere ca este deja in articolul cu multe smenuri (http://"http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai"), mai degraba adaugat ceva cu radical (cautare binara) si impartire (poate chiar si Karatsuba).

Ati putea adauga, va rog frumos, problemele ce s-au dat anul acesta (2014) si anul trecut (2013) la OJI in arhiva de probleme?  :D

Si eu vreau acelasi lucru:D

Ma gandeam ca ar fi frumos daca si triangularea unui poligon simplu ar fi introdusa , oare are releventa pentru arhiva educationala?