infoarena

Am dezghetat clasamentul si am adaugat problemele in arhiva ACM. Descrierea solutiilor in curand.

Felicitari echipa_BoSSilor! singura echipa care a rezolvat 10 probleme.
UPB Banu Popa Visan - locul 2 la studenti
Unibuc - Mita Nitu Velea - locul 3
UNIBUC_Costan_Iordache_Magureanu - locul 4
si echipelor de elevi care au rezolvat 8 probleme, in special CNFB Udristoiu Linca Dicu - toti elevi de gimnaziu.

In urmatoarele zile vom face un clasament filtrat pentru echipele de studenti.

Problemele
1.Consecutive:http://www.infoarena.ro/problema/numar.
2.Padure:http://codeforces.com/contest/559/problem/C.
3.PQ foarte tare se aseamana cu http://codeforces.com/contest/522/problem/D si daca schimbat un pic solutia (citeva rinduri) din problema prezentata de mine obtinem solutia la PQ.
4.Tribut este problema destul de clasica,miroase a flux maxim de la un kilometru.
5.Twoton,nu cred ca e cea mai potrivita pentru acm icpc dar oricum in cel mai rau caz se poate de luat.
6.Carte,este foarte ok pentru incepatori.
7.Politie am inceput sa citesc enuntul,parea interesant si pina la urma nimic n-am inteles chiar daca m-am uitat la explicatiile,numai eu asa?
Celelalte probleme nu leam mai citit(nu am mai vazut sens sa particip cind sunt deja 3 probleme cunoscute),deci nu spun nimic.
Cel mai bun s-a pus limitele la problemele Consecutive,Tribut,Carte,Twoton si PQ(in special PQ).
La problema Padure nu pot sa tin 2 arrayuri cu factorial si inversul lui din cauza limitei de memorie(de ce asa? la ACM ICPC sunt 1024 MB memorie conform online.acmicpc.org),de acea am calculam online inversul si am obtinut 4 WA - uri degeaba.
O idee ar fi sa puneti standart input/output pentru ca sa fie mai comod.  

Foarte tare ce ati facut la Robo.

Ati lasat linii goale in input la o problema la care folositi newline-ul ca informatie FARA sa spuneti in enunt. Ati anuntat in ultimele 15 minute si asta la intrebarea noastra.

Va era greu sa prefixati linia starilor finale cu numarul de noduri ce trebuie citite ..?

Am si eu o curiozitate legata de problema Metrou4.
De ce ideea de arbore partial de cost minim folosind distanta Manhattan nu a fost potrivita pentru un concurs gen Algoritmiada si pana la urma s-a dat "Happy Birthday Infoarena 2014" (http://www.infoarena.ro/problema/rrmst) dar totusi a fost buna pentru Nationala ACM?

Problema a mai fost propusa si pe Codechef (https://www.codechef.com/LTIME15/problems/DRAGONST).
Exista chiar si un tutorial pe Topcoder (https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/).

Echipa noastra este formata din Harsan, Bicsi si Baltatu (toti 3 studenti).

In problema E (Metrou4), din enuntul aferent se intelege construirea unui arbore Steiner pe distante manhattan. (Mai exact, https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree ). Scrollam putin pe articol si aflam ca este o problema NP. Aparent, enuntul a fost ambiguu si presupun ca mai toata lumea l-a inteles gresit. In realitate, era un MST pe distante manhattan (ceea ce nu se intelege din enunt).

Legat de problema Robo nu vreau sa ma pronunt, dar sunt n motive pentru care consider ca nu ar avea ce cauta in acest concurs (unele dintre ele sunt chiar sinistre). Am vorbit despre asta si consider ca nu e deloc in regula ce s-a petrecut. (cautati Automaton Minimization)

Problema Padure2 "a mai fost data la un CF" (Harsan), ceea ce nu e neaparat un lucru rau, dar creeaza dezavantaje pentru unele echipe.

Sunt curios daca a existat o echipa in concurs care sa nu "bulaneasca" solutia de la problema Sate2 (daca da, sunt curios ce solutie aveti :) )

In rest, problemele au fost ok. De apreciat faptul ca runda aceasta (echipa noastra cel putin) nu am mai intampinat probleme legate de limitele stranse de timp.

Concursul asta imi aduce aminte de felul in care se desfasura regionala inainte sa se bage ucrainienii mai serios in comisie.

Foarte reușită problema PQ.
Problema Tribut a avut enunț greșit (încă are) și anume:
În „Date de ieșire” e scris „valoarea maximă a tributului pe care o va primi de la toate sistemele solare.” pe când sursa care afișa valoarea maximă a tributului pe care o primește doar de la uniuni comerciale lua AC și cea care socotea și sistemele solare WA. (Ar fi bine să corectați, măcar pentru arhivă).

p.s. Nasol că la Națională au fost probleme din alte concursuri. : )

