258 Alpin

[•Protoman]

Hy,
   Am incercat sa fac problema cam in 3 moduri ...
   -Odata cu sortarea elem din matrice O(n^2log n) si am luat 70 de puncte: TLE pe ultimile 2 teste si non zero exit status pe al 4-lea.
   -Alta data am incercat sa caut elementul minim din matrice si sa-l expandez cu 2 cozi ... imi iesea din timp pe toate testele. Am micsorat cozile si am luat 40 de puncte TLE pe ultimele 5 si pe al 4-lea (iar). 
   -A 3-a oara ( si cea mai buna ) am cautat elemntul minim si l-am expandat cu o singura coada. Am luat 90 de puncte cu timpi buni la ultimile teste dar iau "Killed by signal 11(SIGSEGV)." pe testul 4.   
   Care ar fi cele mai particulare cazuri? Am incercat toate elementele diferite, parcurgerea in spirala , toate elementele egale... imi dadea bine la toate
   Any hint  ?

[•peanutz]

Daca ti-ar da incorect ai putea vorbi de un caz particular. Nu ai incercat sa maresti coada?

[•Protoman]

Am incercat ...    oricum e totusi mai mare decat n^2 si sunt sigur ca nu bag de 2 ori aceleasi elemente. Ceea ce nu inteleg este cum de nici o metoda nu a trecut testul .
Alte idei ?

[•astronomy]

Pe prima pagina sunt hint-uri cum sa rezolvi corect problema

[•filipb]

Am incercat ...    oricum e totusi mai mare decat n^2 si sunt sigur ca nu bag de 2 ori aceleasi elemente. Ceea ce nu inteleg este cum de nici o metoda nu a trecut testul .
Alte idei ?

Ia incearca ceva particular de genul:

Cod:

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

Raspunsul corect e 25. Eventual fa un debug sa vezi daca programul functioneaza corect si ar trebui sa descoperi bugul.

[•Protoman]

Cod:

25
1 1
1 2
1 3
1 4
1 5
2 5
2 4
2 3
2 2
2 1
3 1
3 2
3 3
3 4
3 5
4 5
4 4
4 3
4 2
4 1
5 1
5 2
5 3
5 4
5 5

se pare ca imi da bine... am luat cu debug sa vad unde ar putea sa sara din dimensiunile vectorului sau ceva asemanator dar nu vad niciun bug .
Algortimul meu e bun totusi... ia 90 de puncte intrand lejer in timp ...

are ceva special testul 4?...adica...am TLE pe el, restu imi intra lejer in timp...dar pe asta iau TLE...si vad ca altii scot 0.15s pe el...

am vazut ca au avut si altii "probleme" la testul acesta si inainte... voi mai incerca sa schimb dimensiunile ... Mersi

OK. Asa voi face!

[•filipb]

Testul 4 are structura similara cu cel care ti l-am dat eu, dar are dimensiuni mai mari... In plus, incearca sa testezi pe Linux pentru ca pe Windows comportamentul este imprevizibil.

[•Dastas]

Mi-ati putea explica mai exact un pic cum trebuie folosita memoizarea la problema asta? Eu am o matrice b, unde b[ i][j] = lungimea maxima pana in punctul [i,j]... si calculez matricea asta recursiv, dar iese din timp pe testul 4. Pe un test cu structura celui dat de filipb, se fac intr-adevar foarte multe apeluri recursive, mult mai multe decat n^2.

Stiu ca memoizarea se poate folosi in calcularea functiei fibonacci, de exemplu, pentru a evita recalcularea de mai multe ori a aceleiasi valori in apeluri recursive. Aici insa eu nu vad cum m-as putea folosi de tehnica asta...

[•filipb]

Fie M[i, j] lungimea maxima a unui traseu care se termina in (i, j). Altitudinea maxima e 16 384. De aceea putem itera fiecare altitudine h de la 1 la 16 384 si sa calculam valorile M[i, j] pentru toate zonele (i j) care au altitudinea h. Astfel, cand suntem la altitudinea h, avem precalculate toate zonele care au altitudinile 1, 2, ... h-1. Un pseudocod arata cam asa:

Cod:

pentru h de la 1 la ALTITUDINE_MAXIMA
          pentru toate casutele (i j) cu altitudinea h
                    M[i][j] = maxim(M[sx][sy]) + 1, (sx sy) vecin cu (i j) si altitudinea din (sx sy) < altitudinea din (i j)

Trebuie sa pui conditia "altitudinea din (sx sy) < altitudinea din (i j)" pentru a evita egalitatea inaltimii din (sx sy) cu cea din (i j). In plus, pentru a extrage toate casutele (i j) cu altitudinea h poti folosi liste.

Cam asa

[•wefgef]

Poti sa ignori faptul ca ai o limita superioara pentru inaltimi.

Tii o matrice best[i, j] - lungimea maxima a unui drum care se termina in pozitia (i, j) si iti construiesti o functie recursiva cu doi parametri, sa ii spunem f(i, j), care iti calculeaza best[i, j] (daca nu e calculata aceasta valoare deja) si o returneaza.

Functia ar fi cam asa:

Cod:

function f(int i, int j)
{
    daca best[i][j] > 0, returneaza best[i][j];

    ptr cei 4 vecini ai lui (i, j)
        daca Inaltime(vecin) < Inaltime( (i, j) ) si f(vecin) > best[i][j]
             best[i][j] = f(vecin);
    best[i][j] += 1;

    returneaza best[i][j];
}

[•filipb]

Da, memoizare recursiva . La mine era iterativ.

[•Dastas]

Cred ca am inteles acuma despre ce-i vorba, sper sa ma descurc mai departe.

Multumesc!

Dap, a mers de 100! Mersi inca o data, nu-mi dadeam seama cum sa aplic memoizarea aici... 

[•Robytzza]

am si eu o intrebare de ce iau KBS 11 pe testele 3,4 ?? folosesc 2 matrici,in una din ele pe (i,j) pastrez numarul maxim pe pasi cu care port sa ajung acolo si folosesc 2 cozi de 1000000 .In program ma mai intreb , daca cumva depasesc coarda ;daca da,pun elementele la inceputul corzi...   de ce iau KBS??

[•wefgef]

Probabil ca ai o greseala undeva in program din moment ce nu iei punctaj maxim pe toate celelalte teste. Vezi daca faci reconstituire bine.

Apropo, incearca sa scrii corect. E foarte obositor sa-ti citeasca cineva posturile.

[•Robytzza]

cat va da pe testul asta:
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


gata am rezolvat problema care o aveam la reconstituire ,insa tot mai am 2 KBS

de ce iau KBS?? am declarate 2 matrici de [1030][1030], aici nu are cum  sa depaseasca si 2 cozi de 1000000 circulare.Si nici macar nu merg pana la sfarsitul cozii, cand ajung la 999990 o iau de la capat ..nu vad care e problema 

[•Tabara]

cat va da pe testul asta:
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

Cu sursa de 100.

Cod:

5
1 3
1 4
2 4
3 4
4 4

[•Robytzza]

ms  mi-am dat seama unde greseam 

[•andrei-alpha]

Are cineva idee dc iau KBS daca declar matricea care o folosesc doar pentru a retine inaltimile , cu short int in loc de int .
.. (cu int iau suta , cu short 90 cu KBS)

[•gabitzish1]

inaltimea minima e 0, sau 1?

[•Mishu91]

Am o intrebare... cum mai pot optimiza pt ca am facut in O(N^2 + Hmax), da' iau TLE pe ultimu' test.   

[•gabitzish1]

Eu am parsat citirea sa intre si ultimul test. 

[•Mishu91]

Mersi fain... asa mi-a intrat si mie ultimu' test

[•gabitzish1]

Cu memoizare + citire parsata s'a luat 100 cu timpi < 300ms.

[•cipri_tom]

in caz ca se mai uita cineva pe aici... ce e aceea parsare? si, ce are asa de special testul 4? daca mai stie cumva careva problema...
trimiteti-mi PM daca raspundeti. Multumesc

[•SpiderMan]

Parsarea este citirea unui string si apoi transformarea lui in numar.