Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: ONI 2014  (Citit de 13698 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« : Aprilie 04, 2014, 19:19:16 »

In perioada 4-9 aprilie 2014 se desfasoara Olimpiada Nationala de Informatica 2014 pentru liceu, iar in perioada 10-14 aprilie 2014 are loc Olimpiada Nationala de Informatica 2014 pentru gimnaziu.

Site-urile competitiilor le gasiti aici si aici.

Mult succes tuturor participantilor!
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #1 : Aprilie 04, 2014, 19:20:43 »

Succes tuturor! Nu uitati sa cititi http://www.infoarena.ro/forum/index.php?topic=9769.0
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #2 : Aprilie 04, 2014, 19:35:49 »

Baftă! Smile
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : Aprilie 05, 2014, 11:49:51 »

Sa aveti parte de subiecte interesante si sa va distrati!
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Aprilie 06, 2014, 22:51:01 »

Clasament clasa a IX-a

Clasament clasa a XI-a

Clasament clasa a XII-a
« Ultima modificare: Aprilie 06, 2014, 23:17:28 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #5 : Aprilie 07, 2014, 10:52:14 »

Au fost postate rezultatele finale la ONI.
Clasamentul la clasele XI-XII s-a schimbat datorita unei reevaluari la problema Avarcolaci.
Link-ul il gasiti aici.
Memorat
GheorgheMihai
Strain
*

Karma: 24
Deconectat Deconectat

Mesaje: 38



Vezi Profilul
« Răspunde #6 : Aprilie 09, 2014, 00:52:32 »

La clasa a IX-a solutia oficiala la problema "progresie":http://oni2014.cnlodobescu.ro/wp-content/uploads/2014/04/progresie.pdf este gresita. Desi sunt vreo 3 solutii oficiale de 100 de puncte, niciuna nu este corecta. In enunt zice ca elementul maxim sa fie <= [2 * N * sqrt(N)] dar comisia nu respecta asta. Pentru n = 4097 toate cele 3 solutii oficiale afiseaza cel putin un numar > 530.000, dar [2 * 4097 * sqrt (4097)] = 524.480.
Din cate stiu, au fost 2-3 concurenti care au gasit o alta solutie care se incadreaza in limitele problemei, dau au fost inca vreo 4 care au avut solutia proasta a comisiei. Toti 6-7 au luat 100 de puncte. Astazi la intalnirea cu lotul cand am ridicat problema asta au zis ca solutia lor e buna si ca nu am inteles eu, dar acum m-am uitat pe sursele oficiale si sunt proaste. Ce trebuie facut intr-un astfel de caz?

Aici sunt sursele oficiale. Sunt mai multe teste pe care solutiile dau gresit, dar nu am stat sa le caut pe toate. Inca cateva exemple sunt 4098 si 4099.
https://ideone.com/Sh2nmm - Chesca Ciprian (am comentat ifstream si ofstream si am inlocuit f>> cu cin>> si g<< cu cout<<)
https://ideone.com/tt07k6 - Pit Rada Vasile Ionel (am adaugat iostream, am comentat fin si fout si am inlocuit fin>> cu cin>> si fout<< cu cout<<)
https://ideone.com/yyCXsd - Eugen Nodea (singurele modificari au fost sa comentez freopen-ul)

Singura sursa oficiala care respecta restrictia ca numerele sa fie mai mici decat 2 * N * sqrt (N), pacat ca nu respecta si restrictia ca numerele sa nu fie in progresie aritmetica (un exemplu 88574 177148 265722)
https://ideone.com/qDHMIc - Popescu Silviu (am scos freopen-ul)
« Ultima modificare: Aprilie 09, 2014, 02:09:39 de către Gheorghe Mihai » Memorat
dariusdarius
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #7 : Aprilie 09, 2014, 07:58:02 »

Am calculat eu in timpul concursului, in total erau aproximativ 800 de valori ale lui N pentru care solutia nu mergea din cele 20.000 posibile. Din fericire testele nu au inclus aceste valori deci nu se poate vorbi de o evaluare gresita, doar de una slaba care nu diferentia concurentii.
Memorat
omer
Strain


Karma: 9
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #8 : Aprilie 09, 2014, 22:33:56 »

M-am uitat si eu peste problema, si intr-adevar solutiile oficiale sunt cu mai multe bube. In primul rand, absolut toate fac exact aceeasi constructie, singura diferenta fiind limbajul folosit (nu de programare). Dar mai intai despre problema.

Solutia greedy (cea oficiala), are in medie a_n ~ n^{log3/log2}, iar log3/log2 este aproximativ 1,585, deci asimptotic mai mare decat n*sqrt(n) cerut de problema. Totusi, se pune problema care e cel mai mic a_n astfel incat sirul ala sa aiba proprietatea ca nu exista 3 termeni in progresie aritmetica. Se cunoaste un upper bound (mai bun decat n*sqrt(n) ), demonstrat de Behrend; vezi http://www.epsilonsmall.com/resources/behrends-construction/behrend.pdf ; in fine, el defapt construieste o multime cu cat mai multe elemente, toate incluse in [1,N]; problemele sunt echivalente. Exista si un lower bound demonstrat de Roth; a_n trebuie sa fie  O(n/ln(n)), dar demonstratia este mai complicata.

Bineinteles constructia lui Behrend nu numai ca nu intra in timp pt N<=30000, dar nici macar nu e prea optima pt N atat de mic. Se pune acum problema daca exista alta constructie; o prima idee e sa facem din nou greedy, dar cu alt set de inceput (in solutia oficiala se incepe cu 1 si se obtin numerele care au in baza 3 doar cifre de 1 si 0). Aceasta problema a fost data la un test de selectie din China, si tot ce demonstreaza este ca exista multe n-uri astfel incat a_n < c*n^2, pentru o constanta c. Vezi http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3434262&sid=a676b71e9396b4d54d8588491732c637#p3434262 . Culmea problema a fost data cam acum o luna. Ce putem observa din aceasta problema este ca in afara de cateva cazuri magice (precum cel din solutia oficiala, dar si daca incepeam cu numere de forma 3^m sau 2*3^m), nu prea putem spune mai mult decat a_n<=c*n^2 (problema a fost data la un test chinezesc, deci ar trebui sa fie relativ optima! ). Intr-adevar, citind aici ( http://www-math.mit.edu/~rstan/papers/od.pdf ), se vede ca solutia greedy se presupune a fi foarte haotica in majoritatea cazurilor.

Iar atunci ramane intrebarea: cum putem rezolva problema? Am vorbit si cu un distins profesor de matematica, si nici el nu cunoaste alta constructie in afara de cele 2 amintite mai sus. Din cele 2, doar cea greedy este fezabila, dar aceasta nu rezolva corect problema.

Si acum sa incerc sa raspund la intrebarea lui Mihai : nu mai prea e nimic de facut, olimpiada s-a terminat deja. Ce poate fi facut in viitor este ca demonstratiile sa fie mai riguros matematica, si sa nu lasam in vant afirmatii (a se observa ca in nicio solutie oficiala nu se face precizare DE CE are loc a_n < 2n*sqrt(n) ). Am observat ca la informatica, spre deosebire de matematica, solutiile se bazeaza foarte mult pe intuitie. Acest lucru este foarte bun in concurs, unde participantii au de rezolvat 3 probleme (relativ) grele, sia poi mai trebuie sa le si implementeze. Nu ar fi timp prea mult pentru demonstratii extrem de riguroase la toate observatiile. Dar aceste demonstrtii nu pto lipsi din solutiile oficiale, caci altfel patim ca in aceasta problema ( a se observa ca si la problema volum de la 11-12 solutiile sunt mai mult intuitive decat argumantate; probabil e la fel la mai multe probleme).

Un numar de observatii in plus: din cate am observat, nici solutia lui Popescu Silcviu nu respecta problema (adica a_n < 2*n*sqrt(n) ). Probabil n-ul in acest caz este mai mare decat 30000, dar sigur exista , caci in solutia lui termenul a_{2^n} este (3^n+1)/2, care iarasi este aproximativ a_n^{log3/log2}. Mai mult, complexitatea primei solutii (daca am inteles bine), nu este O(n *log(n)) (care nu ar explica cele 30 de puncte), ci  O(n^{1(log2/log3)})
, unde log2/log3 este aproximativ 0,631, complexitate mult mai mare decat ce era precizat. Nici nu inteleg de unde au scos complexitatea aia.
« Ultima modificare: Aprilie 10, 2014, 01:20:09 de către Omer Cerrahoglu » Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #9 : Aprilie 10, 2014, 08:58:53 »

Mda, pai din pacate la info se folosesc "Demonstratii Intuitive" (desi e un titlu cam paradoxal). In concurs nu prea ai timp de demonstratii, asa ca e responsabilitatea comisiei sa se asigure ca problema propusa de ei admite solutie. Atata timp cat exista solutie, concurentii sunt liberi sa bage ce vor ei (e pe riscul lor daca demonstreaza sau nu). Cum a fost de exemplu la problema Ciocolata de la baraj: Toata lumea a iesit si a zis ca a facut-o, dar nimeni (cel putin din persoanele cu care am vorbit eu) nu stia sigur daca e bine sau nu. In final, au luat puncte cei care au ghicit cum se face. Pana si Omer, care fiind super tare la mate, nu a demonstrat-o si nu era sigur pe ea (el fiind singurul la care m-as fi asteptat sa o faca sigur). Concluzia a fost ca cei care au demonstrat (adica nimeni) au facut-o 100%, iar restul au sperat ca ce au facut ei acolo era bine. Oricum, sper ca la problema ciocolata comisia a demonstrat cum se face, si nu au incercat sa ghiceasca cum a fost la problema progresii, unde aparent nu au avut prea mult noroc.

Sper ca sunt cat se poate de obiectiv in ceea ce zic.
Memorat
dariusdarius
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #10 : Aprilie 10, 2014, 09:34:28 »

"Observația esențială este aceea ca rezultatul final al jocului depinde de paritatea numerelor de batoane de fiecare tip. Putem demonstra că această observație este corectă aplicând inducție după numărul de mutări care mai ramân de efectuat până la final." (Citat din articolul de solutii oficiale ale barajului)

Nu sunt foarte sigur cum s-ar face inductia, dar cred(sper) ca putem presupune ca macar la aceasta problema comisia a demonstrat complet solutia  Confused Confused
Memorat
proflaurian
Client obisnuit
**

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #11 : Aprilie 10, 2014, 14:03:41 »

La problema ciocolata va fi prezentata demonstratia completa la prima tabara de Lot.

Voi scrie aici in linii mari despre ce e vorba.

Inductia dupa numarul de mutari se bazeaza pe descompunerea jocului in doua jocuri - unul utilizeaza cate un baton din cele care au un numar impar de aparitii si un joc formar din restul batoanelor ( este posibil sa nu avem primul joc - daca toate tipurile apar in numar par , este posibil sa nu avem al doilea joc - daca avem cel mult un baton din fiecare tip). Am sa explic aici doar cazul in care un jucator are strategie de castig. Daca sunt la mutare aplic mutarea care ma duce la configuratia castigatoare pe primul joc. Atunci trec intr-o configuratie castigatoare pentru mine , cu adversarul la mutare si am cu o mutare mai putin ( deci prin inductie voi castiga la diferenta anticipata). Daca nu sunt la mutare astept mutarea adversarului. Daca adversarul muta cu un baton care apare cel putin de doua ori imit mutarea adversarului si ajung la aceeasi configuratie de paritati cu cea initiala si s-au efectuat cu 2 mutari mai putin deci pot sa aplic inductia. Daca se muta intr-un baton care apare o singura data atunci consider ca s-a jucat in jocul 1 si aplic mutarea castigatoare cu care continua acel joc( implicit se ajunge pe o configuratie castigatoare dar la doua mutari mai putin - deci inductie) . Exista aici si un caz particular si anume cand doar numarul de batoane de 2 e impar ( sau altfel spus jocul 1 se termina dintr-o singura mutare) dar aici ajung ca adversarul a mancat deja 2 si se intra pe configuratia cu toate resturile 0 care duce la remiza.
Partea mai delicata la aceasta inductie este initializarea acesteia. Mai precis - ar trebui sa ma asigur ca observatia este valabila pana la un numar dat de mutari - dar acest numar initial sa ma asigure ca am tratat toate configuratiile posibile si nu risc sa ajung mai tarziu la o configuratie care nu a mai fost luata in calcul. Acest numar minim de mutari care asigura aparitia tuturor configuratiilor intr-un numar mai mic de mutari este 1+2+...+15 si se obtine pentru cunfiguratia in care avem exact un baton de fiecare tip. Daca cineva isi doreste sa demonstreze riguros acest pas al inductiei atunci ruleaza un brut care determina deznodamantul jocului pana la acel numar de mutari.
Nu a fost scrisa in descrirea solutiei demonstratia completa ci doar ideea de rezolvare. Mai sunt si alte observatii care ar duce la intelegerea completa a demonstratie dar sa le prezint pe toate ar insema sa mai scriu inca pe atat in acest post.
« Ultima modificare: Aprilie 10, 2014, 14:25:28 de către Panaete Adrian » Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #12 : Aprilie 10, 2014, 14:57:24 »

Adevărul e că problema asta a fost distrusă. Nu înțeleg cum nici măcar nu s-au verificat soluțiile oficiale pe toate valorile lui N, având în vedere că sunt doar 30 000.

Totuși, aș atrage atenția că generalizăm cam ușor. Sunt de acord că există un trend de a relaxa rigurozitatea matematică și sunt complet împotriva lui, însă în 99% din cazuri soluțiile sunt ok. Incidentul cu problema progresii nu trebuie să vă stârnească dubii despre toate problemele care au fost în concurs. Descrierile soluțiilor pot fi făcute în termeni informali / intuitivi, cam așa au fost făcute întotdeauna. Esențial e să existe demonstrația în cadrul comisiei, iar cel mai des acest lucru se întâmplă. Cel puțin în comisiile pe care am avut ocazia să le observ din interior (ONI 11 12, Baraj și Loturi anul trecut).
« Ultima modificare: Aprilie 10, 2014, 15:17:17 de către Mihai Calancea » Memorat
omer
Strain


Karma: 9
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #13 : Aprilie 10, 2014, 16:13:27 »

Da, ceea ce doream sa spun e ca trebuie sa EXISTE o solutie riguroasa, nu neaparat sa apara in solutiile publicate. In acest sens, precum s-a spus si mai sus, solutia la ciocolata este foarte buna: e precizat faptul ca se poate demonstra inductiv afirmatia facuta, dar demonstratia nu e facuta explicit. Daca, spre exemplu, comisia ar fi trebuit in solutiile publicate sa descrie ( NU neaparat sa demonstreze ) de ce algoritmul de la progresie este corect, cu siguranta s-ar fi descoperit greseala.
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #14 : Aprilie 10, 2014, 18:50:03 »

Maine are loc Olimpiada Nationala de Informatica pentru gimnaziu, iar poimaine are loc proba de baraj pentru selectia lotului largit de juniori.
Mult succes tuturor participantilor!
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines