infoarena

Asteptam parerile voastre despre prima runda a concursului aici. Ne intereseaza in special care credeti ca este motivul pentru punctajele mici de la clasele 9 si 10, deoarece toti 6 din comisie eram convinsi ca punctajele o sa fie mai mari. De asemenea, asteptam sugestii pentru niste sondaje referitoare la preONI 2006.

buna runda ! tineti-o tot asa :D

As vrea sa multumesc organizatorilor pt. efortul depus. De data asta nu a fost nici o eroare cu testele, pb., sau evaluarea. Problemele au fost din punctul meu de vedere destul de interesante ... Balans se inspira puternic din secv3 ... dar in rest ok ;)

Felicitari organizatorilor pentru organizarea fara greseli(majore). Speram ca si urmoatoarele concursuri sa fie la fel.
Pacat totusi ca la problema Zebughil se putea lua prea usor 100 cu un back foarte putin optimizat( o simpla sortare...).

O mica rugaminte pt. comisie ...

Data viitoare poate testele vor fi mai grele ...

Cum a zis si andrei la Zebughil se putea lua prea usor punctaj apropiat de maxim [ sau chiar maxim ].

De asemenea, la distante, sa dai unei solutii dijkstra chior minim 70 de puncte, chiar 100p [ cu optimizari ] ....

Problema 'distante' a fost considerata pb. medie la XI-XII ... era prea usoara pt. sector in forma actuala  ...

Ideea e ca trebuie facuta o departajare corecta ... unii s-au chinuit la pb. ca sa le faca corect de 100 .. merita mai mult de 0-30p fata de solutii norocoase [ zise si 'bulaneli' ] ....

