infoarena

Care sunt problemele care v-au placut cel mai mult... ?
Care sunt problemele care v-au facut sa spuneti "Ia uite BAH ce marfa se rezolva asta... Ia sa bag o sursa"

Scrieti aici un top #5
Eventual motivati alegerile...

Nu neaparat in ordinea importantei..

Aladdin - Chiar daca inca nu am facut-o de 100p (inca) imi place ideea de rezolvare
Invsort - Foarte draguta ideea de rezolvare. Interesanta abordare a Quicksort-ului
Traseu - Am invatat flux de la problema asta
Tri - Problema care a necesitat multa gandire... si putin ajutor .. si niste formule de geometrie.. si niste AVL-uri... destule...
Xormax - Smechera ideea cu Trie-ul.. traiasca Paftenie :)

Mai sunt si altele care ar trebui mentionate.. dar... am zis sa fie top #5 deci sa ne limitam doar la 5 :)

Dupa parerea mea ( subiectiva bineinteles ):

134 - Balans - pentru ca imbina mai multe tehnici utile prin concursuri, cautare binara + deque
206 - Arbore - pentru ca te chinui mult la o rezolvare O(log N) / query, cand de fapt e O(sqrt N) / query - prima problema pe care o stiu care merge in O(sqrt N) si nu merge O(log N) ( deocamdata )
182 - Popandai - pentru ca ideile de aici merg folosite in mai multe probleme de geometrie ( sau invers :) )
222 - Aladdin- pentru ca initial am fost dezamagit ca nu stiu sa rezolv o problema aparent atat de simpla, dar care s-a dovedit mult mai grea decat m-am asteptat :wink:
135 - Dreptunghiuri - ideea e draguta, daca nu te prinzi de la inceput trebuie sa faci brute in... O(N^8)!

Mai sunt si altele f. bune, dar acestea mi-au venit primele in minte... Da, vorba lu' cimi... Si A+B merita... Doar ea e Big-Bang-ul arhivei infoarena...  =D>

Count - sentimentul ala enuntat de ditzone "Ia uite BAH ce marfa se rezolva asta... Ia sa bag o sursa"
Gard - dinamica simpla careia, cu o chestie mica si inteligenta,  i se reduce complexitatea
Hotel - analog "Count"
Overlap - aparent complicata, se rezolva cu o idee super simpla  :aha:
Secventa3 - nostalgia primului preoni pe infoarena  :roll:

Sunt multe foarte misto, preferatele mele ar fi (presupun ca nu pot sa zic probleme proprii :) ):
Fractii - pentru solutia foarte scurta cu includere si excludere
Cerere - pentru ca e o problema care pare dura si se poate rezolva cu un dfs
Delay - pentru solutia mea cu jmenu lui mars
Otilia - pentru folosirea deque unde nu m-as fi asteptat, adica la o problema de teoria jocurilor
si Ciclu - a fost intr-un fel deschizatoare de drumuri in problemele ce folosesc cautare binara.

fractii
stramosi (cerere implicit :P )
grupuri
tabela (cand am vazut formula am ramas  :shock: )
sortnet (mie mi-a placut ideea, chiar daca tot iau 0... e prima problema care m-a facut sa stau in fata Cormenului pana am inteles ce voiam)

1. Telegraf
2. Aladdin
3. Zaharel
4. Tri
5. Soc

E cam greu de ales dar hai sa zicem:

194 Invsort (poate preferata mea) - e neasteptat cum scoti din cazul 0-1 ceva general si decat modifici un pic qsort-ul.
072 Tri - nu e nevoie de AVL-uri, doar de niste randomuri inteligente. Sper sa nu se supere lumea pe solutia mea.  :)
022 Perle - mi-a placut mult la OJI.
042 Xor Max - pentru modul in care trebuie sa folosesti un arbore.
079 Frac - pentru aplicarea desteapta a principiului incluziunii si excluziunii.

Nu se poate sa nu primesca mentiuni si: Indep, Secventa Farey, Siruri, Rubarba, Soc, Munte.

