infoarena

Runda 1 (http://infoarena.ro/algoritmiada-2013/runda-1) a concursului Algoritmiada 2013 (http://infoarena.ro/algoritmiada-2013) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/algoritmiada-2013/runda-1/clasament/5-9)!

Așteptăm opiniile și eventualele sugestii ale concurenților în legătură cu oraganizarea, subiectele propuse și orice probleme întâmpinate.

Mult succes în continuare!

Felicitari pt aceasta runda!
Problemele au fost interesante, pacat ca mi-am prins urechile la kinetic (nu sunt singurul)  :P

Salut!

Problemele au fost interesante, si cu toate problemele tehnice, runda a fost ok :) .

Ar putea cineva sa imi explice pe scurt care era ideea la kinetic (stiu ca vor fi puse si solutiile, dar multa lume nu are rabdare pana atunci :) ).

Wa pe testul 2 .. 90 de puncte.
Srsly? :))

Felicitari pentru runda! Problemele au fost super reusite.  :D

Frumoase problemele ! Felicitari organizatorilor , chiar si cu problemele tehnice runda a fost foarte reusita !  =D>

Mi-a placut runda :D . Putin ciudat sa se dea grafuri la a 10-a, dar imi place mult ca a fost diversitate :P

(http://i.imgur.com/XGrB4.jpg)

Foarte faine problemele. Critice2 mi s-a parut prea grea in comparatie cu restul. Eu personal la al doilea exemplu nu am priceput de ce e corect raspunsul.

Felicitari comisiei!  =D>

La Kinetic ideea e ca exista doar N ^ 2 momente in care se schimba ordinea relativa a punctelor. Daca iti generezi momentele astea si le sortezi, poti sa faci update-uri in timp real la ordinea punctelor iar apoi sa cauti binar. Evident, query-urile se parcurg si ele sortate dupa t, in paralel cu schimbarile de ordine.

Asa iese O(N ^ 2 log N + M log N). Din pacate, diverse optimizari la brut au adus punctaje foarte mari. E cam greu sa faci teste perfecte pentru o problema de genul asta. We'll keep that in mind :).

Desi inainte de chestia cu 1 000 000 aveam o gramada de idei pentru kinetic, dupa aceea s-au dus toate, si am bagat brute-ul  :aha: .

Runda a fost foarte reusita, felicitari organizatorilor!

La al doilea exemplu ai 2 muchii critice in graful initial: 1-5 si 7-8. In cazul in care niciuna din muchiile fictive nu apare, ai 2 muchii critice (cu o probabilitate de (1 - 0.5) * (1 - 0.123) * (1 - 0.752) = 0.108748), deci aduni la rezultat 2 * 0.108748 = 0.217496. In cazul in care muchia 2-8 apare, indiferent de celelalte 2 muchii, nu mai ramane nicio muchie critica, deci ai probabilitate 0.5 pentru 0 muchii critice. Acum daca nu apare muchia 2-8 si apar muchiile 4-7 si 6-8, de asemenea nu mai ramane nicio muchie critica. Daca apare doar muchia 6-8, ramane doar muchia critica 1-5, deci adunam (1 - 0.5) * 0.123 * (1 - 0.752) * 1 la rezultat, si daca apare doar muchia 7-5, ramane doar muchia critica 7-8 cu probabilitate (1 - 0.5) * 0.752 * (1 - 0.123). In final, avem 0.108748 * 2 + 0.015252 * 1 + 0.329752 * 1 = 0.5625.

Ne poate da cineva un hint la Critice2? Eu am pierdut aproape 3 ore pe problema si am gasit o solutie care imi dadea bine pe exemple si pe toate testele pe care mi le-am dat eu, dar am luat 0 si nu inteleg ce e gresit in rationamentul meu.

Mersi!

Eu am uitat de cazul in care nu apare nicio muchie  :oops:

Am adaugat problemele in arhiva !  :thumbup:

Se pot lua 90 de puncte la kinetic astfel: pt testele 1 2 3 5 brute, iar pt cele de la 6 pana la 10 ia OK o sursa gresita care cauta binar in functie de valoarea functiei la momentul T, chiar daca valorile celor N functii la acel moment nu sunt sortate  :P  :-'


LE: vad ca imi scade si karma cu ocazia asta, nu vad ce am zis asa rau

cand se va updata ratingul?

Ca sa incheiem(speram) cu problemele tehnice pentru runda asta, anuntam ca testele 5 6 si 7 de la critice2 au fost schimbate si sursele reevaluate. Acest lucru l-a afectat doar pe Mugurel Ionut Andreica, care a obtinut astfel 400 de puncte. Felicitari!

Ne cerem scuze din nou pentru toate problemele intampinate in aceasta runda.

Propun un nou format de concurs pentru Algorimiada cu urmatoarele categorii de varsta:

• Clasele 5-9
• Clasa a 10-a
• Clasele 11-12
• Open
• Mugurel

 :rotfl:  Just kidding

Felicitari Mugurel . Impresionant ca intotdeauna.
Felicitari Echipei Infoarena pentru problemele foarte interesante propuse.

Desi e scuzabil si de inteles ca uneori sa se mai strecoare cate o gresala intr-un enunt sau test, totusi sa fiu sincer runda asta mi s-a parut extrem prost organizata.

Nu e normal ca limitele sa se schimbe la jumatatea concursului, si mi se pare aiurea sa se schimbe restrictiile de timp. Faptul ca testele slabe, limita de memorie sau timpul de executie permit "bulanelilor" sa ia puncte trebuie anticipat/verificat inainte de startul rundei.

Iar legat de subiecte, desi runda a fost prelungita cu o ora pentru unii eu consider ca trebuia sa fie din start si pentru toata lumea o runda de 5 ore luand in calcul nivelul subiectelor. De altfel se si vede ca intr-o runda de calificare punctajele la varf sunt sub 150, iar mai jos...
Personal cred ca asta e si unul din motivele pentru care nivelul de participare este extrem de scazut. Daca inca de la prima runda subiectele sunt foarte grele multi sunt descurajati si considera ca nu mai are rost sa participe in continuare. Deja la ultima runda primii vor fi deja calificati, ceilalti nu vor mai avea nicio sansa si nu va mai participa nimeni.
La grupele 5-9 si Open cred ca ar fi loc de 4 probleme dintre care 2 sa fie simple, astfel incat cei care sunt la inceput cu algoritmica sa nu se simta total outsideri. Ori la runda asta nu a existat nicio problema simpla, nici macar medie, ceea ce se reflecta si in punctajele concurentilor si numarul redus de participanti.

Odata ce ati stabilit un set de probleme ganditi-va si la cat de dificil este setul respectiv, si ganditi-va si ca nu toti au nivelul de cunostiinte si experienta multor olimpiade si concursuri, asa ca trebuie sa estimati dificultatea la un nivel mediu.

Impresia mea a fost ca la runda asta ati bagat la repezeala 3-4 probleme + ce mai era pe stoc si gata runda, norocul a fost ca nu s-a tinut acum 2 saptamani cum era planificat.

In primul rand tin sa subliniez ca tu ai fost in comisia oni 2012 unde subiectele au fost cum au fost, deci stii si tu ca nu tot timpul se pot da subiecte perfecte. Si la oni au fost date exemple gresite la unele probleme. Nu ai cum sa eviti unele chestii totusi la 11-12 nu cred ca s-au luat punctaje mari cu bulaneli.

La 11-12 setul a fost echilibrat: a fost o problema simpla kinetic, una medie mvc si una posibil prea grea critice2.
La open a fost mvc problema simpla care ar trebui sa fie cunoscuta de multa lume fiind o dinamica clasica pe arbore la care se mai adauga o observatie smechera. Interzis nu era o problema atat de dificila. Iar taie si critice2 faceau diferenta.

Mi se pare aiurea sa comentezi cand problemele chiar au fost foarte reusite si bine alese daca analizezi asta stiind rezolvarile.


Da la oni cum faceti ? Sa nu imi zici ca va intalniti inainte de mai multe ori ca sa alegeti subiectele. Din cate stiu eu problemele au fost pregatite din timp. De ce nu te implici tu in infoarena sa dai probleme mai reusite?  :fighting: Nu cred ca e nimeni obligat sa-ti dea tie gratis probleme pe care sa le rezolvi.

Astept din partea ta sa dovedesti ca poti da probleme mai bune ca la algoritmiada. Nu mai zic si de fmi unde ai fost in comisie, iar acolo neplacerile create au fost mult mai mari.

Am scris postul respectiv in ideea de a atrage atentia asupra unor aspecte care scad popularitatea concursului si a infoarenei. Prin posturi de genul "marfa, sa o tineti tot asa" nu se aduce vreun castig, decat eventual la nivel emotional motivational, nu si calitativ.

Petru, deci in opinia ta mvc era medie la 11-12 si simpla la open. Deci tu nu ai inteles chiar nimic din ce am zis.
Legat de oni nu pot sa iti dau raspunsul pe care ti l-as da in mod normal tocmai pt ca reprezint un grup de oameni si nu doar pe mine. Iar legat de atacul la persoana pe care l-ai lansat iti spun doar ca e un gest urat care nu isi are locul pe acest forum si incheiem discutia aici, nu ma intereseaza parerea ta despre mine.

Vlad are dreptate si ar trebui apreciate comentariile lui. Totusi, cred ca majoritatea membrilor din echipa infoarena sunt constienti de aceste probleme, iar ceilalti sunt membrii noi si au nevoie de momente ca acestea sa invete, deci n-ar trebui trecute cu vederea.

Legat de dificultatea problemelor, e adevarat ce spune Vlad cu necesitatea de a exista probleme (foarte) simple la fiecare grupa pentru a incuraja noii participanti si pentru a tine competitia deschisa. De acest lucru este in special nevoie cand se schimba generatiile, ca acum. Pe de alta parte, daca nu se dau niciodata seturi de probleme grele, vom ajunge sa avem o mare masa de programatori care nu sunt competitivi la nivel international. Si in final, nimanui nu-i place sa propuna probleme simple pentru ca nu aduc nici un castig (recunostinta, provocare intelectuala, etc.) celui care le propune. Probabil ca solutia aici ar fi sa avem seturi de probleme foarte clar departajate: cu probleme foarte simple, medii si ruperi (dupa modelul topcoder).

Din experienta mea, presiunea pentru a organiza un concurs de programare online e mult mai scazuta decat cea la concursurile onsite. De aceea, olimpiada nationala nu se compara cu Algoritmiada. Cred ca aici ar trebui sa inteleaga ce a gresit comisia si sa evite sa mai repete astfel de greseli. Posibile solutii: sa verifice enunturile mai in serios, sa analizeze mai exact dificultatea solutiilor, sa petreaca mai mult timp incercand sa gaseasca solutii neoptime care pot obtine punctaje mari, sa se apuce mai devreme de lucru, etc. In plus, daca intreaga comisie este mai responsabila, atunci efortul individual e mai scazut.

Fara sa ma mai cert si sa atac pe nimeni vreau sa analizez putin setul de la open.

In primul rand daca ne uitam pe clasament vedem ca fiecare problema a fost rezolvata de cel putin un om deci nu au fost probleme prea grele.
Problema interzis a fost rezolvata de 11 oameni deci a fost bine aleasa.
Problema mvc se reducea la o problema de dinamica destul de clasica: Dandu-se o firma sub forma de arbore sa se invite un numar minim de angajati astfel incat sa nu existe doi angajati astfel incat unul din ei sa fie seful direct al celuilalt.
Celelalte doua probleme au fost problemele grele care trebuiau sa faca diferenta.
In concluzie doua probleme simple si doua dificile  :ok:

Mie mi se pare un set de probleme echilibrat care departajeaza corect concurentii, iar asta se vede si din clasament. In plus nu mi se pare ok ca o singura problema sa faca diferenta intre primele locuri deoarece s-ar lasa loc de bulaneli.

Parerea mea e ca exista probleme foarte simple la monthly, concurs cu multe runde, si el se poate ocupa de partea de incurajare. Dificultatea problemelor la aceasta runda mi s-a parut a fi cam ce ar trebui sa fie la algoritmiada (in afara de problemele tehnice).

Petru: Tin sa spun ca nu prea ai dreptate din mult puncte de vedere. In primul rand ai spus ca neplacerile aduse de fmi au fost mult mai mari ca la algoritmiada si asta este TOTAL FALS. In afara de testele proaste de la drum4 de care am fost foarte nemultumit concursul a fost bine organizat si nu prea a avut probleme tehnice. Fie ca ti-a placut concursul, fie ca nu, nu poti zice ca oamenii nu au fost seriosi. Algoritmiada in schimb a fost organizata de data asta foarte prost. Cu foarte putina mea experienta in organizat concursuri mi s-a parut evident ca de data asta echipa infoarena nu a fost prea serioasa si am o presimtire ca nici ei nu pot nega asta. In primul rand a fost schimbata o restrictiie foarte importanta. Chiar daca au mai dat o ora in plus, eu care eram super obosit m-am enervat super repede. Dupa au zis la inca o problema ca valorile sunt pana in 20000 si nu pana in 15000. Dupa au uitat sa adauge feedback la critice(asta nu e grav, se mai intampla dar putem numara). Dupa la jumatatea concursului au MICSORAT limita de timp la aceesi problema.  Sa nu mai mentionam de cate ori au schimbat testele si au reevaluat problemele. Deci aceasta runda a fost pe departe cea mai prost organizata runda ever de algoritmiada. Acuma tu esti putin cam copil  :) (nu o zic cu rautate). Adica observ ca zici de toate concursurile la care faci bine ca au fost foarte bine organizate si subiectele au fost foarte bine alese. Sa stii ca uneori cand zici ca subiectele au fost foarte bine alese, se poate ca nici macar comisia sa nu prea fie de acord cu tine. Si mie personal mi-au placut cat de cat subiectele la runda asta dar sunt de parere ca nu au fost foarte bine alese (parca nu se prea completau una pe cealalta) iar cu problemele tehnice daca aveai o zi proasta iti cam bagai picioarele. 

