Probleme cu puncte laticiale

[•Marius]

Comentarii la articolul Probleme cu puncte laticiale scris de Cosmin Negruşeri.

Îi mulţumim Alexandrei Diculescu pentru că s-a implicat în transcrierea lui.

[•Florian]

Legat de problema #7 ( paralelograme ): Spre sfarsitul explicatiei de la rezolvare, se da urmatoarea idee de optimizare:

Mai putem optimiza factorii constanţi ai soluţiei observând că într-un triunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un triunghi W * H. Acest artificiu aproape dublează viteza algoritmului. Menţionăm că aceleaşi optimizări pot fi făcute şi la problema cu triunghiuri.

La ce triunghiuri se refera? 

[•Cosmin]

Am corectat la dreptunghi.

Cand vezi ceva gresit poti sa corectezi chiar tu. Siteul este wiki si va incurajam sa fiti activi nu pasivi.

[•APOCALYPTO]

La problema 5  avem formula 4 * ((H - 1)(W - 1) + H - 1 + W - 1).

Factorul 4 reprezinta cele 4 pozitii ale primului punct.
Produsul (H - 1)(W - 1) toate perechile care se pot forma intre ultimele H-1 puncte de pe verticala si primele W-1 puncte de pe orizontala?
H-1 repezinta numarul de puncte de pe verticala pe care le putem imperechea cu al W-lea de pe orizontala?
Iar W-1 reprezinta numarul de puncte de pe orizontala pe care le putem imperechea cu primul de pe verticala?
 
Later edit:
Iar la problema 7 avem h * w - cmmdc(h - 1, w - 1) - 2 posibilităţi
Pentru diagonala avem cmmdc(h - 1, w - 1) +1 posibilitati si mai eliminam un 1 deoarece putem obtine un patrat de 2 ori?
(Scuzati-ma daca nu se intelege bine ce am scris).

Later later edit:
Si tot la problema 7 la seventa de cod este o mica greseala.
Este scris:

Cod:

  num += (N - h + 1) * (M - w + 1) * laux; 

si trebuia

Cod:

  num += (N - h + 2) * (M - w + 2) * laux; 

pentru ca N si M sunt numarul de randuri respectiv coloane deci numarul de puncte pe verticala este N+1 iar pe orizontala M+1.
Pot sa modific?

[•andrei202]

in legatura cu problema 6 nu am inteles de unde il iau pe H si W pt ca in enunt mi se da doar N si M

[•pauldb]

Astfel, în O(H) vom şti numărul de dreptunghiuri înscrise într-un dreptunghi de dimensiuni H * W. Acest dreptunghi poate fi pus în (N - H + 1) * (M - W + 1) locaţii pe o grilă de dimensiune N * M. Deci, soluţia are complexitate O(N*M^2), pentru fiecare dreptunghi de dimensiuni 1 ≤ H ≤ N şi 1 ≤ W ≤ M calculându-se numărul de dreptunghiuri înscrise.

Cum e precizat mai sus, ideea e sa alegi toate perechile (H,W) cu 1 <= H <= N si 1 <= W <= M, iar pentru fiecare pereche in parte sa calculezi in O(H) numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni H si W, folosind indicatiile din primele paragrafe. Acest numar va trebui inmultit cu numarul de amplasari posibile ale unui astfel de dreptunghi (adica (N - H + 1) * (M - W + 1)).

[•rares96cheseli]

La problema 7 cum pot folosi faptul ca  într-un dreptunghi de dimensiuni H * W poate fi înscris acelaşi număr de dreptunghiuri ca şi într-un dreptunghi W * H?
am incercat sa fac asa dar nu da rezultat bun :

Cod:

for (int h=2; h<=max(m, n)+1; h++)
    {
        for (int w=2; w<=h; w++)
        {
            aux=(h-2)*(w-2) + h*w - gcd[h-1][w-1]-2;
            num+=(n-h+2)*(m-w+2)*aux;
        }
    }