Este corect enuntul. Este valoarea primita de la sisteme solare, uniunile au doar rolul de a regula cat anume da fiecare sistem solar (gandeste-te la uniunii doar ca la niste reguli pe care le respecta sistemele, tot sistemele sunt cele care dau banii in final :) ).

Foarte frumoase problemele la aceasta runda, felicitari comisiei :D

Totuși, în enunț scrie „TOATE sisteme solare”, dar cele care nu au uniune, acelea nu plătesc (în soluția de 100)

Da, ai dreptate. E bine ca din implementarea normala de flux, cele care nu sunt legate la nicio nod "uniune" oricum nu au cum sa trimita flux, fara a trebui sa fie considerat caz particular.

Da, dar unii (Echipa mea) a avut de pierdut din cauza acestei neclarități (bine, nu cotează asta așa mult), de asta zic că ar fi bine să fie schimbat.

Hm.. sorry ca seamana atat de mult. Se vede ca nu mai sunt la curent cu ce probleme se dau pe la concursuri - daca stiam problema asta de pe CF, probabil nu mai propuneam PQ. Initial aveam o problema mai complicata, care avea PQ ca subproblema - si pt ca nu am avut timp sa pregatesc serios problema initiala, am decis sa propun doar subproblema :) (adica PQ). Singura "consolare" este ca problema de pe CF nu are editorial (sau eu, cel putin, nu l-am gasit), asa ca macar solutia nu era explicata in mod direct pe undeva.

Anyway, nu stiu cum au aratat solutiile, in general, la PQ, dar sunt curios daca vi se parea mai potrivita/interesanta daca query-urile erau online (adica parametrii L, R ai unui query depindeau de rezultatul query-ului anterior) - in felul asta solutiile bazate pe sortarea query-urilor nu mai functionau. Solutia mea functioneaza online si klamathix (http://www.infoarena.ro/utilizator/klamathix) mi-a sugerat sa fac problema online, dar nu l-am ascultat :)

Ai putea descrie cum se face online problema ?

@Djok Poti folosi un arbore de intervale persistent in care sa stochezi care este distanta maxima dintre doua elemente care respecta conditiile din enunt (fiecare frunza mentine distanta pana la urmatorul element cu aceeasi valoare; fiecare nod intern mentine maximul celor doi subarbori).
Astfel, cu o preprocesare O(NlogN) atat timp cat si memorie poti raspunde sa intrebari la intrebari online, in O(logN).

Pot sa incerc sa detaliez solutia si/sau sa adaug cod daca este cazul.

Mai trebuie să treacă ceva timp pînă o să înțeleg structuri persistent, dar mulțumesc pentru explicație)

Problema are editorial numai ca este in rusa.
Cred ca este mai bine versiunea offline fiindca mai multi participanti o pot incerca,versiunea online ar putea-o face prea grea pentru unii care au rezolvat-o.

Scuze de intarziere. Am updatat articolul cu solutii http://www.infoarena.ro/onis-2016/solutii-runda-2 (http://www.infoarena.ro/onis-2016/solutii-runda-2) , intre timp am vazut ca s-au trecut solutiile acolo la multe din probleme, multumim Vlad Dumitru-Popescu pentru ajutor. Legat de unele observatii de mai sus:

