Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 724 Stiva  (Citit de 1761 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« : Mai 24, 2008, 12:43:49 »

Aici puteţi discuta despre problema Stiva.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #1 : Octombrie 15, 2009, 17:12:17 »

Iau TLE cu o dinamica in O(N^3) . Se poate mai rapid?  Think
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #2 : Octombrie 15, 2009, 17:27:12 »

Mi se pare ca solutia oficiala e tot n^3.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #3 : Octombrie 15, 2009, 17:33:42 »

Mda. Am trimis si sursa oficiala, care e o(n^3), si ia tot 80 de puncte. Care e optimizarea ce trebuie facuta pt 100 ?
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #4 : Septembrie 26, 2012, 17:36:17 »

E prea mica limita de timp
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #5 : Octombrie 01, 2012, 19:29:50 »

Am modificat-o la 0.2
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
mvcl3
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #6 : Iunie 25, 2013, 18:30:19 »

Explicati-mi si mie un pic va rog ideea cu o(n^3) ca nu ma prind  Brick wall
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #7 : Iunie 25, 2013, 20:58:53 »

Ideea se bazeaza pe o dinamica in n^3. In primul rand pentru orice sir vei folosi n operatii de tipul top(); numarul de operatii de tipul push() va fi tot timpul egal cu numarul de operatii de tipul pop(). Acum problema devine in afla numarul minim de operatii de tipul push() a. i. sa obtii sirul [i..j]; Raspunsul final fiind Nr minim de operatii de a obtine sirul 1...n * 2 (nr de pop-uri) + n (nr de top() -uri); dinamica ar fi dp[ i ] [ j ] = nr minim de operatii de tipul push pentru a obtine sirul i...j;
Cod:
dp[i][j] = dp[i][j-1] + 1;// pur si simplu mai pun caracaterul Text[j];
sau dp[i][j] = dp[i][k] + dp[k+1][j-1], cu k = i,j-1 si Text[k] == Text[j];// asta inseamna ca fac sirul i...k cu un numar minim de operatii dupa care il fac pe k+1...j-1 si cand il pun pe j nu il pun in mod practic ( adica numai apelez push() ) ci scot tot ce e pe
intervalul [k+1..j-1] si o sa ii dau "top()" de Text[j];
Memorat
mvcl3
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #8 : Iunie 26, 2013, 15:42:02 »

Multumesc frumos! am luat 100p Banana
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines