Feedback Nationala ACM & Runda 2

[•diac_paul]

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.

[•cojocarugabi]

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.  

[•UNIBUC_Echipa_Lacheta]

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 ..?

[•AlexandruValeanu]

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_BoSSilor]

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

[•retrograd]

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.

[•wefgef]

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

[•Djok]

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. : )

[•Cristy94]

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

[•Djok]

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

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

[•Cristy94]

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.

[•Djok]

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.

[•mugurelionut]

3.PQ foarte tare se aseamana cu http://codeforces.com/contest/522/problem/D si daca schimbat un

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 mi-a sugerat sa fac problema online, dar nu l-am ascultat

[•Djok]

3.PQ foarte tare se aseamana cu http://codeforces.com/contest/522/problem/D si daca schimbat un

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 mi-a sugerat sa fac problema online, dar nu l-am ascultat

Ai putea descrie cum se face online problema ?

[•AlexandruValeanu]

@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.

[•Djok]

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

[•cojocarugabi]

3.PQ foarte tare se aseamana cu http://codeforces.com/contest/522/problem/D si daca schimbat un

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 mi-a sugerat sa fac problema online, dar nu l-am ascultat

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.

[•diac_paul]

Scuze de intarziere. Am updatat articolul cu solutii 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
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).

[•SebiSebi]

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!

[•Djok]

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.

[•wefgef]

Sau ați putea apela la niște profesioniști.

[•Djok]

Sau ați putea apela la niște profesioniști.

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

[•wefgef]

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

[•SebiSebi]

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.

[•UPB_Darius_Rares_Silviu]

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