504 Euclid

[•DITzoneC]

Aici puteţi discuta despre problema Euclid.

[•bogdan2412]

Nu ar fi mai bine daca ar fi coborata limita de timp in arhiva? Deja sunt destule surse care intra in 4.5 secunde lejer si nu are rost sa ramai cu o problema care tine 2 minute sa se evalueze.

[•sima_cotizo]

Uite de exemplu daca golesti matricea dupa fiecare test cu memset iti ia 11 secunde... fara max 9 secunde... pe rezolvarea mea... bine, nu iau tle, ci WA, nu stiu de ce... Sunt cazuri speciale ? 

LE: sorry pt edit, erau 9s...  nu stiu ce vazusem

[•DITzoneC]

Am pus limita 4s si am reevaluat in arhiva.

[•sima_cotizo]

Rezolvarea mea are complexitate O( N*M * log N * log M ) si ... nu incape... limita de 4s e pusa ca sa abordam rezolvarea eleganta? .. ca as vrea sa stiu daca era buna si rez mea in concurs, sau macar ce am gresit ... 

[•filipb]

Pai rezolvarea mai eleganta mi se pare si mai comod de implementat. Scrie in articol ca ambele obtineau punctaj maxim din ce am vazut. Testele sunt corecte.

[•sima_cotizo]

Eu o aveam deja implementata... ma rog, tinand cont ca intra in concurs pe ultimele teste cu OK, cred ca ar fi luat 100 cu 11.5 s limita... o sa abordez si metoda eleganta atunci  

[•ciprianf]

Cod:

"3904ms	50952kb	Time limit exceeded." 

Ce naiba?

E:Pt prima varianta de rezolvare din solutii:

Cod:

 Pentru aceasta, mai intai sa luam di = [log h] si dj = [log w]. Numarul cautat este gcd(V[di][dj][i][j], V[di][dj][i][j + w - dj], V[di][dj][i + h - di][dj], V[di][dj][i + h - di][j + w - dj]) 

Nu este cumva corect asa:

Cod:

  gcd(V[di][dj][i][j], V[di][dj][i][j + w - 2^dj], V[di][dj][i + h - 2^di][dj], V[di][dj][i + h - 2^di][j + w - 2^dj])

Motivul pt care cred eu ca trebuie pus 2^dx(x=i sau j)  este deoarece noi ne dorim 4  dreptunghiuri de laturi 2^di si 2^dj care suprapunandu-se sa formeze dreptunghiul cu colturile (i,j),(i+h-1)(j+w-1).

Cod:

 Putem apoi vedea in O(1) care este gcd-ul elementelor din dreptunghiul cu colturile in (i, j), (i + w - 1, j + h - 1) 

Nu trebuia

Cod:

 cu colturile in (i,j) , (i+h-1,j+w-1) 

?

LE: chiar nu raspunde nimeni nimeni?

[•Florian]

Ai dreptate. Am modificat articolul cu solutii [ la ambele solutii erau greseli ]. Sper ca nu am gresit nimic. 

[•popoiu.george]

Cred ca trebuie marita limita de timp. Iau 60p cu O(N * M * logN * logM) si am retrimis o sursa care lua 100p si ia tot 60p.

Am updatat http://infoarena.ro/calibrare-limite-de-timp

[•blasterz]

Cred ca trebuie marita limita de timp. Iau 60p cu O(N * M * logN * logM) si am retrimis o sursa care lua 100p si ia tot 60p.

Am updatat http://infoarena.ro/calibrare-limite-de-timp

Din cate stiu, asta nu e solutia optima... deci ar fi ok sa iei 60.

[•popoiu.george]

In articolul cu solutii se spune ca solutia O(N * M * logN * logM) ar trebui sa primeasca 100p. Chiar si asa, sursa care lua 100p e in O(N * M * logN) deci solutia optima. Si ia tot 60p.

[•pauldb]

Fixed.

[•scipianus]

