infoarena

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 aceste 2 topicuri: Topic 2006 (http://infoarena.ro/forum/index.php?topic=1011.0) şi Topic 2012 (http://infoarena.ro/forum/index.php?topic=7978.0). Care sunt problemele voastre preferate și de ce?

PS: Includem ÅŸi arhivele ACM/Monthly :)

Invsort (http://www.infoarena.ro/problema/invsort) - Cazul de 50 de puncte chiar e un hint foarte bun
Hallway (http://www.infoarena.ro/problema/hallway) - Misto sa intelegi cautarea binara.
Dsip (http://www.infoarena.ro/problema/dsip) - Pentru ca merge cu SSE :D
Xormax (http://www.infoarena.ro/problema/xormax) - Chiar invatai trie-uri de la ea, acum e cam cliseu.
Radio2 (http://www.infoarena.ro/problema/radio2) - Imi place cand e inputul random.
Sortnet (http://www.infoarena.ro/problema/sortnet) - Patrascu are cele mai interesante probleme parca

Mai las spatiu pentru adaugare, le-am zis pe cele pe care mi-au venit in minte.

1) Nowhere-Zero. O problema geniala, pe un capitol super nisa al programarii (grafurile planare)
2) Dmg, dar cu complexitate O(NlogN) (O(N) dupa sortare)
3) Robot, o idee foarte misto, desi acum cat de cat clasica, tot face treaba pentru initierea in geometrie.
4) Invsort. Pur si simplu, fara egal in probleme legate de sortare
5) Bubblesort. Defapt am mintit mai sus, invsort are un egal :D
6) Kmalloc. Daca ar merge interactivele, pentru un oarecare contact cu programarea reala.
7) Mstack: coada cu stive, simplut. Deque cu stive? Nu chiar asa..
8. SequenceQuery: aici una mai ciudatica, dar o buna introducere in cat de puternici sunt arborii de intervale
9) Simulare: una mai recenta. Rucsac? Ok. Rucsac pe arbore? Decent. Rucsac pe arbore, cu descompunere in centroizi? Da, un clasic :). Acum fara glume, un exemplu de problema foarte tehnica, ce combina mai multe idei, si merita facuta
10) Rutier. Ciucu ftw. Problema super frumoasa, una din primele pe care le-am vazut cu ideea respectiva pentru a introduce radicalul