* la consecutive imi era clar ca e o problema clasica care sigur s-a mai dat pe undeva, ce-i drept nu stiam ca e fix in arhiva infoarena ceea ce a picat mai prost. Dar oricum era o problema pentru echipele incepatoare, sper ca nu a avut nici un efect pentru varfuri. Ideal ar fi ca Nationala ACM / ONIS sa se tina pe un site separat si cu limitarea accesului in afara.

* la padure2 clar nu mai merge argumentul de mai sus din pacate ... pentru ca e o problema mai serioasa ce face departajare intre echipe mai bune. Eu nu stiam de problema de pe CF si chiar cred ca nici autorul - imi dau seama ca nu pare credibil  :) -, scuze oricum pentru situatia asta. Si pentru limita de memorie cam stransa, am lasat doar ce era default in infoarena si am vazut ca ambele surse oficiale intra in timp si memorie din prima destul de relaxat, nu mi-am mai pus probleme.

* AlexandruValeanu: nu cred ca "standardul" Algoritmiada este fezabil pentru ONIS sau chiar Nationala ACM ICPC, din pacate, sunt mai multe probleme in set si mai putin efort investit in asta overall, relativ.. De exemplu Nationala ACM in 2013 a fost doar o simulare pe TJU. Dar nici nu e bine sa folosim asta ca scuza ...

Despre celelalte probleme nu stiu prea multe, prefer sa nu ma pronunt. Daca e ceva care pot repara la probleme la arhiva nu ma deranjeaza (clarificari enunturi etc; + o sa vb cu Djok in privat).

@All: in general e bine sa treceti numele universitatii in cont, dupa cum era regula la ONIS in trecut. Este destul de probabil acum sa avem o finala ONIS, cel mai probabil in weekendul 24-25 Septembrie, scuze pentru interni plecati in strainatate. Incercam sa o multam mai in Octombrie, dar e si SEERC-ul cam devreme ... si frumos ar fi sa fie inainte de SEERC.

http://students.info.uaic.ro/~paul.diac/acm/2016/acm/ACMICPC_Ro2016.html (http://students.info.uaic.ro/~paul.diac/acm/2016/acm/ACMICPC_Ro2016.html)
Clasamentul filtrat de la Nationala ACM, evident cam aproximativ, sa-mi spuneti daca ceva nu e ok. Poate fi folosit pentru a stabili echipele calificare la SEERC din universitati.

http://students.info.uaic.ro/~paul.diac/acm/2016/onis/ONIS2016.html
Clasamentul cumulat ONIS; normal echipele eligibile sunt doar cele de studenti. Dar cel mai probabil se vor admite si elevi de clasa a 12-a care merg la aceeasi universitate, care vor admisi la facultate in septembrie. (asa e si la ACM iar acum daca finala ONIS e toamna cred ca vom aplica aceelasi principiu).

In primul rând nu știu de ce mai numiți chestia asta încă un concurs. Articolul cu solutii este foarte ajutator, nici nu gasesti solutiile problemelor in editoriale de pe codeforces sau in primul link de pe google (stiu stiu, o sa ziceti ca daca scriu asta insemna ca am cautat chiar eu solutiile in timpul concursului, dar nu este adevarat :) ). Daca nu stiati ca anumite probleme au fost propuse pe CF atunci nu sunteti capabili sa propuneti probleme pentru concursuri, mai ales nationala ACM. Sunt mai multe variante pentru a rezolva asta, una din ele contactati anumite persoane din industrie care stiu cu ce se mananca algoritmica si au habar de ce se intampla in prezent. Sa va reamintesc ca au trecut vremurile in care propuneati probleme pentru OJI, la ACM e cu totul alta poveste. Mai mult decat atat, exista multe echipe care au trimis solutii de pe conturile personale si asta nu e corect deloc. Puteti verifica asta foarte usor, sa va spun si cum: contactati un admin infoarena sa va puna la dispozitie toate sursele trimise in timpul concursului dupa care folositi un tool sa va spuna cat de asemanatoare sunt sursele intre ele si e foarte simplu (seamana mai mult de 70, 80% => descalificare). Cititi asta http://theory.stanford.edu/~aiken/moss/ :). Cu placere! Nu este in regula sa inchideti ochi si sa va bateti joc de cei care au fost corecti, asa ca luati masuri. Explicatii nu puteti sa dati, am vazut, pentru ca nu exista. Cei mai minunati organizatori de concursuri, va multumim foarte mult pentru timpul acordat organizarii acestui concurs de 2 lei, dar daca nu puteti face asta, va intelegem, nu avem nevoie de voi pentru a departaja niste echipe!