Inchei prin a spune ca desi au existat multe runde mult mai reusite, runda nu a fost chiar asa crima. Eu vreau sa fiu doar realist. Nu vreau nici sa laud nici sa fac scandal ca penalu pe aici. Adica eu stiu ca se mai intampla si echipa IA si-a dat silinta cat a putut. Astept sa ne loveasca cu runda 2 mai puternic ca niciodata  :D.

PS Petru: nu trebuie sa zici "fara sa ma mai cert" deoarece aici noi toti suntem prieteni si de asta a fost facut forumul ca sa discutam. Daca vrei sa ma contrazici cu ceva te rog nu ezita. Tin sa mentionez si sa te asigur doar ca eu si cu Vlad nu suntem singurii cu feedback prost. Mai intreaba lume si mai analizeaza pareri :).

La Kinetic, nu e posibila si o abordare cu arbori de intervale sau AIB?

Mie mi-au placut mult problemele de la runda asta de Algoritmiada (ma refer acum doar la cele de la Open, caci doar pe ele le-am citit, dar cum ele au facut parte si din setul de probleme de la celelalte clase, reprezinta o vedere destul de buna asupra intregii runde).

Partea de organizare a avut, intr-adevar, cateva probleme (probabil mai multe decat la alte runde de Algoritmiada). Printre cele de care m-am lovit eu sunt urmatoarele:

- la "interzis" luam TLE pe testul de feedback 9 (desi aveam complexitate O(N*L), care banuiesc ca e si complexitatea solutiei oficiale...) : m-am gandit ca e din cauza ca o exista o solutie de complexitate mai buna de atat si am pierdut ceva timp incercand sa o gasesc (fara succes) ; pana la sf. concursului acceptasem ca o sa iau TLE pe testele 9 si 10, dar se pare ca aceste teste aveau N-ul mai mare decat in enunt si au fost modificate (cand N-ul a fost redus la <= 15.000 sursa mea a intrat in timp) ... inca nu stiu daca ar fi trebuit sa intre in timp si pe testele initiale (cu N <= 20.000) ; nu stiu daca schimbarea testelor si reevaluarea au avut loc in timpul concursului, caci nu am mai verificat feedback-ul la sursa mea dupa ce am decis sa trec la urmatoarea problema

- la "critice2" am terminat sursa cu 30 min inainte de finalul concursului, am trimis-o si luam WA pe cele 2 teste de feedback... am inceput sa-mi generez teste (de mana, ca sa le pot verifica, apoi mai mari ca sa vad ca nu da vreun rezultat aiurea) in speranta ca o sa-mi gasesc bug-ul... nu am gasit.. am mai facut mici modificari si am tot retrimis sursa, insa am luat mereu WA.. ultimele 30 min le-am petrecut incercand sa inteleg ce e in neregula cu sursa mea... pana la urma am renuntat, iar la sf. concursului credeam ca o sa iau 0 pe sursa... se pare, insa, ca eval-ul nu era chiar OK la momentul respectiv (nu verifica cu precizia mentionata in enunt, ci verifica ca output-ul sa fie identic cu cel al comisiei... eu am incercat sa afisez ori cu 4 zecimale, dupa cum se preciza in enunt, ori cu 7... output-ul comisiei banuiesc ca era generat cu 6 zecimale... daca afisam si eu tot cu 6, probabil scapam de 30 min de stress in incercarea de a debug-a o sursa corecta :) )