Nu cumva ar trebui marita putin limita de timp?
Cu solutia in O((logN+logM)*N*M) iau 60pct cu TLE,cel mai mare timp pe testele 1-6 fiind de 276ms (http://infoarena.ro/job_detail/847073) sau de 208ms daca fac Euclid cu scaderi repetate in loc de modulo (http://infoarena.ro/job_detail/847072)

[•SpiderMan]

Chiar trebuie marita, si eu cu sursa veche iau tot 60.

[•scipianus]

Deci se ocupa cineva de limita de timp?

[•Magnvs]

vad ca nu modifica nimeni limita de timp.

pentru 100 de puncte sunt necesare si suficiente :
solutia in o(t*n^2*logn);
gcd cu scaderi repetate (ideea lui scipianus);
parsare a intregului fisier de intrare;
grija sa nu spargi cache-ul.

[•marius135]

Am marit limita!

[•https]

De ce merge mai gcd rapid prin scaderi?

[•pop_bogdan]

Teste de calitate!

[•mihai.alpha]

Am urmarit solutia oficiala si tot iau zero puncte. Am incercat pe cateva teste si totul merge ok. Primesc 3 Incorect si 7 TLE.
#include <stdio.h>

#define r fscanf
#define pr fprintf
#define LOGMAX 20
#define NMmax 600
inline int Max(int a, int b)  {
    if(a > b)
        return a;
    return b;
}

int d[LOGMAX][LOGMAX][NMmax][NMmax], a[NMmax][NMmax];

FILE *f, *g;

int T, m, n, h, w;

inline int log(int x)  {
    int ret = 0;
    int r1 = 2;
    while(r1 <= x)  {
        ret++;
        r1 <<= 1;
    }
    return ret;
}

int gcd(int a, int b)  {
    if(b == 0)
        return a;

    return gcd(b, a % b);
}


int main()  {
    f = fopen("euclid.in", "r");
    g = fopen("euclid.out", "w");

    r(f, "%d", &T);
    for(int i = 0;i < T;i++)  {
        r(f, "%d%d%d%d", &m, &n, &h, &w);
        for(int l = 1;l <= m;l++)
            for(int c = 1;c <= n;c++)  {
                r(f, "%d", &a[l][c]);
            }

        int logm, logn;
        logm = log(m), logn = log(n);

        for(int l = 1;l <= m;l++)
            for(int c = 1;c <= n;c++)  {
                d[0][0][l][c] = a[l][c];
                d[0][1][l][c] = gcd(a[l][c], a[l][c + 1]);
                d[1][0][l][c] = gcd(a[l][c], a[l + 1][c]);
                d[1][1][l][c] = gcd(d[0][1][l][c], d[1][0][l][c]);
                d[1][1][l][c] = gcd(d[1][1][l][c], a[l + 1][c + 1]);
                for(int di = 1;l + (1 << di) - 1 <= m;di++)
                    for(int dj = 1;c + (1 << dj) - 1 <= n;dj++)  {
                        d[di][dj][l][c] = gcd(d[di - 1][dj][l][c], d[di][dj - 1][l][c]);
                        d[di][dj][l][c] = gcd(d[di - 1][dj - 1][l + 1 << (di - 1) - 1][c + 1 << (dj) - 1], d[di][dj][l][c]);
                        d[di][dj][l][c] = gcd(d[di - 1][dj][l + 1 << (di - 1) - 1][c], d[di][dj][l][c]);
                        d[di][dj][l][c] = gcd(d[di][dj - 1][l][c + 1 << (dj - 1) - 1], d[di][dj][l][c]);
                        d[di][dj][l][c] = gcd(d[di][dj][l][c], a[l][c]);
                        d[di][dj][l][c] = gcd(d[di][dj][l][c], a[l + 1 << di - 1][c + 1 << dj - 1]);
//                        printf("dreptunghiul ce incepe din l%d c%d si se termina in l%d c%d are gcd-ul %d\n", l, c, l + 1 << di - 1, c + 1 << dj - 1, d[di][dj][l][c]);
                    }
            }

        int max = 0;

        int logw, logh;
        logw = log(w), logh = log(h);
        int nrw = 1 << logw, nrh = 1 << logh;

        for(int l = 1;l <= m - h + 1;l++)
            for(int c = 1;c <= n - w + 1;c++)  {
                int cmmdc;
                cmmdc = gcd(d[logh][logw][l][c], d[logh][logw][l][c + w - nrw]);
                int cmmdc1 = gcd(d[logh][logw][l + h - nrh][c], d[logh][logw][l + h - nrh][c + w - nrw]);
                cmmdc = gcd(cmmdc, cmmdc1);
                max = Max(cmmdc, max);
            }

        pr(g, "Case #%d: %d\n", i + 1, max);
    }


    fclose(f);
    fclose(g);

    return 0;
}

[•andrei.arnautu]

E destul de greu pentru cineva sa iti ia sursa si sa verifice unde este greseala. Ia mult timp, mai ales datorita faptului ca fiecare are un stil de codare diferit.

Cel mai bine e sa iti generezi teste mici si sa faci debug pe sursa pas cu pas ( nu sa vezi numai daca rezultatul final e OK ). Vei afla unde e greseala mai repede si te va ajuta si in concurs mult mai mult. Bafta!