infoarena

Exprimati-va aici parerile despre concursul Grigore Moisil 2009.

La 11-12 a fost chiar fain, Pari a fost putin cam grea, drept dovada nu a luat nimeni mai mult de 10 puncte

S-au actualizat si ratingurile.

Mi-au placut problemele, cam dificile la nivel de olimpiada interjudeteana !  :ok:
Singurul neajuns a fost ca la Peisaj nu s-a specificat in enunt ca se acorda punctaje partiale.

Dacă nu citeşti tot...

Se refera la concursul onsite, pe foi nu era specificat !

Problema pari foarte tare.  =D> Felicitari Marius.  :yahoo:

Salut,

Felicitari lui Marius si Adrian pentru efortul depus! :winner1:

M-am uitat peste subiectele de la 11-12 in timpul concursului. Ideile mele de rezolvare sunt cam asa:

• Peisaj:
  - subpunctul a) - numerele lui Catalan
  - subpunctul b) - dinamica A[ i ][ j ][ k ] - numarul de munti ce se pot forma cu i betisoare astfel incat sa ma aflu la inaltimea j. Dimensiunea a treia poate lua valori 0 sau 1 - daca s-a ajuns sau nu la inaltimea K pe parcurs
  -subpunctul c) - dinamica A[ i ][ j ][ k ][ l ] - numarul de munti ce se pot forma cu i betisoare, sa te afli la inaltimea j, sa fi avut deja k varfuri si l poate fi 0 sau 1 - daca la pasul curent ai ajuns de la o inaltime mai mare sau mai mica.
  
• Palindrom: Foloseai jmenul de la Pscpld sau faceai hashuri pentru a afla cel mai lung palindrom care se termina pe pozitia N.
  
• Pari: Modelai problema sub forma de graf. Fiecarui numar ii corespundea un nod din graf. Aveai muchie intre doua noduri daca puteai sa faci o operatie cu numerele asociate nodurilor. O observatie buna este faptul ca nu are rost sa adunam in vreo operatiei o valoarea para (e de ajuns sa adunam 1 de fiecare data). Putem sa consideram ca nodurile noastre au doua culori: alb - daca nodul are aceeasi paritate ca in input si negru in caz contrar. Unei operatii ii corespunde alegerea unei muchii si schimbarea culorii fiecarui nod in care este ea incidenta. Pentru a reconstitui o serie corecta de mutari luam fiecare nod negru, faceam un DF din el pentru a gasi un alt nod negru si efectuam operatiile corespunzatoarea muchiilor de pe lantul ce uneste nodurile negre.
  

Voi scrie un articol cu soluţii în curând.  8)

Soluţiile lui wefgef sunt bune, doar că la Peisaj se pot rezolva toate cerinţele cu dinamica de la punctul c) iar la Palindrom eu am folosit KMP.

La Peisaj acelasi ce a spus wefgef numai la punctul
b)numarul total de munte ce se pot forma - numarul total de munte care au inaltime maxima mai mica decat k. :-'

La Peisaj acesta este si solutia oficiala, in afara de faptul ca subpunctul a) este subpunctul b) cu k=1.

Imi pare rau ca la concurs nu s-a specificat pe foaie ca se dau punctaje partiale, a fost o versiune veche a enuntului, pentru ca un email n-a ajuns la destinatie. Din pacate n-am observat acest lucru la fata locului.

La problema "peisaj", subpunctul c): Numerele Narayana reprezinta nr de profile montane, ce se formeaza din n caractere "/" si n caractere "\", si contin exact k varfuri. Exista si o formula bazata pe combinari. Asadar, raspunsul pt punctul c) este exact Narayana(n/2 , k ).

Narayana (n,k) = C (n , k-1) * C(n-1, k-1) / k . Din pacate, in concurs, nu am gasit dinamica de la subpunctul b), asa ca a trebuit sa ma multumesc cu 60% din punctaj.

Problemele mi s-au parut destul de accesibile, insa parca a fost prea putin timp. De ex, nu am apucat sa trimit sursa la problema "pari" ( terminasem implementarea la 12.01 )  :) Oricum, a fost frumos! Felicitari organizatorilor!  :)

Mie personal nu mi-au placut niciodata problemele de formula (gen sa stii numerele lui X). Imi place ca se puteau face cu dinamica toate subpunctele la peisaj :thumbup:

@Marius: La problema palindrom m-am gandit putin si mi-a iesit si cu KMP. Cea mai frumoasa rezolvare mi se pare asta a ta :D. Pacat ca exista solutiile alternative. La hashuri scriai cateva linii sau la cealalta solutie puteai sa dai copy paste de la pscpld.

Wefgef: Poti sa explici solutia bazata pe hashuri la palindrom...:) Si eu am facut cu KMP si n-am idee cum sa fac cu hash.

La palindrom vrei sa aflii lungimea celui mai mare palindrom ce e sufix al sirului.
Pentru asta poti itera prin toate lungimile si la pasul i sa ai codul hash pentru subsecventele [n - 2* i, n - i] si [n - i + 1, n].

Edit: de fapt vrei codul hash pentru secventa reflectata [n - 2*i, n - i].

Poti sa explici putin cum obtin codul hash ? Banuiesc ca trebuie sa consider cuvantul ca fiind un nr intr-o anumita baza (26, de exemplu). Dar daca ar fi asa, pt un cuvant de 100.000 de caractere, ar iesi un numar enorm (desi probabil ca fac modulo). Nu prea inteleg, si un exemplu ar fi binevenit. Scap ceva, insa nu stiu unde...  :fool: Multumesc!

Vezi http://infoarena.ro/problema/strmatch

M-am lamurit! Multumesc, din nou!  :)

Un sir e palindrom daca hash-ul lui este egal cu hash-ul inversului sau. Pornesti de la sfarsit si iti construiesti solutia.

A apărut articolul cu soluţii (http://infoarena.ro/grigore-moisil-2009/solutii).

Se vor publica rezultatele concursului pe site (http://81.196.170.188/) ?

Felicitari organizatorilor  =D>
Marius Stroe si Patcas Csaba sunt dovada vie a faptului că şi Ardealul poate propune probleme de nivel înalt şi un aspirator de valori ca oraşul Bucureşti nu acţionează peste munţii Carpaţi.  :D

Ironia sortii face ca nici Marius, nici Csabi sa nu fie originari din Ardeal :P

Csabi e oradean !!!

Da, stiu. Iar Oradea nu a fost, nu este si nici nu va fi vreodata in Ardeal. Hai ca devenim offtopic :P. http://ro.wikipedia.org/wiki/Regiuni_istorice_ale_Rom%C3%A2niei