- la "taie" limita initiala de timp era, parca, de 0.2 secunde; eu am implementat o solutie in O(N^2 * log(N)) despre care eram sigur ca nu va intra in timp (nu doar din cauza complexitatii, dar si pt ca apelam atan2 de O(N^2) ori, ceea ce e destul de time-consuming) ; ma gandeam ca trebuie sa existe o solutie in O(N^2) pe care urma sa incerc s-o gasesc daca mai aveam timp la final (ceea ce n-am mai avut) ; pana la urma am avut noroc ca s-a marit limita de timp si solutia mea s-a incadrat in aceasta limita de timp (desi as fi foarte curios sa stiu o solutie de complexitate mai buna decat O(N^2 * log(N)).. sau macar una care nu foloseste unghiuri atat de mult precum solutia mea)


Insa nu pot sa ma plang de un concurs organizat de voluntari (de ex., la TopCoder ar avea sens sa ma plang daca ceva e in neregula cu problemele, caci acolo oamenii sunt platiti pt pregatirea si testarea problemelor... la fel pe Codechef... pe Codeforces nu stiu cum sta treaba.. cred ca si acolo e activitate voluntara, insa nu stiu sigur ; si astea sunt celelalte 3 site-uri la care particip la concursuri in mod regulat). Ce-i drept, insa, astfel de probleme de organizare ar putea descuraja unii concurenti de la participarea la Algoritmiada.

