Mie mi-a placut. Bravo baieti! Solutiile le vedem?

Eu am facut cu vectori pentru grupele de puncte. Memoria este clar O(n) - am 3000 de shorturi pentru linii, si inca aprox. 3000 pentru puncte. De fiecare data cand introduc un punct intr-o grupa, il scot din alta, deci nu se pot sa se umfle vectorii aia. Totusi, iau MLE pe testul 9.

http://www.infoarena.ro/job_detail/1474698 - aici e borderoul de evaluare.

Poate sa imi spuna cineva de ce iau MLE si ce pot sa fac sa scap de el?

Multumesc anticipat.

Jetoanele sunt diferite adica jetoanele lui Serban sunt diferite intrel ele si jetoanele Teodorei la fel sau ca multimile jetoanelor celor doi sunt disjuncte?

Am facut pentru problema asta 2 surse, una in care am folosit algoritmul lui Dijkstra "ca la carte", si una in care faceam un fel de bfs - bagam un element in coada, ma duceam la toti vecinii, iar daca distanta noua pana la vecini este mai mica decat distanta veche, reintroduceam vecinul in coada si recalculam. A doua sursa a luat, neasteptat, tot 100 pct. Ba chiar a obtinut timpi mai buni de executie, in medie, decat abordarea clasica cu Dijkstra. Cum e posibil acest lucru, nu ar trebui sa aiba o complexitate mai mare, care trage spre n patrat?  As aprecia mult daca m-ar ajuta cineva sa inteleg cum sursa aparent mai proasta o depaseste pe cea cu Dijkstra.

Iata cele doua surse si borderourile de evaluare:

1. Dijkstra:
http://www.infoarena.ro/job_detail/1399323 - borderou
http://www.infoarena.ro/job_detail/1399323?action=view-source - sursa

2. BFS:
http://www.infoarena.ro/job_detail/1399062 - borderou
http://www.infoarena.ro/job_detail/1399062?action=view-source - sursa.

Multumesc anticipat 

Eu facusem initial problema cu o stiva, cu compexitate O(n) si o constanta de vreo 4, dar lua 80 de puncte din cauza a doua teste care dadeau TLE . Pentru cei care au aceeasi problema, sa stiti ca pentru mine parsarea a scos 100 pct. 

Am luat 100 pct, mersi mult! 

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!