1. Tree2 (http://infoarena.ro/problema/tree2) - all time favourite ad hoc. no comment here :winner1:
2. Hallway (http://infoarena.ro/problema/hallway) - un exemplu de problemă aparent jeg care se reduce printr-o observație inteligentă la un algoritm clasic :winner2:
3. Crescator2 (http://infoarena.ro/problema/crescator2) - două brute-uri corespunzătoare unor idei diferite de dinamică, combinate, pentru soluția de 100 :winner3:
4. Flux (http://infoarena.ro/problema/flux) - altă aplicație interesantă a unui algoritm clasic. hint: nu este flux
5. Tunel (http://infoarena.ro/problema/tunel) - o introducere bună în expected value
6. Telegraf (http://infoarena.ro/problema/telegraf) - nice dp problem
7. Seriale (http://infoarena.ro/problema/seriale) - un ad hoc mai recent care mi-a plăcut în mod special
8. Sakura (http://infoarena.ro/problema/sakura) - am primit în concurs problema asta, mi-a plăcut ideea
9. Invsort (http://infoarena.ro/problema/invsort) - cât de utilă poate fi rezolvarea unei probleme pe un caz particular
10. Nowhere-zero (http://infoarena.ro/problema/nowhere-zero) - grafuri planare :yahoo:

Vmin (http://www.infoarena.ro/problema/vmin) - pentru un query x se afla functia care are graficul cel mai jos
Copii2 (http://www.infoarena.ro/problema/copii2) - faina ideea cu impartirea echipelor in functie de bitii numerelor de ordine
Evantai (http://www.infoarena.ro/problema/evantai) - observatia de a reduce complexitatea de la O(n^4)
Xp (http://www.infoarena.ro/problema/xp) - impartire in bucati de sqrt
Xor3 (http://www.infoarena.ro/problema/xor3) - faina solutia cu de cate ori ajung anumiti biti intr-o pozitie (x,y)
Cut it (http://www.infoarena.ro/problema/cutit) - observatia cu compunerea grafului din clici
Virus (http://www.infoarena.ro/problema/virus) - Aici am inteles pe deplin suffix array
Radare (http://www.infoarena.ro/problema/radare) - dinamica pe parcurgerea Euler
Lost (http://www.infoarena.ro/problema/lost) - tractoreala, dar tractoreala faina cu dinamica smechera
Grazing (http://www.infoarena.ro/problema/grazing) - cazuri particulare de grafuri

Geometrie:
http://www.infoarena.ro/problema/harbingers  ->  Poate cea mai frumoasa problema de batch pe care am rezolvat-o.
http://www.infoarena.ro/problema/biathlon  ->  Pare foarte grea, dar se rezolva imediat printr-o idee geniala.
http://www.infoarena.ro/problema/tri3 ->  Dupa ce o faci, intelegi mult mai bine infasuratoarea si folosul ariei cu semn.
http://www.infoarena.ro/problema/combl -> Pare foarte simpla dupa ce ai inteles bine ce forma poate lua spatiul solutiilor.
Orbit (Shumen 2013) -> Trisez putin cand o includ, dar este cea mai frumoasa problema de geometrie pe care am rezolvat-o.

Grafuri:
http://www.infoarena.ro/problema/politic2 -> Foarte utila pentru a invata smenul de reducere la N² a dinamicii pe fii.
http://www.infoarena.ro/problema/sortop -> Nu am reusit inca sa iau 100, dar ideea de rezolvare este geniala.
http://www.infoarena.ro/problema/salaj -> Foarte dificila, te invata bine cum sa gestionezi problemele care numara stari finale, nu moduri.
http://www.infoarena.ro/problema/tree2 -> Are o solutie minunata bazata pe grafuri cordale.
http://www.infoarena.ro/problema/soc -> Descompunerea cu care se rezolva este foarte ingenioasa.
http://www.infoarena.ro/problema/santa  -> Te invata cum sa compactezi cat mai mult o rezolvare ca sa nu tractoresti 10 kilo.
http://www.infoarena.ro/problema/ro  -> Te invata cum sa compactezi cat mai mult o rezolvare ca sa nu tractoresti 10 kilo.
http://www.infoarena.ro/problema/parb -> O noua adaptare a ideii de la siruri de sufixe.
http://www.infoarena.ro/problema/divizori2 -> Cel mai dragut tractor de pe IA, printre putinele probleme cu izomorfism de arbori.

Altele:
http://www.infoarena.ro/problema/bcolor -> Cea mai frumoasa problema cu gauss de pe site.
http://www.infoarena.ro/problema/afterparty -> A doua cea mai frumoasa problema cu gauss de pe site.
http://www.infoarena.ro/problema/match -> Mi-a placut foarte mult demonstratia inductiva.

Am pus dublu, dar sper ca cineva sa gaseasca printre ele o problema care sa il impresioneze. :)

Ar fi fost pacat sa elimin vreuna dintre aceste probleme din lista doar de dragul de a fi fix 10.

• Purification (http://infoarena.ro/problema/purification) - Un tur de forta de observatie, dinamica si tehnica. Exceptionala.
• Combl (http://infoarena.ro/problema/combl) - Ideea de geometrie vectoriala este neglijata in scoala (da, se preda, dar nu i se explica utilitatea si nu se introduce ideea de transformare liniara, care mi se pare esentiala dintr-un numar covarsitor de mare de puncte de vedere).
• Nowhere-zero (http://infoarena.ro/problema/nowhere-zero) - Au inclus-o deja multi oameni in lista lor. O adaug si eu pentru ca am pierdut o zi intreaga pentru a demonstra ca ultimul test nu respecta restrictiile. Acum testul a fost schimbat si 5 oameni au trecut de la 90 la 100. Other than that, foarte instructiva atat ca idee cat si ca implementare.
• Entanglement (http://infoarena.ro/problema/entanglement) - Pentru cerinta geniala.
• Bounding Box (http://infoarena.ro/problema/boundingbox) - Pentru enuntul extrem de natural si solutia in N².
• Kthvalue (http://infoarena.ro/problema/kthvalue) - Pentru solutia cu persistent.
• Yamstp (http://infoarena.ro/problema/yamstp) - Daca am avea mai multe concursuri cu probleme de o asemenea calitate am ajunge multi target pe TopCoder.
• Tri3 (http://infoarena.ro/problema/tri3) - Pentru ca mi-a luat 1.5h de la prima citire pana la sursa de 100 - a intrat din prima si de atunci e prima la statistici. Needless to say, o problema superba, nemuritoare.
• Centrale Nucleare (http://infoarena.ro/problema/centrale) - 2SAT pe nodurile unui Aint 2D, respect.
• Labirint (http://infoarena.ro/problema/labirint) - Pentru ca sunt singurul care s-a incumetat sa o implementeze.
• Magic4 (http://infoarena.ro/problema/magic4) - Pentru ca mi se pare extrem de underrated. Grea si cu idee frumoasa.

Lista mea conține 15 probleme, nu m-am putut limita la 10:

• Tree 2 (http://www.infoarena.ro/problema/tree2) - Pentru solutia liniara (cea corecta, testele sunt slabe pe IA si intra si o solutie liniara gresita)
  
• Hacker (http://www.infoarena.ro/problema/hacker) - Solutie aparent exponentiala, nu stiu nici acum sa-i calculez complexitatea
• Bmat (http://www.infoarena.ro/problema/bmat) - Ad hoc dragut
• Flux (http://www.infoarena.ro/problema/flux) - Pentru ca e Gauss
• Tarnacop (http://www.infoarena.ro/problema/tarnacop) - Crezi ca stii flux? Incearc-o pe asta
• Nowhere-zero (http://www.infoarena.ro/problema/nowhere-zero) - Graful fetelor e si el planar? Si ce legatura are asta cu problema?
• Mstack (http://www.infoarena.ro/problema/mstack) - E simplu sa simulezi o coada cu 2 stive. Dar un deque cu 3 stive?
• Aladdin (http://www.infoarena.ro/problema/aladdin) - Un 2-SAT extrem de bine ascuns
• Arbsat2 (http://www.infoarena.ro/problema/arbsat2) - Ad hoc constructiv greu
• Soc (http://www.infoarena.ro/problema/soc) - Acum nu mai este asa grea, dar deconstructia grafului e interesanta
• Invsort (http://www.infoarena.ro/problema/invsort) - Mi-ar placea sa nu existe hint-ul de 50 de puncte.
• Gard 4 (http://www.infoarena.ro/problema/gard4) - Dijkstra, pe ce graf?
• Unique (http://www.infoarena.ro/problema/unique) - Pentru solutia liniara pe care nu o stie nimeni
• Ghiozdan (http://www.infoarena.ro/problema/ghiozdan) - E grea si fara memorie liniara
• Pitici3 (http://www.infoarena.ro/problema/pitici3) - Pentru solutia in N log N

Later edit: Cele 15 probleme au fost propuse de 13 autori diferiti.

•  Combl (http://www.infoarena.ro/problema/combl) Am învăţat din această problemă cât de important este să înveÅ£i algebră liniara ÅŸi să ai o minte deschisă pentru reprezentări geometrice.
• Disconnect (http://www.infoarena.ro/problema/combl) Toată lumea a bagat în concurs Heavy Path, deÅŸi problema admite o soluÅ£ie pur ad-hoc. Merită citit articolul cu soluÅ£ii în cazul în care ÅŸtiÅ£i doar soluÅ£ia cu Heavy Path.
• Ciclu2 (http://www.infoarena.ro/problema/ciclu2) Cea mai frumoasă problemă nedeterministă de pe infoarena.
• Kgraf (http://www.infoarena.ro/problema/kgraf) Nu cred că a avut cineva curajul să bage soluÅ£ia bună fără să îşi dea seamă că merge. E important să demonstrezi.
• RamÄ‚ (http://www.infoarena.ro/problema/rama) Pentru soluÅ£ia cu Divide Et Impera. Chiar ÅŸi cu acest hint, încă nu e simplu.
• Match (http://www.infoarena.ro/problema/match) O problemă foarte naturală.
• Magic4 (http://www.infoarena.ro/problema/magic4) E magie.
• Divisor Graph (http://www.infoarena.ro/problema/divisorgraph) Această problemă arată un mindset diferit, pe care propunătorii români nu îl prea au.
• Pinball (http://www.infoarena.ro/problema/pinball) Pentru că am văzut copii de a 8-a care au rezolvat problema ÅŸi copii de lot care nu.
• Unicat (http://www.infoarena.ro/problema/unicat) Trebuie să înÅ£elegi bine Pscpld-ul.

Am făcut o listă scurtă si cu probleme propuse de mine:

• Popeală (http://www.infoarena.ro/problema/popeala) EnunÅ£ul de suflet.
• Sălaj (http://www.infoarena.ro/problema/salaj) O problemă irosită.
• Reversez (http://www.infoarena.ro/problema/reversez) Stringuri si numărare....
• Bucket (http://www.infoarena.ro/problema/bucket) ÃŽncă nu ÅŸtiu dacă e simplă sau grea.
• MoÅŸtenire (http://www.infoarena.ro/problema/mostenire) Pentru complexitate.

Top 16 din punctul meu de vedere:

1. poveste - culmea algoritmicii
2. otilia - regina gandirii in afara cutiei
3. diametru - un ad-hoc briliant... am gasit o solutie care obtine K = 122267, ar merita o discutie daca se poate mai bine de atat
4. unique - o experienta cu adevarat unica
5. flooow - evidenteaza puterea incredibila a arborilor de intervale dar mai ales a ideei de la flux
6. hardtask - implinirea unui tractorist : smenuri peste idei peste o frumusete de arbore
7. shgraf - cea mai tare problema de numarare
8. nowhere-zero - teorie, idei, implementare: definitia unei probleme grele de info
9. arbfind - rezolvarea liniara este spectaculoasa si incantatoare
10. parb - foarte puternica ca idee si abordare
11. switch5 - observatii si tehnici de abordare culminand intr-un gauss socant
12. matcnt - interpretarea cerintei si optimizarea dinamicii figureaza o problema de numarare de calitate superioara
13. bowling - WOW si doar WOW... e dovada pentru cat de minunat este domeniul teoriei jocurilor
14. combl - promoveaza interpretarea geometrica, gandirea organizata pe subtaskuri si puterea structurilor de date
15. classictask - definitia arhivei monthly: idei dragute si amuzante
16. superbec - desi obiectivitatea tinde la zero pentru ca e prima mea problema pe infoarena, imi place pentru ca forteaza rezolvitorul sa faca observatii si sa aplice mai multe idei; si nici nu e banal de implementat

Multumesc informaticii romanesti ca mi-a dat sansa sa traiesc atatea bucurii prin problemele acestea si toate celelalte pe care nu le-am amintit pentru a nu face postarea prea lunga si plicitisitoare.
Multumesc si initiativei de a nota problemele favorite, pentru ca a fost un exercitiu cu ocazia caruia mi-am amintit de atatea probleme minunate, pentru ca am putut sa le impartasesc celor curiosi, si pentru ca pot afla de probleme noi pentru mine din postarile celorlalti.

Atentie, contine spoilere. Daca vreti sa rezolvati singuri problemele, nu cititi ce urmeaza dupa linkuri.

• Bossime (http://www.infoarena.ro/problema/bossime) - Faci o brutana, observi patternul numerelor care nu au solutie, te gandesti de ce se intampla asta, apoi cauti o solutie constructiva pentru numerele care nu se incadreaza in pattern. Fara brutana, mi se pare greu sa gasesti o conditie suficienta ca sa nu existe solutie (primul pas pentru rezolvarea problemei)
• Maestru (http://www.infoarena.ro/problema/maestru) - Problema trebuia sa se numeasca "Maestrul alcoolic", dupa un film vazut in perioada aia de Teo. Din pacate, conducerea infoarena ne-a cenzurat numele :( Pe langa faptul ca e misto problema, imi place si ca sunt mentionat.
• Mingiute (http://www.infoarena.ro/problema/mingiute) - Mi se pare o problema de flux destul de originala (nu am mai vazut ceva asemanator). Totodata, l-a popit pe Oncescu in timpul concursului (Oncescu de clasa a 10 a, dar tot se pune). Din pacate pentru mine, protagonistul din enunt participa la concursul onsite si, in timp ce ma plimbam prin sali, mi-a spus "ba Chirica, sa vezi ce te bat dupa ce se termina proba"  :sad:
• Copacul Smenar (http://www.infoarena.ro/problema/copacsmenar) - E a doua problema a mea mentionata, stiu ca deja par narcisist, dar e ultima. Probabil dupa ce te prinzi de solutie, spui "wow, ce tare", ca apoi sa incepi sa injuri pentru cat este de tractorit. Solutia poate fi spusa in 2 propozitii, sursa in 5-7 kb. Anul asta m-a popit Oncescu cu o bulaneala (sa-si ia revansa pentru anul trecut), in schimb am popit si eu conducerea infoarena, care nu au fost pe faza cand am scris enuntul si am putut scrie prostioare.  :harhar:
• Invsort (http://www.infoarena.ro/problema/invsort) - Stiu ca e recomandata de 14342432 de ori, dar nu are cum sa nu apara in lista mea. O problema grea pe care as recomanda-o chiar si incepatorilor, o data ce invata despre sortare. Daca intelegi (in loc sa tokesti) algoritmii de sortare, ar trebui sa fie facubila problema.
• Soc (http://www.infoarena.ro/problema/soc) - Alta problema grea pe care as recomanda-o indiferent de nivelul cuiva. In afara de a sti sa parcurgi un graf, restul problemei e doar ad-hoc.
• Ciclu5 (http://www.infoarena.ro/problema/ciclu5) - Desi foarte frecventi in research, nu prea am vazut algoritmi randomizati la concursuri. Solutia e f misto - colorari random + dinamica pe biti. Desi sansa sa nimeresti la o iterare e extrem de mica, probabilitatile ne spun ca sansa sa nimeresti daca repeti procesul de multe ori e extrem de mare.
• Shgraf (http://www.infoarena.ro/problema/shgraf) - Daca o intelegi pe asta pe bune, poti face cam orice problema care te pune sa numeri grafuri. Prima oara cand am rezolvat problema abia am inteles, a doua oara mi-era totul clar, a treia oara parea totul trivial. E clar genul de problema pe care as rezolva-o de mai multe ori.
• Arbsat2 (http://www.infoarena.ro/problema/arbsat2) - Super interesanta solutia. Nu iti vine in minte sa faci Divide et Impera prea usor. Sunt curios daca se poate rezolva fara si care e intuitia care te face sa te gandesti la D&I.
• Comisia (http://www.infoarena.ro/problema/comisia) - Asemanatoare cu smenul de la Heavy Path. Desi sa faci asta pe arbore a devenit clasic, sa te gandesti sa folosesti o idee asemanatoare pe vector mi se pare smecher.
• Dlog (http://www.infoarena.ro/problema/Dlog) - De obicei dupa ce auzi ca se face in sqrt, devine destul de simpla rezolvarea. Aici nu e deloc clar cum continui. Foarte interesanta solutia (Baby step giant step algorithm).
• Echipe (http://www.infoarena.ro/problema/echipe) - Aveam 9 ani cand aparea problema asta. Foarte veche, dar sunt sigur ca e grea chiar si pentru concurentii de acum. O data ce reducem problema la intervale ordonate crescator atat dupa x, cat si dupa y, devine ceva mai simplu. Dar e destul de greu sa te gandesti la reducerea asta.

Well, am pus 10 probleme care chiar mi-au placut (excluzandu-le pe cele 2 ale mele) si pe care inca le tin minte, chiar daca unele sunt rezolvate cu mult timp in urma. Cred ca lista poate avea lejer 20-30 de probleme, sunt super multe faine pe IA, dar le-am scris doar pe primele 10 care mi-au venit in minte  :yahoo:

O mentiune, lista lui wef m-a ajutat super mult (tin minte ca a fost printre cele mai productive perioade ale mele cand incercam sa rezolv cat mai mult din ea). Din pacate, contine probleme propuse pana in 2006. Ar fi o idee sa faca comunitatea o lista noua pentru ultimii 10 ani, cred ca am castiga toti de pe urma ei.

1. tarnacop -- imi place nu doar la nivel de idee, cat si din cauza distantei intre aspectul initial al problemei (flux) si algoritmul cu care se rezolva pana la urma
2. transform2 -- mi-a placut inca de la ONI2016; mi se pare ca isomorfismul utilizat e dragut.
3. nop -- e interesant ca practic problema se reduce la a programa un computer sa "programeze" un alt sistem formal.
4. rangemode -- pt. ca m-a ajutata sa descopar nu doar mo, ci si impartirea pe elemente calde / reci
5. reversez -- pt. ca te invata niste proprietati importante pe z si un mod frumos de a il privi
6. bmat -- conditia pentru ca sa existe o strategie de castig e neasteptata & faina
7. fenrir -- problema "mioritica" faina atat prin ideea in sine, cat si prin faptul ca e printre putinele probleme output-only de pe site.
8. parpal -- imi place "structura" asta de rezolvare a unei probleme (adica 1. ghiceste o proprietate care ar face rezolvarea simpla si 2. demonstreaz-o).
9. bcolor -- mi se pare ca problema se foloseste de niste idei frumoase ("adunarea" paritatilor pe muchii a 2 multimi de cicluri da tot o multime de cicluri, si orice multime de cicluri poate fi aproximata d.p.d.v. a paritatilor pe muchii de un singur ciclu), care sunt utile si in alte cazuri (euler & flux).
10. bunicu -- pt. ca mi-a demonstrat ca tehnica diagonalizarii lui Cantor nu e inutila in viata :)
11. grafc -- mi se pare o problema de idee draguta
12. arbciclu -- imi place cum solutia e, in principiu, simpla de descris ("scoatem mereu o 'frunza'"), dar rezolvarea eficienta depinde de gasirea unui alt mod de a o enunta

1. soc
2. drumuri5
3. tunel
4. ciocolata2
5. afterparty
6. comisia (in Nlog, ofc)
7. cast
8. caraibe
9. rev (in Nsqrt)
10. invsort

Lista mea:

Spoilers ahead!

1. NoGameNoLife - The Final Stage -> pentru smenul cu rularea programului cat timp nu ia TLE, super util si in alte cazuri  :harhar: (http://www.infoarena.ro/problema/nolife (http://www.infoarena.ro/problema/nolife))

2. Tri -> cred ca a fost unul dintre cele mai puternice sentimente de "mind-blown" pe care le-am avut cand mi-a fost explicata metoda de rezolvare ( cea care nu necesita structuri de date )  =D> (http://www.infoarena.ro/problema/tri (http://www.infoarena.ro/problema/tri))

3. Gravity -> dijkstra pe costuri mici..subtil (http://www.infoarena.ro/problema/gravity (http://(http://www.infoarena.ro/problema/gravity))

4. Import -> mi s-a parut super faina metoda de a rezolva un sistem de inecuatii de genul x - y <= k (k constant) cu Bellman Ford (http://www.infoarena.ro/problema/import (http://(http://www.infoarena.ro/problema/import))

5. Hide and Seek Game -> problema care m-a facut sa realizez utilitatea ciclilor din cadrul unei permutari (http://www.infoarena.ro/problema/hideandseek (http://www.infoarena.ro/problema/hideandseek))

6. Arbfind -> idee inedita de rezolvare (http://www.infoarena.ro/problema/arbfind (http://www.infoarena.ro/problema/arbfind))

7. Fantasy -> pur si simplu mi-a placut (http://www.infoarena.ro/problema/fantasy (http://www.infoarena.ro/problema/fantasy))

8. Cowfood -> (http://www.infoarena.ro/problema/cowfood (http://www.infoarena.ro/problema/cowfood))

9. Unlock -> misto ideea de a folosi paduri de multimi disjuncte care suporta si operatia de undo (http://www.infoarena.ro/problema/unlock (http://www.infoarena.ro/problema/unlock))

10. Rangemode -> pentru algoritmul lui Mo, destul de intalnit acum (http://www.infoarena.ro/problema/rangemode (http://www.infoarena.ro/problema/rangemode))

1. soc
2. drumuri
3. tunel
4. ciocolata
5. afterparty
6. comisia
7. cast
8. caraibe
9. rev
10. invsort

1. soc
2. drumuri
3. tunel
4. ciocolata
5. afterparty
6. comisia
7. cast
8. caraibe
9. rev
10. invsort