traseu
delay
cerere
arbore
a+b

E cam sec asa, ar trebui fiecare sa isi motiveze putin ce i-a placut la fiecare problema.

1. Aladdin - mi-am batut o saptamana capu cu ea, n-am produs nimica :) si pana la urma avea o solutie super tare si (aparent) ne-intuitiva
2. Caraibe - cu toate ca nu era prea grea, sunt dragute problemele astea de gandire
3. ADN - foarte utila la vremea ei, foarte fericit ca mi-a mers pe atunci :)
4. Xormax - subscriu la ce-a zis Adi
5. Soc - alta idee marfa

Mentiuni speciale (in afara topului): PetSoft, Poligon, Algola, Tri, Otilia, Soldati, Siruri. Ce sa fac daca sunt atatea probleme tari pe infoarena ?  8)

Sunt multe probleme tari pe infoarena. Uneori chiar prea tari :)

La categoria "mama ce problema tare.. hai sa fac o sursa" intra toate problemele mele ca .. deh .. a trebuit sa fac surse la ele  :-k

Hai sa vedem ce mi-a placut mie.. in general probleme care stralucesc.. care au solutii marfa, intuitive si care fac placere rezolvitorului sa le descopere spre satisfactia si bucuria lui :)

In aceasta categorie pot sa enumar linistit o groaza de probleme.. Rezumandu-ma la cinci (toate fiind pe picior de egalitate in sufletul meu):

xormax - idee inedita, cute and shining
soc - Mugurel e recunoscut pentru problemele cool iar asta este one of his bests
tri2 - din categoria "uite ca si geometria poate fi marfa"
sortnet - cool ideea Patrascu TM
invsort - singura problema pe care n-am rezolvat-o la selectie in 2004 :P
alladin - as fi nedrept daca nu i-as recunoaste calitatile de bright mind ale lu Cosmin; cool problems dude
arbore - very cute (mai ales daca ai STL :P)

Eh.. au fost 7 in loc de 5.. I couldn't help myself

Tabela: rezolvarea recursiva mi s-a parut super tare( nu mai facusem asa ceva pana atunci)
Munte: dinamica in 4 dimensiuni... wow( ... )
Lacate: mi s-a parut o problema care necesita multa logica
Cerere: o problema care parea clasica de LCA a tzapit pe multa lume( si pe mine printre altii)
Critite: presupunea intelegerea fluxului nu doar cunoasterea algoritmului
Mai sunt cateva care mi-au placut dar trebuie sa ma rezum la 5... :(

Poligon: pt. ideea marfa si usurinta implementarii
Secventa3: super idee, cu multe 'surori' [ vezi ciclu ]
Arbore: citat domino : "Tii pe biti 1000000 de valori pe bucati de sqrt(N)" :)
ADN: problema de baza, te trece prin X algoritmi
Otilia: vezi explicatia 'Cosmin'.

Nu am rezolvat foarte multe. Am intrat de curand pe site-ul asta dar mi-au placut::
1) Copaci- o multime de formule de geometrie interesante
2)Regine - mai multe tipuri de back pana mi-am dat seama de o solutie plauzibila
3) Fractii- Are foarte multe cazuri particulare din ce se maresc valorile
4)Coins- m-am chinuit s-o rezolv folosind numai lucru pe biti si am luat 100 la prima sursa
5)Fold - O idee nice pe care nu am gasit-o foarte usor

094Hotel -misto ideea cu arborele binar
098Parcela -ii faina ideea chiar daca inca n-am avut timp s-o implementez
217Popandai2 -la Moisil nu imi trecea prin minte ca ar merge cu o cautare binar si am facut brute force
025Munte -la momentul cand am rezolvat-o mi se parea cea mai grea problema de dinamica pe care am facut-o
084Algola -inainte sa o fac nu credeam ca se face asa usor mi se parea chiar imposibila

din seria "ce marfa se rezolva, ia sa bag o sursa" - soc si caraibe.
aladdin - ptr ca nu m-as fi prins de ea niciodata :P.
ferma - ptr multitudinea de solutii bune.
ADN - folosesti multe chestii utile si in alte probleme.

mentiuni : consiliul tribului - jmenar patrascu asta.
               pscpld - idee cool.

Misto threadul pana acum  :ok: Hai mai ziceti si altii ;).

Desi nu am facut foarte multe problema, acestea sunt acelea mi-au placut cel mai mult:
[in ordinea cronologica :), ceva mai multe de 5  :-' ]


Indep - Misto problema  :thumbup:
Car - Interesanta ideea cu lee-ul si cu codificarea
Cerere
Concert - Destul de dubioasa dinamica...mi-a luat ceva sa ma prind  :-k
Drumuri
Zebughil
Adapost 2 - Uite o problema la care am invatat ceva nou [chiar de pe forum]
Domino
Path
Pscpld - Interesanta ideea...si destul de intuitiva

Cred ca top 5 ar arata asa: Car, Indep, Zebughil, PscPld, Domino.

Cele mai tari probleme dupa parerea mea (in ordine aleatorie):

Algola - flux tare
Xor Max - prima oara cand am auzit de trie
Pscpld - super interesanta rezolvare
Aladdin - nu m-as fi prins singur de asta niciodata :)
Arbore - 50 mega de memorie... :-|
Cerere - tare ideea
Grazing / Sistem - super tare dinamica
Poligon - geometrie marfa
Robot - mi-a placut ca poti sa faci No-Fit-Polygon pe poligoane convexe cu infasuratoare convexa simplu :P

Eh... au fost 10 in loc de 5 :)

Am apreciat o problema nu neaparat dupa dificultate, ci gradul de inventivitate, originalitate si idee "frumoasa" de rezolvare.

Top 5 in nici o ordine:
1. Caraibe
2. TV Show
3. Critice
4. Boom
5. Xor Max

Asta din ce imi amintesc acum, daca le-as lua pe fiecare in parte probabil 80% ar trece prin Top 5. Cea care mi-a placut cel mai putin este totusi Barman...

Xor max-marfa ideea cu trie-ul
tri2 - problema frumoasa care imbina geometria cu algoritmii
gard-dinamica super tare, care se optimizeaza frumos
telegraf-un exemplu mai aparte de dinamica, idee foarte neevidenta
sortnet-pentru solutia cu codul lui gray foarte originala

ok, cosmin  :D

ordinea irelevanta:

pavare :  :D am dezbatuto cu mai multi (live) care nu o stiau, si a ieshit solutia :D, am fost ff bucuros cand am luat atunci 100 si in plus a fost problema care mi-a facut introducerea in genu' acela de probleme ;)

zero: mi-a placut ca inca atunci nu prea stiam pd, si cineva tot insita sa o fac, ca sunt lenes... si nu vreau sa fac... si m-am hotarat sa am placerea sa o rezolv, apoi am provocat si eu la randu meu si cineva a facuto cu back

Indep: include si exclude

sortari: am dat de faza cu 0 si 1 din greseala... si dupaia am aflat ca chiar exista

mult: a fost mistho... da mai mult de 95 nu am reusit :))

infine nu cred ca e lista numa 5, pt mine sunt multe probleme care mi-au facut o introducere intro categorie cum ar fii: include si exclude, pd, anumite jmenuri etc... inca mai sunt probleme de rezolvad dar m-am cam lasat in ultima vreme, a fost mutarea asta si nu prea am avut timp .. deabia acu m-am rezolvat cu chestiile necesare programarii :D

this is my opinon :D  :harhar:
ok, numa bine  :thumbup:

Sunt mai multe dar acuma scriu ce imi vine in minte  :)

Drumuri Minime - super ideea cu logaritmarea

Heroes of Might&Magic - imi place foarte mult tipul asta de dinamica  :thumbup:

Muzeu -  am invatat ca Lee-ul poate pleca din mai multe pozitii  :aha:

Alpin - tare ideea cu 'memoization' pentru a lua 100

Catun - frumoasa dar inca sunt la pragul de 70  :oops:... ](*,)
{later Edit} Cum am putut sa uit de problema Copaci ?  :aha:. E meseriasa! :thumbup:

 :peacefingers:

Excluzand problemele mele de pe infoarena (care nici macar nu-mi plac toate.. dar unele din ele imi plac foarte mult.. ca de exemplu, soc & tj), cele care imi plac cel mai mult ar fi urmatoarele:

1) Algola -> pt ca am mai intalnit problema cu capacitati 1 pe muchii si n-am stiut s-o rezolv, iar cand mi-a prezentat-o Silviu cu capacitati >1 pe muchii mi-a picat fisa :) - asta ca sa vezi ce mult conteaza forma in care e prezentata problema (practic, in varianta initiala, era doar.. un simplu graf si nu "tzipa" ca s-ar rezolva cu flux :) )

2) Telegraf -> pt ca e marfa si a fost foarte grea la vremea ei [ si pt ca n-am rezolvat-o atunci :) ]

3) Petsoft -> pt ca mi-a placut ideea de dinamica pe arbore

4) Lapte -> pt ca mi-a placut ideea de cautare binara + dinamica (desi am auzit ca exista si soluti emai simpla :) )

5) Lesbulan -> pt ca inca nu mi-a iesit :)

-------

extra problems ;)

6) Rubarba -> pt ca am rezolvat-o fara sa stiu ce sunt "rotating calipers"

7) Drumuri2 -> pt ideea de cautare binara + flux cu capacitati inferioare (& superioare)  care a fost f misto la vremea ei

8) Oras -> pt ca a fost una dintre putinele probleme pe care, dupa ce am citit-o, chiar mi-a venit s-o implementez :D , ca sa verific daca chiar imi mergea ideea (si pt ca mi-a iesit aproape din prima)

9) Hallway ->  numai pt ideea de cauare binara + componente conexe pe punctele transformate in cercuri.. pt ideea fara cautare binara nu imi place :)

10) Frac -> pt ideea misto de cautare binara + includere-excludere

11) Pavare -> pt ideea misto de dinamica cu stari exponentiale

12) Dreptunghiuri -> pt ca se poate rezolva in complexitate optima in mai multe moduri (nu doar cum e solutia lui Cosmin)

13) ABC -> pt ca mi s-a parut draguta


That's it! ;)

Joke:

1. A+B
2. CMMDC
 :rotfl:

Incerc sa fac un clasament desi nu cred ca voi reusi sa ma limitez doar la 5 ptr ca sunt multe probleme tari pe infoarena.

radiatie - multe idei smekere intr-o singura problema (eu am rezolvat-o cu arbori de intervale)
Drept 2  - pur si simplu marfa
Import - am mai invatat o chestie mishto :D
Sequencequery si Hotel  - am inteles mai bine arborii de intervale
Zoo - in sfarsit am inteles acel articol al doamnei Dana Lica
Ben - mi-a placut ideea cu sortarea capetelor intervalelor
Vila2 si Divk - ptr ca am reusit sa inteleg klumea deque-ul.

Eh m-am intins oleaka cam mult dar asta e.

Top 5 pentru mine sunt:

1. Campion - o stiva face minuni.
2. Gard4 - cel mai tare graf al starilor pe care l-am intalnit.
3. Soc - in enunt e practic predata o lectie de teoria grafurilor si iti cere sa rezolvi "tema".
4. Cabane - stii STL aranjezi linistit cabanele.
5. Radiatie - mi-a placut pentru solutia foarte scurta cu "fatairea" nodurile dintr-un arbore in altul.


Din restul topului mai fac parte: Grazing, Lesbulan, Cowfood, Zebughil si restul problemelor, pentru ca toate merita.  8)

 :-' Haideti sa zik si eu pe bune:

1. Cifra -m-am kinuit la ea foarte mult pana knd mi-am dat seama k trebuie sa iau in considerare doar ultimile 2 cifre, + un vector precalculat
2. Fractii-aici am reusit sa invat functia totient si am aprofundat cunostintele in ceea ce priveste ciurul lui eratostene.  :weightlift: [mi-a venit ideea in drum spre scoala, iar in timpul orei de info am facut-o de 100  :wink: ]
3. Factorial: Super buna aplicatie pt cautarea binara !  :thumbup:
4. Divizori primi - faina aplicatie la programare dinamica...
5. 2sec: relativ simplutza, insa mie mi-a cauzat probleme  :aha:
6. Numere prime-aici am aflat prima data de ciurul lui eratostene  :ok:

Sunt foarte frumoase toate problemele site-ului! De fapt e frumos intreg site-ul! Felicitari celor care l-au creat! Succes in continuare!  :thumbup:

 1) Cerere -> pur si simplu mi-a placut
 2) Critice -> pentru ca nici pana in ziua de azi nu-mi dau seama unde busheste fluxu' ala
 3) Cifra   ->  mi-a mancat mult prea mult timp
 4) AsMax ->  banala.... dar mi-am batut prea mult capu' cu ea

Din moment ce au trecut 4 ani de la ultimul post ma gandesc ca tinand cont ca in acesti 4 ani au mai aparut multe alte probleme sa refacem un top de probleme. Propun sa facem un top 10 cele mai faine probleme din arhiva (10 deoarece acum au aparut mai multe probleme si poate unii nu se mai multumesc doar cu 5).

Ca urmare top 10 probleme din arhiva ale mele:
Namlei - imi place atunci cand intr-o problema se combina chestii. Matrici pe arbori de intervale!!!! Jos palaria  :D
Lant2 - Aici am descoperit niste formule cu combinari care m-au dat pe spate.
DreptPal - Repet ca imi place cand se combina smenuri.
Subarbore - Solutia mea era un dijakstra pe configuratii care nu mi sa parut deloc pe fata si care mi-a placut super mult.
Kgraf - Tot respectul.
Puteri3 - Geniala problema dar pacat ca exista formule pe net.
Arbsat2 - In concurs am zis ca este super jeg problema si ca nu ma apuc de ea dar cand am vazut cat de smechera si scurta e, am zis WOW.
Dlog - Bucati de sqrt rules   :yahoo:
Matcnt - O problema de numarare foarte smechera (dupa parerea mea).
Arbfind - dupa nu stiu cati ani in care lumea a bagato cu suffixe rays in n * log^2(n) sa descoperi ca se poate in O(n). Credema ca e super tare sentimentul.

Mi-a fost super greu sa selectez chiar si 10 probleme dar intr-un final am reusit. Ele sunt in ordine aleatoare (daca stateam sa le si sortez chiar ca incepea sa ma doara capul   :) )
Acuma astept cat mai multe opinii.    :D

PS: Matcnt inca nu este pusa in arhiva dar va fi publicata in curand (e de la Lot Botosani in caz ca sunteti curiosi)

Dani, vad ca ai selectat multe probleme de la Algoritmiada 2012 :D.

Putem sa facem un topic nou cu Top 10.

Nu e vina mea ca au fost misto.  :D

Da sa mai posteze lumea.

Si mie mi-a placut namlei initial, dar acum nu mi se mai par atat de interesante problemele care imbina mai multi algoritmi sau poate cele pe care le-am vazut eu nu sunt prea originale.

1)  Bal: simpla si scurta, desi la prima vedere pare complicata
2)  Egal
3)  Carti2
4)  Ubuntzei: nu ma prind de sol de 100
5)  Terenuri3d: nu m-as fi gandit la flux
6)  Camera: super tare metoda de rezolvare, dar si modul cum se pot calcula diagramele voronoi cu ajutorul ei
7)  RK: solutia fara trie
8)  jstc: pentru ca m-am chinuit mult sa o optimizez, iar acum nu se mai poate lua 100 la ea
9)  motel: pentru sol in nlogn de care nu ma prind

Din arhiva monthly imi plac mult bursa si graf2
10) sea2: solutie scurta cu set