Top #10 probleme din arhivă

[•wefgef]

Pentru că în ultimii ani arhiva de probleme a crescut foarte mult, cred că este momentul să revizuim opțiunile pe care le-am exprimat în acest topic. Care sunt problemele voastre preferate și de ce?

[•S7012MY]

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
 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

[•elfus]

Favoritele mele (din ce am lucrat pana acum, ordine random):

1. radiatie = imbina mai multe tehnici utile: LCA, APM si smenul de la problema stramosi
2. otilia = prima oara cand o vezi pare imposibila. Dar daca faci niste observatii cheie, nu mai e deloc asa grea.
3. dreptPal = combinatie de smenuri. Jos palaria eudanip 
4. Dlog = desi pare problema de matematica, admite mai multe solutii care sunt pur informatice
5. swaps = inca n-am facut-o, dar in teorie stiu s-o implementez. Imi place atat problema, cat si explicatia solutiei din articolul oficial
6. Pav = cred ca unul dintre cele mai misto Divide at Impera pe care le-am vazut
7. Rk = un exemplu foarte didactic de Radix sort
8. xor = m-am prins la SMR de ieri de D2-500 doar pentru ca am rezolvat problema asta, altfel nu cred ca eram in stare sa fac problema
9. lapte = 2 abordari posibile (cautare binara + dinamica sau greedy), din ambele ai ce invata
10. ratphu = de aici am auzit prima oara de dinamica pe stari exponentiale. Mi se pare un exemplu foarte intuitiv pentru cine vrea sa invete astfel de dinamice.

[•wefgef]

Lista mea este următoarea:

• Aladdin- O problemă grea din toate punctele de vedere.
• Flux - Pentru că e Gauss.
• Invsort - Așa ar trebui să arate o problemă de olimpiadă.
• Sortnet - Așa ar trebui să arate o problemă de olimpiadă.
• Tarnacop - Trebuie să înțelegi fluxul cu adevărat pentru a o rezolva.
• Arbsat2 - Așa ar trebui să arate o problemă de olimpiadă.
• Bal - Pentru demonstrația soluției, mie mi se pare foarte greu de scos în condiții de concurs.
• Pitici3 - O programare dinamică neintuitivă.
• Harta2 - Pentru soluția cu divide et impera.
• Ghiozdan - Pentru soluția cu memorie liniară.

[•eudanip]

Sa fie si aici  :

Namlei - imi place atunci cand intr-o problema se combina chestii. Matrici pe arbori de intervale!!!! Jos palaria   
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   
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.

Ca sa scriu ceva in plus pot sa zic ca imi plac deasemenea foarte mult problemele: Invsort, Ghiozdan(solutia oficiala), NumereX, Perioada, Poze(solutia cu suffixe rays 2D), Secv2m, Shgraf, Regat, Stalpi2, Radare.

[•a_h1926]

Problemele mele preferate (in ordine aleatoare) sunt:

• NumereX - pentru modul in care poti folosi un arbore de intervale
• Invsort - pentru solutia geniala
• Unique - una din cele mai frumoase probleme pe care le-am rezolvat cu paduri de multimi disjuncte
• Ciclu - pentru ca de aici am invatat smenul cu cautarea binara a mediei aritmetice
• Carray - pentru modul super in care se construiesc arborii
• Spirt - una din cele mai faine probleme de numarare pe care le-am intalnit
• Xormax - prima problema pe care am rezolvat-o folosind un trie
• Otilia - pentru ca nu te gandesti sa folosesti o stiva la o problema de teoria jocurilor
• Radio2 - aplicatie super pentru principiul lui Dirichlet
• Arbore - pentru solutia cu impartirea in bucati de sqrtN

[•CezarMocan]

Top 10 probleme din arhiva:

Invsort - Problema asta e ca un film bun: dupa ce afli solutia / te prinzi, simti ca iti pare rau si ca ai da orice sa te gandesti la ea din nou

Dmg - Desi am 100 pe ea, solutia mea nu e in totalitate corecta. In orice caz, hash-uri pe laturile si unghiurile poligonului - respect

Caraibe - Nu foarte grea si strict de idee, ar trebui mai multe probleme de felul asta

Cabane - Dinamica de dinamica, nu mi-as dori sa o primesc in concurs )

Robot - E ca si cum ai manca mici si ai bea tequilla in loc de bere - are niste parti frumoase, per total nu iti place, dar dupa te lauzi la toti prietenii cu ce ai facut.

Tri3 - Dupa ce afli solutia ti se pare atat de evidenta, si cu toate astea e destul de greu sa te prinzi si sa implementezi

Reg - No comment.

Grazing - Putin de grafuri, putin de combinatorica, putin de dinamica, putin de observatie, putin de idee, mi-a placut tare... mult

Ghiozdan - Sa te tot gandesti la problema asta si nu ai cum sa te plictisesti

Radio2 - Din toate motivele mentionate mai sus Si pentru ca mi-a iesit la lot

Si nu in ultimul rand Adapost2 si Semne, care m-au invatat sa bulanesc .

[•toni2007]

Top 10 dupa parerea mea:

#10 harta3 (stiu e a mea, dar dupa 2 ani doar 17 oameni au scos-o, si mie mi-a iesit din a5-a incercare cand am bagat-o din nou).

#9 color3, se facea pt ca e smen

#8 mst, pt ca se bulanea misto dar si solutia era misto

#7 semne, pt ca solutia era ceva bulaneala dubioasa

#6 a+b, pt ca mi-a iesit din a doua incercare

#5 aladdin2, pur si simplu mi-a placut ca era cu aladdin

#4 nrtri, asa am invatat algoritmul meu preferat, cautarea binara

#3 icrisop, pt ca sunt personajul principal (pt cine stie ONI Piatra Neamt)

#2 nuke, pt ca am fost singurul care a scos-o de 100 in concurs cu treapuri

#1 santa, pt ca am scos sursa de 10 kilo

[•eudanip]

Top 10 dupa parerea mea:
#6 a+b, pt ca mi-a iesit din a doua incercare

#5 aladdin2, pur si simplu mi-a placut ca era cu aladdin

Toni, eu unul apreciez motivul pentru care iti place problema Alladin2 dar de ce nu iti place si problema Alladin? 
PS: Mie A+B mi-a iesit din a 3-a incercare.

[•toni2007]

Ca nu m-am prins de smen.

[•freak93]

La mine

• Pavare pentru cei 2 ani in care m-am gandit la ea si am scos solutia M * N * fibonacci(M)
• Petrica pentru ca e prima problema cu arbor/i/grafuri pe care am facut-o vreodata
• Hotel pentru ca am invatat Lazy Deletion
• KMP , best algorithm
• Kgraf, singura problema la care sunt autor
• Radio2, input random, te invata lucruri
• Egal ca m-am prins de jmen in concurs, si am fost singurul care am scos-o
• Trasee prea tare problema,
• Ghiozdan prea destepte cele 2 solutii cu memorie liniara
• Euro pentru inca un jmen util

[•GavrilaVlad]

Top 10 probleme preferate (in ordine invers alfabetica)

• Zoo - Printre primele probleme cu arbori de intervale pe care le-am facut
• Tunelul groazei - Una din putinele probleme cu expected value de pe infoarena
• Terenuri - Infasuratoare convexa tinuta ca lista dublu inlantuita + ceva seturi ca sa gasesti repede ce-ti trebuie
• Tarnacop - Trecand peste enuntul ambiguu (), e tare ca ajungi pana la urma la CTC plecand de la flux
• Stramosi - Multe aplicatii pentru "dinamica de la stramosi"
• Robot - Pentru ca inca n-am chef sa implementez tractorul asta
• Plan - Imi plac combinatiile de algoritmi
• Namlei - Aceeasi explicatie ca la plan
• Egal - Sunt fan al smenului de la Heavy-Path Decomposition
• Arbsat2 - Pentru ca a fost cea mai profitabila problema pe care-am facut-o (si pe deasupra mai are si solutie smechera)

Bonus: In topul meu, la mare-mare distanta de problemele acestea (in jos ), se afla problema Intensitate - pentru mine cel putin, este cea mai "speciala" problema din arhiva

[•pauldb]

Imi place mult ideea acestui top, te ajuta sa gasesti probleme interesante din arhiva fara prea mult efort. De aceea voi mentiona si eu 10 probleme care mi se par tari (nu neaparat cele mai tari) si pe care nu cred ca le-a mentionat cineva pana acum:

• Telegraf - smechera problema, n-am avut nici o idee cum s-o abordez initial
• Dreptunghiuri - rupere cu cunostinte de clasa a 9-a
• Cerc - interesant ca se reduce la o problema de grafuri si la teorie nu prea des intalnita in probleme
• Obiective - grafuri, arbori, algoritmi, structuri de date, tot ce vrea sufletul
• Ndap - o dinamica 3^n misto
• Copaci3 - relativ simpla rezolvarea, greu/interesant de demonstrat de ce e corecta
• NKPerm - o abordare neobisnuita pentru problemele cu stari
• Trenuri - subiectiv: pentru ca am venit o rezolvare misto la problema lui Alex, motiv pentru care a ajuns sa fie o problema tare de lot
• Posta - imi place genul asta de probleme (greedy + structuri de date) avand input destul de minimal
• Gard4 - interesant modul de utilizare al configuratiilor, desi problema nu e atat de dificila

Dintre problemele care au mai fost mentionate imi plac foarte mult Cabane si Reg.

[•repp4radu]

Top 10 la mine(ordine aleatoare):

• Boom - La problema asta am invatat ce e aia o configuratie
• Muncitori - Prima problema de la vreun concurs de pe infoarena la care am luat 100 in concurs
• Otilia - Cea mai smechera problema de teoria jocurilor care am rezolvat-o
• Unique - Cea mai smechera problema cu paduri de multimi disjuncte
• Bool - Pentru ca am invatat sa evaluez o expresie
• Bal - Faina si scurta
• Petsoft - Prima dinamica pe arbore care am facut-o
• Lupul Urias si Rau - Pur si simplu mi-a placut
• Caraibe - Cea mai faina problema care am rezolvat-o
• Hotel - Imi place lazy deletion