Pareri despre Runda 2

[ditzone]

Asteptam parerile voastre despre cea de-a doua runda a concursului preONI 2006.

[cristi8]

eu am participat la 11-12.
..ma temeam de rezultatele astea..
problemele au fost grele (nu prea s-a luat 100 mai deloc).. astept articolul cu solutii.
Eu sper ca la rundele viitoare sa fie probleme mai abordabile..

[•mastermage]

problemele au fost mult prea grele, ca la runda anterioara(dece nu invatam noi din greselile din trecut?). de exemplu la problema "desc" nimeni nu o luat mai mult de 4 puncte.    
prima oara cand citesti nu-ti dai seama de dificultatea problemei si stai o ora pe ea si iti dai seama ca nu poti sa faci un algoritm cu care sa faci macar 10. dupaia incerci sa te apuci de alta probema, deci s-o pierdut mult timp pentru nimic. cineva care are noroc si incepe cu o problema mai usoara are posibilitatea sa faca mai multe puncte.

[•cyron]

sau poate ca altii se  uita mai intai pe toate problemele ...interesant concept nuh?

[VladS]

Dupa stelele informaticii ati zis ceva de genu : "Fiti fara grija. Nu o sa dam asa greu la preONI" dar mi se pare ca problemele se apropie (cel putin dpdv al rezultatelor) de cele de la stele.
Oricum problemele au fost frumoase si nu au fost probleme cu testele.  Deci  

[•Zeus]

Personal problemele nu mi s-au parut f. grele. Limita de timp m-a omorat. La struti cu O(N*M*P) am luat 70 ...
[ nu stiu inca solutia oficiala, poate e O(N*M) ].

Probabil e vina mea, deoarece vad ca alti concurenti au luat 90-100p.

La desc se putea da limita de timp un pic mai mare . Am folosit un algoritm recursiv cu hash si am luat 50p ...

Iar 'camera' a fost intradevar grea ...

Una peste alta, runda a fost interesanta, astept sa vad 'complexitatile' oficiale.

[•Cosmin]

Hmm la camera vroiam sa dam teste cu n 60000 ...

[•filipb]

de exemplu la problema "desc" nimeni nu o luat mai mult de 4 puncte.

Problema desc nu mi s-a parut asa grea ( dupa ce m-am prins ).E interesanta si chiar merita! In timpul concursului am luat 60 la ea... Bine, neoficial :p Dupa ce am facut o legatura, mi-a venit ideea imediat... De exemplu, daca schimbam operatorul ( in loc de inmultire, adunare ) obtinem problema de partitie unui numar natural, care se rezolva cu dinamica. Asa faceai si aici: M[j] - numarul descompunerilor lui p ( al i-lea divizor al lui N), in care primul termen este p[j]. Cred k trebuia optimizat k am luat 4 TLEuri...  

Personal problemele nu mi s-au parut f. grele. Limita de timp m-a omorat. La struti cu O(N*M*P) am luat 70 ...
[ nu stiu inca solutia oficiala, poate e O(N*M) ].

Nu.. E O(P * N * M). Aici e ceva foarte ciudat   eu chiar propusesem initial limita la 3 secunde... Sursa mea merge f. repede, da am inteles si de la altii ca surse pe aceeasi idee ruleaza mult mai greu  

[•greco]

Probabil ca atunci cand stii solutiile problemelor dinainte este mai greu sa-ti dai seama de nivelul de dificultate al lor. De exemplu la problema "camera" noi credeam ca o sa se ia punctaje maricele cu gandul la faptul ca nu am mai dat-o in n * lg n. Dar realitatea era alta, punand probleme si in n^2.

Oricum, una peste alta, eu zic ca n-au fost asa de grele ca la "stele" problemele, dar o sa tragem concluziile necesare si o sa incercam sa ajustam cat mai bine nivelul concursurilor.

[•Zeus]

Pai asa am facut si eu filipb. Numai ca am facut recursiv. Apropo, e normal ca o solutie corecta ca complexitate sa ia 50p ? Inteleg ca trebuie sa optimizez, dar pe vremuri faptul ca te prindeai de o pb. merita mai mult de 50p ....

[•filipb]

Daca intr-adevar aia e complexitatea optima, poate ca e cam mult sa pierzi 50 de puncte... Afisarea solutiei tot recursiv am facut-o si eu. Oricum, depinde de autor, de constanta algoritmului, de mici optimizari, de mai multi factori... Adevarul e ca sunt unele probleme cu limite de timp foarte stranse pe site ( la preONI trecut la balans am postat in arhiva algoritmul de complexitate optima dat pe info.devnet si nu am luat decat 50   )
Cat despre probleme in ansamblu, mie mi-au placut.

