Mugur

[•Marius]

Aici se pot pune întrebări legate de problema Mugur a concursului CCEX 2009.

Timpul alocat întrebărilor este de 1 oră. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea îşi găseşte răspuns în enunţul problemei, răspunsul va fi FĂRĂ COMENTARII.

[•Marius]

Timpul alocat întrebărilor a expirat.

[•Mishu91]

As avea o intrebare, am generat numerele lu catalan, apoi din N am scazut K (parantezele care delimiteaza un mugure), iar apoi am facut o dinamica in care am cautat numarul de posibilitati de a pune N-K perechi de paranteze (asta cu ajutorul numerelor lu catalan), dar nu iau mai mult de 35. E busita ideea sau e de la implementare?

[•Marius]

Nu ştiu. Două inturi modulo 123457 înmulţite vor avea nevoie de long long. Ai avut grijă de asta?

[•Mishu91]

Dap, mi-am definit tot long long, si asta ma cam depaseste, ca ideea mi se pare buna

Am descoperit hiba, nu prea merge generarea numerelor lui catalan modulo 123457. Imi puteti da o idee cum s-ar putea face asta?

[•pauldb]

Folosesti invers modular.

[•devilkind]

Ca sa calculezi numarul de parantezari corecte cu N perechi de paranteze poti sa faci urmatoarea dinamica:

T[ i ] = suma( T[j - 1], T[i - j])  j:1->i.

De asemenea daca imi aduc eu bine aminte numerele lui Catalan parca erau o serie de combinari. Combinarile le poti calcula si fara invers modular.

C[ i ][j] = C[i - 1][j] + C[i - 1][j - 1];

Unde C[ i ][j] e combinari de i luate cate j.

[•Mishu91]

Ca sa calculezi numarul de parantezari corecte cu N perechi de paranteze poti sa faci urmatoarea dinamica:
T[ i ] = suma( T[j - 1] * T[i - j])  j:1->i.

Asta chiar e o modalitate mai simpla de calculare a numerelor lui Catalan in cazul in care apare modulo. Pacat ca am pierdut 90 de puncte in concurs pe o chestie de asta, dar macar am invatat ceva din ea