Nu întreb cu rău sau provocator, sunt aproape de aceeași părere ca tine.

Ce propuneri ai? Cum s-ar putea proceda în continuare ?
Aș vrea ca la fiecare propunere(idee) să-i pui un punctaj de la 1 la 100. Punctajul să reflecte „cît de pragmatică este propunerea”.

Eu nu am altă idee, înafară de a face încă o rundă ca să o înlocuiască pe asta, dar în același timp îmi dau seama că punctajul este de  aproximativ 20%. Adică nu e foarte pragmatică, din simplul motiv că nu sunt destule persoane interesate ca să facă încă o rundă (chiar dacă sunt, pentru tine ei ar fi incomentenți). Runda aceasta tot a fost „trasă de urechi” (presupun) și s-a primit ce s-a primit.

Sau ați putea apela la niște profesioniști (https://csacademy.com/).

Eu, ca participant, m-aș bucura dacă ați putea colabora, pentru runde cît mai bune : )

Momentan nu suportăm concursuri de tip ACM ICPC. Pînă la anul va fi gata.

Pai, în primul rând, ați putea sa vedeți ce echipe au copiat. După cum am spus, este destul de uşor. Apoi, nu vad de ce nu se reorganizează runda. Este normal să fie echipe (chiar multe) care nu îşi doresc asta deoarece fie au trişat şi nu vor mai obţine acest punctaj într-un context normal fie sau s-au calificat şi nu le pasă. Cele care s-au calificat şi merită asta, nu cred că ar avea mari probleme în a mai demonstra încă o dată ca îşi merită poziţia. Puteţi să incepeţi cu asta prin a mai remedia ce a mai rămas din această încercare de concurs. Pe viitor, ar fi de recomandat să întrebați anumite persoane dacă au mai întâlnit problemele în alte concursuri (persoane care participă activ sau urmăresc ceea ce se întâmplă şi nu sunt concurenţi la ACM).

Cât ține de un scor pentru fiecare propunere: verificarea plagiatului - 100, reorganizare - 100, verificarea ca problemele să nu mai fi fost propuse pe alte platforme - 80. Sunt nişte cerinţe normale, unele precizate chiar în regulamentul ACM.

Pe langa problemele copiate, sa nu uitam de problema Politie, care e gresita.

În contextul unui spațiu ideal, aș fi de acord cu tine. Dar să vedem ce zic organizatorii, ce putere mai au ei ca să schimbe lucrurile.

Da.... Clar și asta, o problema greșită, la nivelul asta...
@Djok Organizatorii nu se deranjează nici măcar sa răspundă asa ca nu ne facem mari speranțe. Dar poate se găsește cineva să ia în calcul acest feedback.

Salut,

Eu nu am fost implicat serios în organizarea acestui concurs, dar am vorbit puțin cu organizatorii, iar concursul fiind găzduit de infoarena, îmi permit să răspund eu pe cât de oficial pot în momentul de față. Concursul a avut clar niște defecte grave.

Problema Poliție a avut enunțul ambiguu, ambiguitate peste care unele echipe au trecut fiindcă una dintre interpretări te ducea imediat cu gândul la o soluție "tipică" (o adaptare a Kruskalului), ceea ce nu este în regulă.