Relativ la dificultatea problemelor, cel putin la grupa Open, nu as putea sa zic ca as putea eticheta vreuna din probleme ca fiind "simpla" (asta nu inseamna ca, de exemplu, solutiile la "mvc" si "interzis" nu mi s-au parut evidente, dar stiu ca aceste probleme ar fi etichetate cel putin "medii" daca ar fi considerate pentru a fi propuse la olimpiada nationala de informatica - clasele 11-12).

Desi mie imi plac problemele challenging, cred ca sunt partial de acord cu parerea exprimata de Vman intr-un post anterior. Cred ca daca unele probleme ar fi in mod evident mai simple (ori efectiv mai usoare, ori in mod direct mai clasice -- nu ca in sensul de la "mvc" ca se pot reduce la ceva mai standard, ci sa fie "pe fata" ceva clasic/standard), mai multi concurenti s-ar simti incurajati sa participe. In plus, la astfel de probleme mai simple si munca comisiei ar fi mai usoara (existand sanse mai mici sa greseasca la limite, teste, etc.).

Anyway, este doar la latitudinea echipei infoarena sa decida formatul si dificultatea problemelor propuse la Algoritmiada.


In incheiere, arunc si eu o parere personala (pe care am mentionat-o si acum mai multi ani conducerii infoarena de atunci). Cred ca concursurile de pe infoarena ar beneficia de o participare mult mai mare daca enunturile ar fi propuse in lb. engleza (asta ar implica si faptul ca o parte a site-ului sa fie in lb. engleza). Cred ca un exemplu foarte bun este Codeforces, care are continut in rusa si engleza si are foarte multi utilizatori internationali. Bineinteles, nu stiu cat de fezabila ar fi o astfel de idee (ca volum de munca) sau cat de dezirabila (acum mai multi ani mi s-a spus ca infoarena e gandita pt elevii din Romania, astfel ca o sectiune in lb. engleza nu si-ar avea rostul avand in vedere "publicul tinta" -- am parafrazat eu, caci nu mai tin minte cuvintele exacte).

De ce nu este permis accesul la articolul cu solutii? :-s http://infoarena.ro/algoritmiada-2013/runda-1/solutii (http://infoarena.ro/algoritmiada-2013/runda-1/solutii)

Eu am acces, insa e gol articolul, momentan...

@VisuianMihai : Ciprian se referea la faptul ca nu poate sa editeze pagina, nu ca nu poate sa o vada.

@scipianus : Nu pagina aceea trebuie editata (deoarece ea este doar "un fel de template"), ci paginile corespunzatoare fiecarei probleme (daca modifici in ele apare automat si acolo pentru ca sunt incluse):

De fapt ma refeream ca la vremea aia cand dadeam pe link ma ducea pe pagina principala infoarena cu acel chenar rosu in care zice ca n-am drept de acces,etc.  :)