Am trimis o sursa la D.Entropy acum vreo jumatate de ora si inca nu a aparut pe clasament.

Tot iau 20p la problema asta. Mi-am dat multe teste, si, comparand rezultatul cu ce mi-a dat la brut, toate testele mi-au dat bine. Doar primele 2 teste sunt OK, in rest WA. Poate cineva sa imi spuna ce greseala as putea sa am la problema?
Link catre sursa: http://www.infoarena.ro/job_detail/2015504?action=view-source

Pentru cei care au luat WA in afara de testele 4, 5, 8, 9, probabil ca gresiti cand faceti leftMax si incercati sa calculati minimul dintre Lminuri din secventa Lmax+1-i.
Good luck

WTF imi da 0 puncte cu incorect pe primele 3 teste si TLE pe ultimele 7, insa am verificat Testul 1 (si 2) si raspunsul este exact la fel. ?

Sursa: http://www.infoarena.ro/job_detail/2012947

 It is a very interesting method. Thanks for sharing it!

Ideea este sa imparti numerele in mai multe cicluri de permutari, periodicitatea fiecarui numar fiind chiar dimensiunea fiecarui ciclu.

Tot iau 60p cu 4 WA. Am facut cu LCA, in rest aceeasi idee ca cea a lui filipb. Aveti vreo sugestie?
LE:
Am luat 100p. Am pus unsigned int peste tot si a mers .

Foarte ciudat. Mi-am facut cateva teste si toate merg, comparand rezultatele cu sursa comisiei. Ce ar putea sa-mi scape?!
Va rog, ajutati-ma

Cea mai usoara solutie fara map si set: solutie cu std::vector. Am scos cu tot cu parsare 300ms pe cel mai rau test

Poate cineva sa adauge problema pe arhiva? 

Problema asta ma dispera. Am facut cu programare dinamica si tot imi da 70 de puncte, cu testele 6, 8, 9 WA. Uitati codul:

Cod:

#include <bits/stdc++.h>

#define Max 1004

FILE *fin, *fout;
int N, M;
int a[Max][Max];
int maxi[Max][Max], sol[Max][Max];

inline int smax(int a, int b)  {
    if(a > b)
        return a;

    return b;
}


int main()  {
    fin = fopen("joc.in", "r");
    fout = fopen("joc.out", "w");

    int s;

    fscanf(fin, "%d%d", &N, &M);

    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)
            fscanf(fin, "%d", &a[j]);
    int ri, rj;

    s = a[1][1];
    ri = 1, rj = 1, maxi[1][1] = a[1][1];
    sol[1][1] = a[1][1];
    maxi[1][2] = a[1][1];
    maxi[2][1] = a[1][1];


    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M;j++)  {
            if(i == 1 && j == 1)
                continue;
            sol[j] = a[j] - maxi[j];
            maxi[j] = smax(maxi[j], sol[j]);
            maxi[j + 1] = maxi[j];
            maxi[i + 1][j] = maxi[j];
            maxi[i + 1][j + 1] = maxi[j];
            if(sol[j] > s)
                s = sol[j], ri = i, rj = j;
        }

    fprintf(fout, "%d %d %d", s, ri, rj);

    fclose(fin);
    fclose(fout);

    return 0;
}

Later edit:

Am luat 100p. Am refacut dinamica si a mers

Tot iau 84p, desi am verificat toate testele comisiei. Aveti vreo idee despre ce poate cauza asta?

Uitati sursa:

#include <fstream>
#include <algorithm>

std::ifstream f("betasah.in");
std::ofstream g("betasah.out");

#define MAX 1000
#define Dmax 100

int N, D, K;
int M, P;

char mat[MAX + 2][MAX + 2];
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {1, -1, -1, 1, 0, 0, 1, -1};

int X[Dmax];
int Y[Dmax];
int ran[MAX + 2];