S-a discutat mai puțin, dar problema Metrou a avut și ea enunțul incorect. Se înțelege din enunț că ceea ce se cere este un "Rectilinear Steiner Tree" (care de altfel e și NP-Hard), deși intenția autorilor era să fie un APM cu distanță Manhattan între puncte.

Problema Robo are un enunț prea clasic, iar inputul avea un format groaznic.

Despre problemele care au apărut în forme foarte similare pe Codeforces: Eu sunt în general destul de strict cu chestiile astea și e într-adevăr regretabil când apare posibilitatea ca unii concurenți să fi știut problema în prealabil. Totuși trebuie să remarc că s-a ajuns la o poziție destul de extremă și puțin deconectată de realitate în legătură cu incidentele de genul ăsta.


Îmi pare rău, dar asta este pur și simplu fals. Puteți citi lanțul ăsta de comentarii (http://codeforces.com/blog/entry/45080?#comment-296331) de la Code Jam Runda 2, ca să vedeți că se întâmplă la case mult mai mari. În speță, observați cum zice SnapDragon (care este un zeu al comisiilor) că a propus o problemă la finala ACM-ICPC care exista deja pe TopCoder, și vorbim de o finală la care cu 4 probleme puteai lua medalie. Citiți și cum Smulewicz, din echipa Varșoviei, era pe cale să o propună a 3-a oară, în mod independent, înainte să simuleze finala respectivă  :). În ritmul în care apar concursuri noi astăzi este imposibil să se excludă coliziunile de genul ăsta în totalitate. Singura problemă (una foarte reală la noi în țară, din păcate) este ca aceste coliziuni să nu se întâmple din cauza unui plagiat conștient. Din punctul ăsta de vedere am încredere deplină în ce zice Paul Diac, iar pe Mugurel cred că îl știți suficient de bine încât nici să nu se pună problema. Also, cum a spus și Paul, concursul ăsta era o rundă pe TJU până prin 2013. Deci toate problemele de la acele naționale existau deja altundeva, de ani buni. Nu e în niciun caz un motiv să ignorăm greșelile prezentului, dar dă totuși puțină perspectivă în legătură cu evoluția ACM-ICPC-ului la noi în țară în ultimii 3 ani.

Acum soluțiile. O altă rundă sunt destul de sigur că nu se va organiza, fiindcă nu există resursele necesare, iar asta e o perioadă aglomerată pentru toată lumea. În același timp, runda asta nu este în mod obligatoriu eliminatorie. Ea este o fază necesară în calendarul ACM-ICPC, dar fiecare antrenor poate decide dacă o va folosi ca criteriu de selecție pentru calificarea la regională. Pentru echipele de la UNIBUC concursul ăsta nu este decisiv în niciun fel și nu a fost de ceva ani. Putem contacta toți antrenorii pentru a-i face conștienți de acest lucru, în caz că nu sunt. Noi la UNIBUC vom ține cel mai probabil niște baraje în toamnă și suntem bucuroși să primim și alte echipe.

În concluzie, dincolo de reacțiile la problemele similare, pe care le-am considerat irezonabile într-o anumită măsură, sunt de acord cu voi că au existat probleme grave în concursul ăsta. Îmi cer scuze în numele comisiei și îmi cer scuze și personal fiindcă nu m-am implicat cât ar fi trebuit și nu am sesizat din timp aceste erori. Îmi propun ca pe viitor să fac asta pentru toate concursurile ținute pe infoarena. În condițiile în care antrenorii voștri sunt de acord (iar noi le vom atrage atenția în acest sens), este perfect fezabil ca acest concurs să nu vă afecteze calificarea la regională.

Mulțumim pentru răspuns! :) Încă o observație referitoare la soluțiile propuse: au existat multe echipe care au copiat, din cele spuse nu cred că se va investiga asta, dar ar fi ok ca pe viitor să se țină cont.

