025 Munte

[•fluffy]

Aici puteţi discuta despre problema Munte.

[•tm_radu]

Cam care ar fi complexitatea optima la problema asta ca iau TLE pe 6 teste?  

[•domino]

Cam care ar fi complexitatea optima la problema asta ca iau TLE pe 6 teste?  

O rezolvare O(D*N*K) corecta e de ajuns pentru a obtine punctajul maxim.

[•tm_radu]

Eu am calculat cu backtracking un sir x care reprezinta inaltimea in puntul i (0......d). punctele speciale le-am verificat cu un sir caracteristic O(1), si inaltimea cu o variabila ce retine inaltimea maxima 0.....i;

[andreit1]

In nici un caz backtracking. Incearca sa gasesti dinamica in complexitatea sugerata mai sus.

[•filipb]

Daca nu reusesti cu dinamica, sa stii ca si backtracking-ul tau poate fi imbunatatit (sa mai iei 10-15 puncte...). De exemplu in stiva de back retii pe fiecare pozitie {0, 1, 2}, adica 0 pentru segment orizontal, 1 - pt. segment care urca, 2 - pt. segment care coboara...
  In plus, ca un caz particular, daca K = 0, se poate rezolva si cu numerele lui Catalan.

  Spor la lucru!  

[•tm_radu]

Mersi de sfaturi.  

[•filipb]

M-am uitat si eu pe problema... Inca nu am postat-o... Totusi complexitatea nu este O(D * N * N * K)? Adica avem de retinut lungimea, inaltimea maxima, primele K puncte speciale daca au fost bifate si nu mai trebuia sa retinem si inaltimea ultimului punct ( ca sa stim unde ajungem si eventual sa actualizam maxima... )?

 Filip b.

[•tm_radu]

Ce metoda ai folosit?

[andreit1]

Filip, nu are rost sa pui o dimensiune [1..n] pentru inaltimea maxima. Eu am pus doar[0..1]: 0 daca nu s-a atins maximul si 1 daca s-a atins.[/quote]

[•tm_radu]

is incepator, asa ca nu va enervati, da nu-mi dau seama cum pot folosi programarea dinamica sa rezolv problema

[andreit1]

Eu am lucrat in '4' dimensiuni. m[i,j,k,l]=numarul de posibilitati ca gheorghe sa ajunga la distanta i de plecare, sa fie la inaltimea j, sa fi trecut deja prin primele k puncte speciale, iar l este 1 daca a atins inaltimea maxima, sau 0 daca nu. Pentru a calcula m[I ] ai nevoie doar de m[i-1], deci in memorie trebuie sa tii doar o matrice [n,k,1]. Formula de recurenta o deduci singur...

[•filipb]

Mersi mult, Andrei. Intr-adevar, nu prea m-am gandit profund la problema asta

[•tm_radu]

Nici eu.......asa profund

[•filipb]

Iti sugerez sa incepi cu probleme mai usoare de dinamica daca esti incepator, asta e "destul de incalcita"... Incearca alta probleme mai usurele din arhiva: "perm" (asta e o relatie de recurenta cunoscuta... nu iti spun mai mult), "joc", "siruri 2-3 monotone" (si asta e destul de grea daca nu o stii dinainte ), "Energii", etc.

  bubbleSORT

[•tm_radu]

N-am reusit inca sa gasesc relatia de recurenta. Ma poate ajuta cineva?

[•bogdan2412]

Te afli intr-un anumit punct, la o anumita distanta fata de origine si la o anumita inaltime. Din acel punct te poti duce in 3 directii inaintand in sus, orizontal sau in jos. Cand cauti relatia de recurenta te gandesti din ce puncte ajungi in punctu curent si ai tot 3 posibilitati. Iei doua cazuri: dc inaltimea la care esti in momentul actual este egala cu cea a punctului special in care trebuie ajungii sau nu si vezi ce diferente sunt intre cele doua cazuti. Te mai gandesti cum rezolvi problema daca ai atins sau nu maximul.
Mai mult decat atat n-am ce sa-ti spun.
Mai fa niste probleme de dinamica mai simple dintr-o carte sau ceva si o sa te prinzi pana la urma.

[•tm_radu]

Mersi pentru sfaturi. O sa mai fac niste probleme de dinamica mai usoare ca sa ma familiarizez cu ele.

[•Dorin]

pentru ultimul exemplu din enunt

Cod:

3 8 4 
2
2
3
1

pargurgerile sunt :

Cod:

  _/\
 /   \_
/      \
12345678
   _/\
 _/   \
/      \
12345678
  __/\
 /    \
/      \
12345678
    /\
 /\/  \
/      \
12345678
  _/\_
 /    \
/      \
12345678
    _
  _/ \
 /    \
/      \
12345678
   _/\
  /   \
_/     \
12345678

[cristi8]

parca nu aveau voie sa inceapa sau sa se termine cu "_"
h=0 e doar la inceput si sfarsit

[•Dorin]

si atunci in loc de ultima ce vine
penultima modificata...

[•bogdan2412]

Cod:

  /\/\
 /    \
/      \

[•wefgef]

imi spuneti si mie va rog cat trebuie sa dea ptr:

Cod:

10 40 7
3
8
9
5
3
3
2

?

[VladS]

43141453917002

[•wefgef]

atat imi da si mie.. ms mult

inseamna k imi depaseste int64 la un mom dat, fac pe numere mari.