|
Titlul: 025 Munte Scris de: Dan-Leonard Crestez din Aprilie 01, 2004, 00:32:22 Aici puteţi discuta despre problema Munte (http://infoarena.ro/problema/munte).
Titlul: 025 Munte Scris de: Toma Radu din Iunie 30, 2005, 11:41:22 Cam care ar fi complexitatea optima la problema asta ca iau TLE pe 6 teste? :-k
Titlul: 025 Munte Scris de: Mircea Pasoi din Iunie 30, 2005, 11:45:57 Citat din mesajul lui: tm_radu Cam care ar fi complexitatea optima la problema asta ca iau TLE pe 6 teste? :-k O rezolvare O(D*N*K) corecta e de ajuns pentru a obtine punctajul maxim. Titlul: 025 Munte Scris de: Toma Radu din Iunie 30, 2005, 12:09:23 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;
Titlul: 025 Munte Scris de: andreit1 din Iunie 30, 2005, 12:30:24 In nici un caz backtracking. Incearca sa gasesti dinamica in complexitatea sugerata mai sus.
Titlul: 025 Munte Scris de: Filip Cristian Buruiana din Iunie 30, 2005, 13:20:51 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! 8) Titlul: 025 Munte Scris de: Toma Radu din Iunie 30, 2005, 14:14:06 Mersi de sfaturi. :)
Titlul: 025 Munte Scris de: Filip Cristian Buruiana din Iunie 30, 2005, 14:41:19 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. Titlul: 025 Munte Scris de: Toma Radu din Iunie 30, 2005, 15:27:28 Ce metoda ai folosit?
Titlul: 025 Munte Scris de: andreit1 din Iunie 30, 2005, 15:45:05 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]
Titlul: 025 Munte Scris de: Toma Radu din Iunie 30, 2005, 16:02:54 is incepator, asa ca nu va enervati, da nu-mi dau seama cum pot folosi programarea dinamica sa rezolv problema
Titlul: 025 Munte Scris de: andreit1 din Iunie 30, 2005, 16:23:24 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...
Titlul: 025 Munte Scris de: Filip Cristian Buruiana din Iunie 30, 2005, 18:44:52 Mersi mult, Andrei. Intr-adevar, nu prea m-am gandit profund la problema asta :)
Titlul: 025 Munte Scris de: Toma Radu din Iulie 02, 2005, 22:19:33 Nici eu.......asa profund
Titlul: 025 Munte Scris de: Filip Cristian Buruiana din Iulie 03, 2005, 09:18:06 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 Titlul: 025 Munte Scris de: Toma Radu din Octombrie 05, 2005, 15:18:02 N-am reusit inca sa gasesc relatia de recurenta. Ma poate ajuta cineva?
Titlul: 025 Munte Scris de: Bogdan-Cristian Tataroiu din Octombrie 05, 2005, 15:57:03 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. Titlul: 025 Munte Scris de: Toma Radu din Octombrie 08, 2005, 18:08:17 Mersi pentru sfaturi. O sa mai fac niste probleme de dinamica mai usoare ca sa ma familiarizez cu ele.
Titlul: 025 Munte Scris de: Oltean Dorin din Octombrie 09, 2005, 10:21:51 pentru ultimul exemplu din enunt
Cod:
pargurgerile sunt : Cod:
Titlul: 025 Munte Scris de: cristi8 din Octombrie 09, 2005, 12:50:33 parca nu aveau voie sa inceapa sau sa se termine cu "_"
h=0 e doar la inceput si sfarsit Titlul: 025 Munte Scris de: Oltean Dorin din Octombrie 09, 2005, 20:40:15 si atunci in loc de ultima ce vine ???
penultima modificata... Titlul: 025 Munte Scris de: Bogdan-Cristian Tataroiu din Octombrie 09, 2005, 20:43:15 Cod: /\/\ Titlul: 025 Munte Scris de: Andrei Grigorean din Noiembrie 16, 2005, 17:13:34 imi spuneti si mie va rog cat trebuie sa dea ptr:
Cod:
? Titlul: 025 Munte Scris de: VladS din Noiembrie 16, 2005, 18:38:43 43141453917002
Titlul: 025 Munte Scris de: Andrei Grigorean din Noiembrie 16, 2005, 18:50:20 atat imi da si mie.. ms mult
inseamna k imi depaseste int64 la un mom dat, fac pe numere mari. Titlul: 025 Munte Scris de: VladS din Noiembrie 16, 2005, 19:14:40 Poti folosi int64 cu incredere. De fapt scrie si in enunt.
Titlul: 025 Munte Scris de: Andrei Grigorean din Noiembrie 16, 2005, 19:50:00 nu stiu de ce dar tot iau WA pe 8 teste... :angry:
ptr: Cod:
va da 75500211146359 ? Titlul: 025 Munte Scris de: VladS din Noiembrie 16, 2005, 19:57:55 Da, iti da bine. Vezi poate gresesti la afisare sau chestii din astea marunte.
Titlul: Raspuns: 025 Munte Scris de: David si Goliat din Iulie 26, 2006, 13:16:59 la mine am calculat pe foaie pt exemplu 4 si mi-au iesit mult mai multe solutii :vreo 15 . oare ce nu am luat in calcul?
Titlul: Raspuns: 025 Munte Scris de: David si Goliat din Iulie 26, 2006, 13:24:10 de fapt sunt un prost :oops: n-am citit prea bine problema . am facut pentru cazul in care punctele obiectivele sunt vizitate in orice ordine ???
Titlul: Răspuns: 025 Munte Scris de: nash mit din Aprilie 16, 2010, 00:22:46 ok... probabil ca sunt prea obosit dar chiar si asa devine enervant... la problema asta am facut o dinamca la care am ajuns la urmatoarea recurenta :
Cod:
totusi nu imi da rezultatul dorit... nicio data si nu inteleg de ce... si nu cred ca am pierdut vre-un caz (stiu ca sparg cache-ul... la modul in care am pus acolo niste indici... dar ideea este ca nu da rezultat corect si nu ca iese din timp ) Titlul: Răspuns: 025 Munte Scris de: Airinei Adrian din Aprilie 16, 2010, 13:16:48 Trebuie sa gandesti din nou recurenta si sa obtii o recurenta mult mai simplificata decat ce ai scris tu acolo. Cand ai 15 cazuri e foarte usor sa gresesti.
Titlul: Răspuns: 025 Munte Scris de: nash mit din Aprilie 16, 2010, 16:23:52 Chiar 18 :)
Nu imi vine in minte cum as putea sa pun in recurenta mai simplu asa ca o sa incerc sa ma explic ca sa fie mai clar ce fac acolo: sol[ i ][ j ][ T ][ P ] -> inseamna numarul de moduri in care pot sa ajung de la pozitia "i" la pozitia "n" ( lungimea pe verticala a muntelui este "n" ) aflandu-ma la inaltimea "j" si daca am reusit sa trec prin inaltimea maxima ( T de la true ) trecand prin punctul special "p" . sol[ i ][ j ][ F ][ P ] -> aproape la fel doar ca in loc de T avem F adica "inca nu am reusit sa trecem prin punctul maxim al muntelui. si acum cum se formeaza este exact ca in recurenta care am precizat-o pentru sol[ i ][ j ][ T ][ P ] avem posibilitatile : - sa venim din pozitia "i+1"(din fata) cu inaltimile "j+1" ,"j" sau "j-1" dintr-o pozitia care face parte dintru-un sir care a trecut prin punctul maxim ( deci cu "T" ) si care a trecut prin punctul obligatoriu "p" ( adica punct[p] ) : sol[i+1][j+1][T][p] sol[i+1][j ][T][p] sol[i+1][SAFE(j-1)][T][p] - sa venimla fel ca mai innainte doar ca dintr-o pozitia care inca nu a trecut prin innaltimea maxima ( deci "F" (false) in loc de T) si care la pozitia actuala se va afla la inatimea maxima adica "j = h" : sol[i+1][j+1][F][p] * (h==j) sol[i+1][j ][F][p] * (h==j) sol[i+1][SAFE(j-1)][F][p] * (h==j) - sa venim ca in primul caz doar ca sa nu fi trecut prin punctul "p" inca sol[i+1][SAFE(j-1)][T][p-1] * (punct[p] == j) sol[i+1][j ][T][p-1] * (punct[p] == j) sol[i+1][j+1][T][p-1] * (punct[p] == j) -sa venim la fel ca in cazul 2 doar ca inca sa nu fi atins punctul de "h" maxim : sol[i+1][SAFE(j-1)][F][p-1] * (punct[p] == j) * (h == j) sol[i+1][j ][F][p-1] * (punct[p] == j) * (h == j) sol[i+1][j+1][F][p-1] * (punct[p] == j) * (h == j); pentru cazul : sol[ i ][ j ][ F ][ P ] se merge pe acesi idee doar ca singurul mod in care se poate ajunge intr-o stare care inca nu a trecut prin punctul maxim deci cu "F" este sa vina tot din stari care inca nu au trecut prin punctul maxim. Am facut o modificare : peste tot unde este"p-1" trebuia "p+1"... poti sa ajungi la punctul "p" din "p+1" ca mergi invers de la "n" la "1" cu "i-ul" rezultatul este acelas ( adica tot nu imi da nimic corect ) Titlul: Răspuns: 025 Munte Scris de: Airinei Adrian din Aprilie 16, 2010, 17:18:14 Poate te ajuta cum am retinut eu starile la problema asta: A(i,j,k,t) = numarul de posibilitati sa ajung la inaltimea i, la distanta j pe orizontala, trecand prin primele k puncte speciale; t = 1 sau 0 daca am atins pana aici intaltimea N sau nu. Solutia se va afla in A(1, D, K, 1).
Titlul: Răspuns: 025 Munte Scris de: nash mit din Aprilie 16, 2010, 18:19:47 Avem fix aceasi recurenta :) si acelas mod de a retine... doar ordinea difera :) si tu pleci de la 1 la n eu invers . O diferenta este faptul ca eu am solutia in punctul in care inaltimea este "0" .
"heorghe avand toate aceste informatii, N (inaltimea maxima a muntelui, presupunand ca muntele incepe la nivelul 0 si se termina la nivelul 0)......." Titlul: Răspuns: 025 Munte Scris de: Florian Marcu din Aprilie 17, 2010, 10:47:48 Tii cont ca nu poti sa atingi nivelul 0 decat la inceput si sfarsit?
Titlul: Răspuns: 025 Munte Scris de: nash mit din Aprilie 22, 2010, 14:30:10 Nu, nu tineam cont... merci:)
Titlul: Răspuns: 025 Munte Scris de: Simoiu Robert din Septembrie 13, 2010, 15:48:40 Este gresit la specificatii . In loc de 1 <= N <= 50, trebuie 1 <= N <= 100 .
Titlul: Răspuns: 025 Munte Scris de: Paul-Dan Baltescu din Septembrie 13, 2010, 18:25:03 Toate testele respecta restrictiile specificate in enunt.
Citesti tu datele de intrare in alta ordine. Verifica-te si tu de doua ori inainte sa postezi. In atata timp, sigur ar fi sesizat cineva mai repede daca era vreo greseala. Titlul: Răspuns: 025 Munte Scris de: Simoiu Robert din Septembrie 13, 2010, 20:20:04 Am pus codul asta si am primit SIGABRT. L-am scos si am primit KBS 11 ( fiindca aveam matricea doar 50 ) .
Cod: assert ( 1 <= N && N <= 50 ) ; Titlul: Răspuns: 025 Munte Scris de: Mardare Rares din Decembrie 20, 2010, 12:50:57 Pentru 3 8 4 si punctele 2, 2, 3, 1 o parcurgere de genul
- urc 2 bete in sus, 2 bete la dreapta, un bat in sus si 3 in jos e corecta? Titlul: Răspuns: 025 Munte Scris de: Paul-Dan Baltescu din Decembrie 20, 2010, 16:21:59 Da.
Titlul: Răspuns: 025 Munte Scris de: Mihai Grebla din Octombrie 05, 2017, 20:59:09 Am incercat cu numerele lui Catalan si am obtinut 20 de puncte, sfaturi?
:-k |