Da, am uitat să adresez subiectul ăsta. În principal copiatul se rezolvă cu o supervizie atentă on-site. În legătură cu trimisul de pe alt cont, asta e mai problematic. La un concurs on-site (spre exemplu finala ONIS) în general supraveghem clasamentul suficient de atent încât să detectăm anomalii de genul ăsta live. Ne vom gândi la ce soluții mai sistematice există, luăm în calcul și detectorul de plagiat pe care l-ai menționat (deja îl folosim intern pentru temele de la cercul de algoritmi din UNIBUC). Între timp voi face publice sursele din concursul ăsta, ca să poată investiga oricine dorește.

Am facut mici modificari in enunturile problemelor la arhiva:
Politie: la restrictii am pus P < N (in loc de <=)
Tribut: la date de iesire: "o va primi de la toate sistemele solare care fac parte dintr-o uniune comercială.".
Exista istoric deci pot sa fac revert daca e ceva rau. Multumim Djok pentru ajutor.

Ca si antrenor la UAIC o sa ma uit putin peste sursele trimise in timpul concursului (de pe mai multe conturi etc, ceea ce am facut si in concurs) si daca detectez ceva rau care afecteaza calificarea la SEERC, o sa sanctionez evident cazul. Daca stiti ca sunt probleme cu asta legate de calificari, ar fi bine sa vorbiti cu antrenori vostri.

Mi se pare ca tot comentezi, dar pana acum ai avut 0 implicare in comunitate. Intr-adevar concursul nu a fost printre cele mai bune. Totusi mi se pare nesimtit sa comentezi fara sa ajuti in vreun fel.

Petru, în titlul acestui topic este inclus cuvântul "feedback. Dacă lumea nu ar "comenta" cum zici tu, cum ar putea comisia să observe unele greşeli pentru a le repara pe viitor?
Într-adevăr, ajutorul venit din exteriorul comunităţii este foarte important dar şi critica (în mod constructiv) are un rol care nu trebuie neglijat.

Nu vad de ce trebuie sa ma implic (sub un anumit sens al cuvântului implic) în comunitate pentru a semnala niște erori destul de importante. Pe lângă asta, prin acordarea unui feedback si prin propunerea unor metode de rezolvare a problemelor aparute exista o anumita "implicare". Nu în ultimul rând, a acorda un feedback și a discuta cu privire la organizarea/îmbunatățirea concursului nu însemnă tocmai sa comentezi. In fond, nu vad ce te deranjează pe tine în toată aceasta discuție.

Sebi, tu nu ai zis nimic concret (doar niste idei), de asta iti zice Petru ca ar trebui sa te implici.

E foarte usor sa zici ca trebuie facut X sau Y, e mult mai greu de facut asta in practica. E foarte greu sa spui concret cum anume s-ar putea rezolva o anumita problema. Ti-ai fi dat seama natural de asta daca incercai sa participi la organizarea unui concurs.

De exemplu ziceai ca ar trebui orice comisie sa stie absolut orice problema data la vreun concurs public de pana acum. Ar insemna  sa stie comisia in ordinul zecilor de mii de probleme (atatea area SPOJ de exemplu) iar asta e probabil dimensiunea vocabularului tau de cuvinte ca om normal. Nu ti se pare cam greu?

Nu este necesar sa ții minte toate problemele din arhiva SPOJ. Da, sunt de accord ca este imposibil sa faci asta. Dar am auzit de la mai multe persoane, imediat după ce s-a terminat concursul sau chiar in timpul concursului, cum se lăudau ca au gasit nu stiu ce problema pe google... Ca autor (nu am propus probleme pana acum, este doar o părere, nu stiu cat de fezabila) poți sa dai un search pe google si sa încerci sa vezi cât este de ușor sa găsești rezolvarea la problema propusa de tine. Daca primul link este o rezolvare a problemei, poate ca  nu este recomandat sa o propui la un concurs (repet, este doar o propunere, încerc sa îmi spun părerea, dacă este luata sau nu in considerare nu ma privește). Am încercat sa pomenesc si niste solutii la problema legata de copiat, destul de concrete, vezi MOSS.