[ditzone]

Intr-adevar se pare ca limita a fost un pic cam stransa la desc... desi eu si mircea am facut surse de O(D^2 log D) (D= numarul de divizori) care ruleaza in 0.3 secunde... fara vreo optimizare ...si exista si solutie in O(D^2)...

[•Zeus]

Voi ati facut surse avand plenty of time to spare, poate ati si colaborat la idei. Nu ati avut o runda cu o rupere de geometrie, o pb. cu 3 deque si o pb. cu optimizare la greu ( desc ) in 4 ore ...

Adica ce va costa sa dati limita de timp la 2 sec de ex ? Exista riscul sa intre un back in 2 sec si sa nu intre intr-o secunda ?

Pe viitor, ati putea si voi da limita de timp astfel incat solutiile cu complexitatea corecta sa ia mai mult, fara sa fie necesare optimizari majore. Un exemplu bun de urmat este TopCoder. Am avut complexitate optima si la desc si la struti si am luat 120p pe ele ...

Si la runda trecuta a trebuit sa optimizez la greu solutia O(NlogN + M) de la 'distante' ca sa intre.

In rest pb. au fost bune, testele la fel. Doar limita de timp a fost cu probleme.

Keep up the good work !

[•azotlichid]

In concursurile urmatoare vom incerca sa dam limite mai mari de timp care sa permita diferite implementari la complexitatea optima, dar care totusi sa pice rezolvarile brute force & stuff..

[•Cosmin]

La topcoder o problema ca si camera o fac bazatii in 20 de min ... si noi vrem sa ridicam nivelul, nu trebuie sa ajunga comparabil cu cel de pe tc, dar totusi sa se vada la olimpiada nationala o diferenta.

[•Zeus]

stiu destul de bine cum sta treaba pe TC ...
Si nu fac bazatii 'camera' in N log N in 20 minute ... stai linistit ...

[•Cosmin]

Ziceam de n^2 ... si eu stiu destul de bine cum sta treaba cu tc, si sunt linistit.

[•domino]

Pai la "Distante" nu trebuia sa iei max cu altceva decat O(N+M) , deci e bine ca a trebui sa optimizezi. La "Descompuneri" sursa am facut-o aseara la 3 noaptea, deci n-am avut prea mult timp pentru ea. Fiindca rula in 0.3s, limita de 3 ori mai mare mi s-a parut suficienta. Este normal sa iei punctaj maxim cu solutii de aceeasi comeplexitate, se pare ca la Descompuneri constanta ta era foarte mare. Ca regula generala, exista o diferenta destul de mare intre sursele care le facem si limitele de timp puse , tocmai pentru a evita astfel de situatii. Pacat ca de data asta nu prea s-a reusit.. oricum, fiecare concurent isi putea testa pe un test maxim sa vada daca e nevoie de optimizare. Sunt destul de frecvente cazurile acestea si la concursuri , cand trebuie implementat cu grija pentru 100 de puncte (ex. la "Stele" problema "siruri"). Iar comparatia cu TopCoder nu este tocmai corecta, acolo ai 75minute, nu prea se asteapta nimeni sa stai sa-ti testezi sursa prea mult.

[•Zeus]

Aha .. in N^2 da, pb. o faceau multi ...

Ideea in legatura cu TC era ca acolo nu se pune pret f. mare pe optimizari, ci pe algoritm .. [ la probleme de nivel mai mare ].

Nu vad legatura dintre nivelul competitie si limite mai mari de timp care sa nu necesite optimizari la greu.

Nivelul e dat de optimizari ?

Daca ar fi fost limite de timp mai mari, poate lumea nu ar fi stat pe optimizari si ar fi facut si ceva la 'camera'.

E bine sa fi linistit.  

[•Cosmin]

Pai mie imi merge sursa la problema mea in 0.1 deci am dat de 3 ori mai mult timp ... La struti mi se pare si mie acuma cam dura limita de timp, dar sa fi dat un timp de vreo 6-10 secunde parea un pic exagerat inainte de concurs si s-a luat decizia asta. Incercam la urmatoarele runde sa calibram mai bine nivelul de dificultate.

[•domino]

Punctajele tocmai arata ca lumea nu prea a stat pe optimizari si a implementat "din topor".  :lol:

[cristi8]

eu am facut O(P*N*M* log(N*M)) .. si ma asteptam la ceva mai mult de 20 de puncte..
..sunt curios cat ar fi luat un brute-force P*N^2*M^2.. stie cineva ?

[•sarabogdan]

30