int main()  {

    f >> N >> D >> K;
    for(int i = 0;i <= N + 1;i++)
        mat

• = mat[N + 1] = 1;

    for(int i = 0;i <= N + 1;i++)
        mat[i + 1] = 1, ran = i;

    for(int i = 0;i < D;i++)  {
        f >> X >> Y;
        int x = X, y = Y;
        mat

• [y] = 2;

    }

    for(int i = 0;i < K;i++)  {
        int x, y;
        f >> x >> y;
        mat

• [y] = 2;

        ran

• --;

    }

    for(int i = 1;i <= N;i++)  {
        M = std::max(M, ran);
    }

    g << M << std::endl;

    for(int i = 0;i < D;i++)  {
        int x = X, y = Y;
        for(int j = 0;j < 8;j++)  {
            x = X, y = Y;
            int xx = dx[j], yy = dy[j];
            while(mat[x + xx][y + yy] != 2 && x + xx >= y + yy && x + xx >= 1 && y + yy >= 1 && x + xx >= 1 && x + xx <= N)  {
                if(!mat[x + xx][y + yy])P++;
                x += xx, y += yy;
                mat

• [y] = 1;// printf("%d %d\n", x, y);

          //      printf("%d %d %d\n", mat

• [y] - 0, x, y);

                }
        }
    }

    g << P << std::endl;

    f.close();
    g.close();

    return 0;
}

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;
}

In exemplu, de ce Paftenie nu castiga si jocurile 2 si 4?

Are idee cineva ce au testele 2 si 10, pt ca sunt singurele pe care iau Incorect.

Edit: Am reusit sa iau 100p. Nvm oricum nu ma asteptam sa raspunda cineva (Forumul pare mort).

Ma ajuta si pe mine cineva, pt ca nu imi iese generarea matricii a.i. sa nu existe elem 0
uitati codul:
#include <bits/stdc++.h>
#define min(a, b)(a < b?a:b)
#define maxi(a, b)(a>b?a:b)
FILE *fin, *fout;
int mat[22][22];int b[22][1000001];int DP[1000000];
long long v[20];
int r[1000001];


int main()  {
fin = fopen("triunghi.in", "r");
fout = fopen("triunghi.out", "w");
int n, s;
fscanf(fin, "%d%d", &n, &s);
int i, j, k;

///Generarea vectorului v-cu cat creste elementul de pe pozitia i daca adunam 1 la elementul de pe pozitia i
///se observa ca vectorul v este palindrom
///Ma va ajuta sa scap de TLE
long long sum;
v[0] = n;
v[n - 1] = n;
for(i = 1;i <= n / 2;i++)  {
    sum = 1;
    mat[n] = 1;
    for(j = n - 1;j >= 1;j--)
        for(k = 0;k < j;k++)
            mat[j][k] = mat[j + 1][k] + mat[j + 1][k+1], sum += mat[j][k];
    v = sum;
    v[n - i - 1] = sum;
    memset(mat, 0, 500);
}
//for(i = 0;i <= n - 1;i++)
//    printf("%d ", v);

///acum trebuie sa rezolvam problema rucsacului a.i. sa vedem
///daca exista a[0],...,a[n-1] a.i. a[0] * v[0] +...a[n-1] * v[n-1] = s
       for(i=1;i<=n;i++){
      for(j=i;j<=s;j++){
         if(DP[j-v[i-1]]+v[i-1]>=DP[j])
            b[j]=1;
         if(j>=v[i-1])
            DP[j]=maxi(DP[j],DP[j-v[i-1]]+v[i-1]);
      }
      }
   if(DP!=s)
      fprintf(fout, "imposibil");
    else  {
        int x, y;
        x=n;y=s;
   while(x>=1 && y >= 1){
         //printf("%d %d %d\n", b

• [y], x, y);

      if(b

• [y] == 1){

         y-=v[x - 1];
         mat[n]

• ++;

      }
      else
       x--;
       //if(x == 1)
   }
   //printf("%d %d", x, y);
   for(i=n-1;i>=1;i--)
      for(j=1;j<=i;j++)
         mat[j]=mat[i+1][j]+mat[i+1][j+1];
   for(i=1;i<=n;i++){
      for(j=1;j<=i;j++){
         fprintf(fout, "%d ", mat[j]);
      }
      fprintf(fout, "\n");
   }
    }
fclose(fin)
fclose(fout);
return 0;
}


De asemenea, cum pot sa optimizez(am 4 TLE si 5 WA  )