de asemenea multumesc organizatorilor pt efortul depus, subiectele au fost ok la 11-12.  :thumbup:
singurul regret care il am la runda asta e ca la zebu am trimis tot un fel de greedy pana la urma si am luat 30, acum am vazut ca bkt`u meu scotea 90   ](*,)

o idee de sondaj: ar trebui sa existe mai multi participanti in finala de la clasele 11-12? (avand in vedere punctajele stranse [la runda asta, cel putin] si numarul de concurenti)

Problema Distante mi s-a parut super tare. Si nu cred ca un dijkstra chior( O(n^2)) ar fi scos 70 de puncte. Un dijkstra cu heap( care ia cam 100 de linii de cod) eu zis ca merita 70-100 puncte.
Cat despre marirea numarului de participanti... Unde ar mai fi concurenta??? Si punctajele nu sunt asa de ridicate: 160 puncte locul 10; pare destul de corect trasa linia...

Felicitari! Intr-adevar nu au existat probleme de organizare.  :!:  =D>

Pai nu chior mai ... M log N ... e in manualul de a 11-a ... asta nu e concurs de manual, nu ? si nu scrii 100 linii .. se poate face si in 60-70 de randuri .. tot programul ...

Sa fim seriosi, nu se poate pune problema ca un algoritm dijkstra de M log N sa fi pus dificultati unui concurent de clasa a 11-a ... doar daca nu are manual de info :lol:

Hai sa dam acuma cel mai lung subsir crescator... 70p N ^ 2 .... 100p N log N

Oricum, dupa cum am inteles, dificultatea pb. va creste pe masura ce se apropie finala ...

=D>  =D>  Felicitari organizatorilor !!  :mrgreen:  Si eu ma numar printre cei care s-au tzepit cu dijkstra NLogN ! Felicitari cataline, si bafta in continuare ! Pentru echipa devnet, pot sa zic ca ati creat un concurs mult mai tare decat cele existente in acest moment in tara. Asteptam runda 2 !  =D>

Poate ai dreptate... poate in alte locuri se face la info si Dijkstra cu heap. La mine in clasa( info intensiv- 7 ore pe saptamana) o singura persoana stie ce este ala heap. Si pe langa asta restul colegilor considera ca dijkstra este un algoritm care trebuie tocit instructiune cu instructiune. Si nu stiu despre care manual vorbesti Zeus. Ca noi am facut dintr-un manual in care sigur nu exista dijkstra in M*longN( din cate imi aduc bine aminte este chiar N^3). Si in manulul lui Tudor Sorin( varianta pe care o am eu) heapurile apar cu mult dupa dijkstra.
Ideea ar fi ca in clase nu prea am auzit sa se predea asa ceva...

La zebughil am avut vreo 8 surse cu algoritmi diferiti eu si adi, de aia sunt cate trei teste, incercam sa combinam teste sa nu mearga nici greedy nici back nici random nici solutii neoptime ca timp. Cred ca numai daca dadeam n mai mare puteam cumva sa scapam, oricum un back un pic optimizat intr-o directie in care nu ne-am gandit noi probabil oricum ar fi mers pe testele generate impotriva algoritmilor pe care i-am fi implementat, problema ne-a placut mult si am stat pe ea si am lucrat-o dar se pare ca nu a fost de ajuns ... si eu sunt dezamagit de teste credeam ca dupa atatea implementari am scos niste teste bune. Pe de alta parte daca nu erau slabe testele la a 10-a era jale. Vom incerca data viitoare sa departajam mai bine solutiile.

Mi se pare un pic penibila asa zisa dificultate a algoritmului dijkstra... la mine in clasa intra 11-a s-a predat dijkstra cu heap. Se invata heapul, si se zice si aplicatia la dijkstra. Trebuie sa iti dea mura in gura ? Nu se poate zice ca minimul se poate extrage in log N si update-ul tot in logN ? Cine e pasionat si vrea mai mult [ lumea de pe infoarena ] va invata si M log N.

Deja devine off-topic ...

Idea e ca dijkstra M log N nu e asa de GREU si o pb. atat de clasik nu trebuie sa se dea la 100p.

Daca o persoana are pb. cu un amarat de dijkstra, poate ca concursurile infoarena nu sunt inca de ea .... :book:

Cat despre N ^ 3 sau N ^ 2 ... nu am de unde stii ... nu am implementat niciodata nici macar N ^ 2.

PS: un dijkstra mult mai greu este pb. 'Lanterna', care s-a dat la municipiu in 2004. Este si in arhiva si punctajul mediu este 79 pe ea , cu 34 de concurenti ... destul de mult.

PS: asta nu inseamna ca la mine in clasa algoritmul dijkstra nu se tocea inainte de teza :lol:. Dar s-a predat ....

multumesc vlade ;) succes si tie !

punctajele mici [cel putin in cazul meu] sunt din cauza ca nu am mai lucrat de mult la info din cauza ca nu e perioada de concursuri, nu exista nici o motivatie, sunt si alte lucruri de pus la punct..

eu sper [si sunt aproape sigur] ca rezultatele la urmatoarele runde o sa fie mult mai bune. asta a fost doar asa, de incalzire si de motivatie.

problemele nu pot sa zic ca au fost grele, sper sa se mentina nivelul de dificultate..

misto concurs! ..tot inainte

am si eu o intrebare... asa de curiozitate.

la distante erau muchii de cost 0? ca am pierdut ceva timp sa tratez cazu asta.. si m-am tzapit ca nu am mai avut timp sa implementez ca lumea zebu. X(

Eu vreau sa ii felicit pe organizatori pentru PreOni si pentru problemele propuse azi. Din pacate am fost plecat si nu am putut participa azi, dar oricum nu ma voi uita peste solutii, pana cand nu voi implementa ideile mele. Mult spor si la celelate runde.

Parca nu erau muchii cu cost 0. Initial am vrut sa fac o departajare mai mare intre Dijkstra cu heap-uri si solutia oficiala, dar fiindca a fost gandita ca problema usoara am lasat asa.. oricum pentru departajare trebuiau teste mai mari, si C-ul mergea destul de greu la citire.

unul sau mai multe noduri legate prin muchii de cost 0 vor fi legate de sursa prin drumuri de acelasi cost minim, evident. daca puneai un teste in care doua noduri legate printr-o muchie de cost 0, la care bronzarel gaseste o distanta mai mica decat cea reala, iar celelalte muchii incidente in cele doua noduri ar fi avut valori foarte mari, mai scadeai 10 p de la multi care au implementat solutia oficiala. insa atunci ar fi fost si mai incorect... cu dijkstra optimizat tot 100p s-ar fi obtinut.

Eu nu cred ca distante trebuia sa fie mai grea. A fost gandita ca problama usoara, nu ca problema medie si cred ca daca un dikstra cu heap lua 80p sau chiar 100 nu este nici o problema. Bineinteles, sunt multe probleme pentru care putem gasi mai multe solutii, unele elegante altele mai putin elegante, care sa ia punctajul maxim.
Nu stiu daca la clasele 11-12 nivelul ar trebui sa fie cu mult mai dificil decat a fost acum. Nu a luat nimeni 300, si noi am considerat ca este un concurs usor... Probabil ca nivelul de dificultate din viitor nu va fi foarte diferit de runda aceasta.

Exista o posibilitate ca sa nu stergi minimul in O(logN) si complexitatea sa fie curat O(m log N)? Complexitatea la dijkstra cu heap nu e de fapt O((n + m) log N)?

Folosing fibonacci heap se poate ajunge la complexitate de  (N log N) + M ( amortizata )... daca tot intrebai teoretic ...
 
Si cum de obicei M = O ( N^2 ) complexitatea de M log N este corecta ... depinde cat de riguros vrei sa fii ... varianta 'stiintifica' este intradevar complexitate de ( N+M ) logN ...

Ideea de baza e ca faptul ca are sau nu complexitatea ( N + M ) log N nu il face mai greu sau mai special .. tot de manual ramane ...  :P

Unul din motivele pentru punctajele mici de la clasa a 10-a ar fi problema Dreptunghiuri pe care nici o persoana nu a facut-o si pe buna dreptate... Vorbind cat se poate de serios asta e problema de 11-12 sau mai mult. La 11-12 n-a fost nici o problema la care sa trebuiasca sa te gandesti prea mult... Problema Distante e mult mai adecvata pentru clasa a 10-a.
Eu zic sa aveti mai multa grija ce probleme la ce clase propuneti. Nu stiu... poate e doar impresia mea, dar sunt destul de sigur ca si altii considera la fel.

Ne-am gandit sa nu dam grafuri la a 10-a pt ca nu se prea stiu ... Diferenta pentru nivelul unei probleme nu o face dificultatea ei ca idee ci structurile si nivelul de cunostinte de care este nevoie. La dreptunghiuri cunostintele necesare erau aproape inexistente, pentru 100 de puncte trebuia sa stii sa rezolvi ecuatii de gradul 2. Am stiut ca problema este grea da nu ni s-a parut inabordabila si implementarea este destul de lejera. Eu zic ca la 11-12 aveai nevoie de gandire daca nu te-ai fi intalnit cu o idee asemanatoare la problema cu matricea sau daca ti-era frica sa faci back la Zebughil.