Sugestii pentru probleme

[•pauldb]

In pagina proiectului, 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.

[•gabitzish1]

Ar trebui sa aveti grija la problemele astea cand fixati limitele de timp si memorie. Scopul lor este sa invete lumea algoritmii, nu jmenuri de implementare. Ati putea cere cuiva sa va ajute si cu o sursa in pascal, sa fiti siguri ca intra

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

[•wefgef]

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

[•silviug]

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

[•pauldb]

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.

[•Cosmin]

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.

[•silviug]

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.

[•wefgef]

Este in Cormen problema ciclului bitonic

[•Cosmin]

@andrei, pai ce zicea silviu

[•Marius]

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²).

[•Cosmin]

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

[•Marius]

Chiar dacă în secțiunea de articole există Probleme de acoperire 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.

[•Marius]

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

[•MciprianM]

Poate ar trebui adaugata si problema postasului chinez? 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.

[•Cosmin]

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.

[•alexa_myparadise]

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

[•SpiderMan]

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

[•S7012MY]

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

[•Cosmin]

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

[•maritim]

Din cate stiu o problema care se rezolva complet cu acest algoritm s-a dat la ONI 2008 : Virus. Eu sunt pro!

[•blasterz]

Din cate stiu o problema care se rezolva complet cu acest algoritm s-a dat la ONI 2008 : 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.

[•devilkind]

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

[•wefgef]

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

[•scipianus]

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

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)" ?  

O platforma distribuita si open pentru informatii de olimpiade cum este infoarena.ro. Poti sa fii cel mai tare din orasul tau, dar trebuie sa mai stii si smenurile clasice, ce fac altii, cum se fac anumite smenuri.. o comunitate stransa, dar distribuita, sa nu se ajunga in cazul degenerat de la ICHB.
Deja infoarena.ro e super tare ca si continut, dar eu am predat multe smenuri si probleme care nu exista aici si care ar ajuta pe multa lume.. daca se accepta ideea ca trebuie sa se share knowledge pe o platforma de genul asta ca sa fim competitivi internationali, atunci suntem abia la 1% din ce trebuie facut. O solutie simpla: fiecare profesor care preda la ICHB sa se inregistreze si sa se puna pe Youtube/Trilulilu cu embed pe infoarena. Bandwidth-ul e ieftin, video e viitorul, si e foarte low-effort pentru persoana care preda.

Ar fi foarte frumos daca s-ar realiza ce a spus Mircea Pasoi in discutia Monopol 

[•wefgef]

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)" ?  

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