258 Alpin

[•mordred]

Un exemplu: ai de citit un vector de numere (de maxim 5 cifre, să zicem)

Cod:

...
char buffer[NMAX * 6 + 1], tmp;
gets(buffer);
for( i = 0, nr = 0; i < n; ++i )
    {
    sscanf(buffer, "%c", &tmp);
    if( tmp == ' ')
        ++nr;
    else
        a[nr] = a[nr] * 10 + tmp - '0';
    }

Unde a[NMAX] se presupune că e vectorul tău de int-uri, iniţializat cu 0. Dezavantajul e că aloci (foarte) multă memorie vectorului de char, o variantă ar fi un vector buffer de dimensiuni mai mici şi citirea pe bucăţi mai mici.

[•klamathix]

A luat cineva TLE doar pe testul 3 la problema asta facand dinamica cu memoizare ? Evident cicleaza dintr-un anume motiv , dar nu reusesc sa-mi dau seama. Thanks.

[•andrey932]

Ce are mai special testul 4?
ma incadrez destul de bine in restul testelor(maxim 752ms, pe ultimul test).
Folosec un algoritm asemanator BFS cu coada(in care introduc toate elementele care sunt inconjurate in toate cele 4 parti de maxime, dupa care aplic BFS).

LE: Am parsat citirea, s-au imbunatatit timpurile(332 ms), dar pe testul 4...acelasi lucru:|

LE2: Am inlocuit BFS cu un DFS (cu stack) si am luat 100

[•soriyn]

Ma scoate din minti problema asta

Iau KBS pe testele 3 si 4. Imi poate da cineva un test mai smecher ?

Apropo...pot exista si altitudini negative ? Am impresia ca macar la testul 3 e asa.

[•geniucos]

Imi poate spune si mie cineva unde gasesc articolul cu solutii?

[•geniucos]

Nu mai e nevoi am luat 100 in O(n^2) fara memoizare(sau cu ,nu stiu exact ce e aia)

[•lucian666]

 :)Buna ziua!
AM 60 pct cu 3 WA si 1 TLE.Nu stiu  de ce  am TLE  deoarece am parsat citirea
Am procedat in felul urmator:
Am folosit un queue din STL in care am bagat initial toate altitudinile care erau mai mici decat toti vecinii
Am folosit un BFS in care expandam coada si modificam in o matrice d  rezultatele(daca a[i ][j] < a[vecin(i)] [vecin(j)]  ) atunci d[vecin(i)][vecin(j)]=d[i ][j] +1.
Cred ca e corect avand in vedere ca am luat 60 pct


Pt reconstituirea drumului am folosit 2 vectori
Am facut in felul urmator:
Atata timp cat nu am ajuns la poz initiala ,verific pt vecinii pozitii curente daca sunt cu 1 mai mici decat poz curenta,daca sunt salvez i,j in cei doi vectori si actualizez pozitiile.



Cum pot scapa de TLE si mai mult decat atat exista cazuri particulare?

Multumesc Anticipat!!!!

[•PlayLikeNeverB4]

Ai verificat sa nu introduci in coada de mai multe ori aceeasi celula ?

[•lucian666]

Am verificat
Insa pt un test de genul:
Cod:
5
1 1 1 2 3
3 1 3 3 3
1 2 3 4 4
5 6 6 6 6
1 1 1 1 1

raspunsul la mine este :
1
1 1
si nu stiu de ce.

Atunci cand bag in coada daca pun la conditia respectiva( a[i ][j] < vecin(sus  ) && a[i ][j] < vecin(jos )  ....... )
la testul de mai sus afiseaza 1
1 1
dar daca in conditie pun || imi afiseaza corect doar ca iau 40 pct restul cu TLE
 

[•SebiSebi]

Tu iei incorect pentru ca abordarea ta este gresita. In primul rand trebuie sa faci un fel de Bellman-Ford adica in conditia asta :

Cod:

if( ii>=1 && jj>=1 && ii<=n && jj<=n &&  a[i][j] < a[ii][jj] ) {
	d[ii][jj]=d[i][j]+1;
	Q.push(mp(ii,jj));
}

Mai trebuie sa adaugi d[ ii ] [ jj ] < d[ i ] [ j ] + 1 si cred ca merge.In al doilea rand nu inteleg de ce introduci in coada casutele care au toti vecinii mai mici.Pentru exemplul tau respunsul corect este :

Cod:

5
1 3
1 4
2 4
3 4
4 4

Deci incepe in 1,3 pe care tu nu il introduci in coada. Insa oricum vei lua TLE pe cateva teste. Eu am rezolvat folosind dinamica cu memoizare. Daca nu te prinzi da-mi un PM.

[•lucian666]

Am luat 90 pct pana la urma.AM mai pus o conditie la inceput inainte sa bag in coada si acum am 1 TLE pe testul 4

[•SebiSebi]

Vad ca ai si parsat citirea si tot ai un TLE. Asta e problema, complexitatea nu este cea optima, de aceea trebuie dinamica cu memoizare.

[•lucian666]

Vad ca ai si parsat citirea si tot ai un TLE. Asta e problema, complexitatea nu este cea optima, de aceea trebuie dinamica cu memoizare.

ti-am trimis PM in legatura cu memoizarea

[•andunhill]

Nu se poate mari limita de timp? Am facut dinamica cu memoizare + parsare si tot nu intra.

[•valex]

I-au 90 de puncte si un wrong answer pe testul 3 si nu ma prind de nicio culoare de ce.. 

[•felixi]

Poate sa imi spuna cineva ce am gresit la sursa mea? Am parsat citirea dar afisarea nu si imi da un test gresit daca parsez. Idei?

[•gedica]

Pot face problema cu un dfs si un vector de memorare? 

[•blackodd]

Imi poate spune cineva de ce iau 0 pe toate testele (pe 3 iau TLE) ?

#include <fstream>
#include <queue>

using namespace std;

ifstream fin("alpin.in");
ofstream fout("alpin.out");

#define Dim 1024
#define INF 16384

short imin, jmin, imax, jmax;
short n, a[Dim][Dim], c[Dim][Dim], minim = INF, maxim = -16384;
const short di[] = { -1, 0, 1, 0 };
const short dj[] = { 0, 1, 0, -1 };
queue<pair<int, int> >Q;

void Read();
void Lee();
bool OK(int i, int j);
void Write(int i, int j);

int main()
{
    Read();
    Lee();
    fout << maxim << '\n';
    Write( imax, jmax );
    fout << imax << ' ' << jmax << '\n';
    fin.close();
    fout.close();
    return 0;
}

void Write(int i, int j)
{
    if ( i == imin && j == jmin )
        return;
    if ( c[j-1] == c[j] - 1 && OK(i,j-1) )
    {
        Write(i, j - 1);
        fout << i << ' ' << j - 1 << '\n';
    }
    else
    if ( c[i-1][j] == c[j] - 1 && OK(i-1,j) )
    {
        Write( i - 1, j);
        fout << i - 1 << ' ' << j << '\n';
    }
    else
    if ( c[j+1] == c[j] - 1 && OK(i,j+1) )
    {
        Write(i, j + 1 );
        fout << i << ' ' << j + 1 << '\n';
    }
    else
    if ( c[i+1][j] == c[j] - 1 && OK(i+1,j) )
    {
        Write(i + 1, j);
        fout << i + 1 << ' ' << j << '\n';
    }
}

void Lee()
{
    int i, j, iv, jv;
    Q.push({imin,jmin});
    c[imin][jmin] = 1;
    while ( !Q.empty() )
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for ( int d = 0; d < 4; ++d )
        {
            iv = i + di[d];
            jv = j + dj[d];
            if ( OK(iv, jv) && a[iv][jv] > a[j] )
            {
                c[iv][jv] = c[j] + 1;
                Q.push({iv,jv});
                if ( c[iv][jv] > maxim ) {
                    maxim = c[iv][jv];
                    imax = iv, jmax = jv;} // retinem coord drumului maxim
            }
        }
    }
}

bool OK(int i, int j)
{
    if ( i < 1 or i > n or j < 1 or j > n )
        return false;
    return true;
}

void Read()
{
    fin >> n;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
        {
            fin >> a[j];
            c[j] = INF;
            if ( a[j] < minim ) // cautam punctul de plecare
            {
                minim = a[j]; // adica minimul din matrice
                imin = i; // retinem coordonatele
                jmin = j;
            }
        }
}

[•blackodd]

** De fapt iau Memory limit exceeded pe 2 teste, nu TLE.

[•PlayLikeNeverB4]

Nu faci bine parcurgerea. Introduci de prea multe ori elementul in coada, de asta iei MLE/TLE. Incearca sa inveti http://www.infoarena.ro/problema/bfs si http://www.infoarena.ro/problema/bellmanford. Acestea fiind zise, rezolvarea ta nu e corecta. Vezi ce s-a scris prin acest topic.

[•depevlad]

Imi poate spune si mie cineva de ce pe testul 9, imi spune ca lungimea este corecta dar drumul afisat incorect? Ma chinui la asta de 2 ore 

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX 1025
#define BORDER -(1<<30)
#define DIR 4

int a[MAX][MAX], s[MAX][MAX];
int dx[DIR] = {-1, 0, 1, 0};
int dy[DIR] = {0, 1, 0, -1};

int extend(int i, int j) {
    if(s[j]) return s[j];
    int _max = 1, k, val;
    for(k = 0; k < DIR; k++)
        if(a[i+dx[k]][j+dy[k]] > a[j] && a[i+dx[k]][j+dy[k]] >= 0)
            if(extend(i+dx[k], j+dy[k]) + 1 > _max)
                _max = extend(i+dx[k], j+dy[k]) + 1;
    s[j] = _max;
    return s[j];
}

int main() {
    FILE *in = fopen("alpin.in", "r");
    FILE *out = fopen("alpin.out", "w");
   
    int n, _max = 0, val, i, j, x, y;
   
    fscanf(in, "%d", &n);
   
    for(i = 0; i <= n+1; i++) {
        a

• = a[0] = a[n+1] = a[n+1] = BORDER;

        s

• = s[0] = s[n+1] = s[n+1] = BORDER;

    }
   
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            fscanf(in, "%d", &a[j]);
   
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++) {
            if(extend(i,j) > _max) {
                _max = extend(i,j);
                x = i;
                y = j;
            }
        }
       
    fprintf(out, "%d\n", _max);
    fprintf(out, "%d %d\n", x, y);
   
    while(s

• [y] != 1) {

        for(i = 0; i < DIR; i++)
            if(s[x+dx][y+dy] == s

• [y] - 1)

                break;
        x += dx;
        y += dy;
        fprintf(out, "%d %d\n", x, y);
    }
   
    return 0;
}

Daca nu e voie sa postez surse aici, imi cer scuze si va rog sa stergeti postarea. Multumesc! 

[•BaTDucK]

if(s[x+dx][y+dy] == s[ x][y] - 1)

Conditia nu este suficienta, verifica si daca celula in care "urci" este mai mare ca precedenta.

[•depevlad]

Am luat 100 pct, mersi mult! 

[•StarGold2]

Problema nu necesita sortare, eu am facut-o fara in complexitate O(n^2) folosind <vector>, si am luat pe testul 10 600 ms!!!

[•hopingsteam]

Altitudinea poate fi negativa (sau nula)? Ma gandesc ca nu..