1128 Poligoane

[•andrei.12]

Aici puteti discuta despre problema Poligoane.

[•soriyn]

Imi da si mie cineva o idee de rezolvare ? 

[•SpiderMan]

Faci recurenta dp[ i ][j] - numarul de moduri sa imparti i bete in poligoane, unde cel mai mare poligon are j bete. Rezultatul o sa fie suma ( dp[N][ i ] ), i = 3, N. Daca ai nevoie de alt ajutor sa-mi spui.

[•S7012MY]

Cred ca ar trebui pus poligoane convexe regulate pt ca pt n=6 poti forma si un dreptunghi

[•Magnus]

Vi se pun T teste la dispoziţie. Pentru fiecare trebuie să afişaţi numărul de moduri în care se pot grupa beţele pentru a forma poligoane convexe regulate modulo un număr dat.

[•S7012MY]

ma refeream la prima parte a enuntului

[•Magnus]

cu 6 betisoare iti desenez si 666013 poligoane neregulate distincte daca vreau (trebuie doar sa maresc/micsorez 2 unghiuri din hexagon)
ceea ce vreau sa zic este ca problema nu are sens daca poligoanele nu se considera regulate
oricum in enunt se precizeaza sa fii atent la exemplu pentru a intelege mai bine cerinta
nu cred ca in concurs ai fi busit solutia la problema asta pentru ca n-ai citit atent

[•ctlin04]

Presupunem ca am gasit relatia de recurenta pentru matrice, dar acum cum trebue de procedat cu resturile diferite de fiecare data?

[•SpiderMan]

Cum adica cum ? Faci pt. fiecare test in parte o dinamica in O(N²), si asta e.

[•ctlin04]

Pai asta am si facut problema e ca asa imi intra in timp doar 6 teste, nustiu probabil e de la pascal 

[•SpiderMan]

Cred ca ar trebui marita limita de timp ...

[•ctlin04]

Cred ca este si alta solutie mai buna, in timp ce sunt surse cu timpi sub 200 ms si memorie in jur de 250Kb, poate sugereaza cineva dintre cei care au implimentat solutia buna, care e ideea

[•maritim]

Daca vorbesti de sursa mea sa stii ca am facut exact cum a zis si spiderman putin mai sus. Eu am folosit memorie O(N) facand dinamica pe vector. De aici probabil se mai poate scuti timpul deoarece alocarea memoriei cere mult timp .

[•VisuianMihai]

Am o intrebare.
Se pune daca poligoanele sunt lipite? adica din 5 bete se pot face 2 triunghiuri sau e doar un patrulater cu diagonala ?

[•danalex97]

Salut ! Nu ma prind care ar fi recurenta la aceasta problema. Sa posteze sau sa imi lase si mie un PM cine a rezolvat-o. Mi se pare ca e o dinamica O(N^2*T) , insa nu reusesc sa imi dau seama de recurenta.    

LE: Mi-am dat seama. Hint: Construiti tabelul dinamic de la dreapta la stanga 
@ Mihai: Pentru 5 rezultatul e 1 (pentagonul).