018 Siruri 2-3-monotone

[•fluffy]

Aici puteţi discuta despre problema Siruri 2-3-monotone.

[•bogdan2412]

Poate cineva sa-mi spuna si mie cum se rezolva aceasta problema sau sa-mi dea un indiciu? Ce complexitate ar trebui sa aiba (nu e nici o restrictie in problema pt n)?

[•silviug]

Iti inteleg nelamurirea. Enuntul nu este "case sensitive" deci n = N <= 1000. Complexitatea recomandata este de O(N^2). O solutie O(N^3) poti gasi si pe .campion (problema a fost propusa la o runda de pregatire la grupa mare). Solutia de pe .campion poate fi imbunatatita si se ajunge la o solutie O(N^2) folosind cateva observatii matematice.

Succes,

Silviu

[•ParrAzitU]

Sau se poate face oricand un O(1)      

[•silviug]

Spune-mi si mie cum faci O(1) ... ca eu nu stiu !!

Silviu

PS: Solutia cu constante e O(N) (mai judeca un pic si o sa vezi ca am dreptate )

[•ParrAzitU]

Cod:

int main () {

   freopen("sir23.in","r",stdin); freopen("sir23.out","w",stdout);
   scanf("%d", &k);
   printf("%d\n", s[k-1]);

   return 0;
}

No deci dupa judecata mea asta ii O(1)..
Dc nu explica-mi si mie terog dece e O(n)  

[•silviug]

Si unde e partea cu initializarea ?? Aia ce complexitate are ?

[•ParrAzitU]

:lol: declar un sir de constante de lungime constanta 1000
nu il pun acuma aicia din motive evidente.
Da oricum e O(1) sau oricum as initializa O(1000) = O(1) nu ??      
 

[•Cosmin]

Pai atunci orice problema de pe infoarena e rezolvabila in mai putin de 100^100 operatii, deci orice problema de pe infoarena e rezolvabila in O(1).

[•svalentin]

:lol: declar un sir de constante de lungime constanta 1000
nu il pun acuma aicia din motive evidente.
Da oricum e O(1) sau oricum as initializa O(1000) = O(1) nu ??      
 

hai sa fim seriosi; e O(N);
ca stii tu ca N=1000 si iti da O(1000) bravo; dar asa poti sa zici la orice problema ca ai complexitate O(N*M*K), iar tu stii ca N,M si K au maxim 10^10; deci ai complexitate maxima O(10^30)=O(1)
nu?!?

[•silviug]

Parazitule.. ideea e ca numarul de initializari pe care le faci depinde de N. Ca e N-ul mai mic ca o mie e o pura intamplare .. deci pentru problema ta, daca N-ul creste, iti creste si numarul de initializari => complexitate O(N) !!

[•ParrAzitU]

Pai acuma nu vreau sa insist prea mult pe kestia asta, nu mi se pare asa de important, da oricum e O(1) , ca am 1000 de initializari, oricat ar fi N. (e declarat un sir de constante de lungime 1000) deci e O(1)!
alte pareri ?    

[•ParrAzitU]

:lol: declar un sir de constante de lungime constanta 1000
nu il pun acuma aicia din motive evidente.
Da oricum e O(1) sau oricum as initializa O(1000) = O(1) nu ??      
 

hai sa fim seriosi; e O(N);
ca stii tu ca N=1000 si iti da O(1000) bravo; dar asa poti sa zici la orice problema ca ai complexitate O(N*M*K), iar tu stii ca N,M si K au maxim 10^10; deci ai complexitate maxima O(10^30)=O(1)
nu?!?

Deci acuma serios.... dc stii cum se evalueaza complexitatea algoritmului, ai stii ca dc nu depide de nici o variabila e O(1) ... asa ca nu vad rostul O(N*M*K) = O(10^30) = O(1).. mai gandestete tu

[•silviug]

Pai si la tine e acelasi lucru: O(N) initializari = O(1000) = O(1) !! (ceea ce e naspa!!)

[•ParrAzitU]

Acuma serios, asta e ultimul lucru care il zic :
nu sunt n intializari ca sunt 1000 !!
oricat ar fi n si dc e 2, sau  3 sau ...
defapt  e o singura initializare a unui sir de 1000 de constante, da dc voi vreti sa zicem ca sunt 1000 de initializari
Cum sa fie O(N) initializari Sunt clar O(1) !!! Ce e asa de greu ?
In fine dc tu vrei e O(N), sau poate O(N^2) dc N e sqrt(1000) cumva si eu intializez de 1000 sau cat vrei tu

Next subj, ca deja asta ma plictiseste...

[•silviug]

Mah.. daca N-ul maxim creste .. ce face numarul de initializari pe care il faci tu ramane acelasi ?

Raspuns: NU!!!

Sau si mai marfa!!!


Cate locatii ai in memorie ?
Raspuns: O(N)
Cat iti ia sa le initializezi ?
Raspuns: O(N)

[•svalentin]

doar sa ai gija ca la concursuri sa nu scoti complexitati ca O(N), dar cu constanta 1000*1000

[•ParrAzitU]

doar sa ai gija ca la concursuri sa nu scoti complexitati ca O(N), dar cu constanta 1000*1000

Stai linistit ca imi intra in 0.1 secunde cu constanta 1000*1000...
Nu vad problema...

[•cristy]

auziti...imi spune si mie cineva care sunt alea 4 solutii pentru n=2? si cele 9 pentru n=3? pls...

[•danburzo]

Cate locatii ai in memorie ?
Raspuns: O(N)
Cat iti ia sa le initializezi ?
Raspuns: O(N)

Nu inteleg silviug ce e asa de greu sa te prinzi. Te rog sa-mi explici si mie cum depinde de n faptul ca eu am in program :

Cod:

int[1000]={1,2,3, bla bla}

alocarea se face intr-un spatiu constant de memorie si in timp constant - tot timpu sunt 1000 de chestii for crying out loud   .

Cred ca confunzi cu citirea a n numere sau nush.

Nu stiu cum vedeti voi, dar eu cred ca e O(1).

So sue me .  

[cristi8]

se fac NMAX operatii, nu n .. si NMAX e constant.. la timp, intr-un fel e      o(n) pe cazul cel mai defavorabil... dar la complexitate ramane teoretic     o(1) cu o constanta f mare (NMAX)..

dar in practica e mai bine sa "iei" o(n) , sa aproximezi mai bine timpul de executie



..parerea mea

[•silviug]

Nu inteleg silviug ce e asa de greu sa te prinzi. Te rog sa-mi explici si mie cum depinde de n faptul ca eu am in program

Si iar incepem ..

Tu ai NMAX locatii de memorie care in cazul de fata e 1000. Okay, toate bune si frumoase dar daca marim valoarea maxima a lui N la, sa zicem, la 10^6 ce vei face ? Programul tau tot 1000 de locatii de memorie / operatii va folosi ?

Raspunsul este clar: NU => numarul de operatii facute de programul tau depinde de N, si mai exact, face O(N) operatii folosind O(N) memorie.

Reamintesc ca e o chestiune subtila aici in care va prindeti urechile. Daca programul tau e intr-adevar O(1) inseamna ca oricat de mare ar fi N-ul (adica facand N sa tinda la infinit) tu tot un numar constant de operatii faci.. wich is not the case!!!

Eu zic sa te mai dai odata cu capul de zid si sa mai citesti eventual vreun articol despre calcularea complexitatii unui algoritm (iti recomand Cormen).

Si acum e randul meu   cu promisiunea ca acesta este ultimul post despre acest subiect.

Silviu

[•wickedman]

In toate notatiile asimptotice N tinde spre infinit.
Cand spui ca ai facut un algoritm de complexitate O(f(n)) faci abstractie de "NMAX-uri".

se fac NMAX operatii, nu n .. si NMAX e constant..

pai daca vrei s-o iei asa (no pun intended), majoritatea problemelor de informatica rezolvabile pe calculator au un "NMAX", deci avem timp constant... chiar daca algoritmul e O(N^N).
 

[cristi8]

da ma da ! asa e... o(n) .. sry    

..se confunda n din o(n) cu n-ul care se citeste..

[•danburzo]

Io zic sa lasam subiectul balta. Oricum sorry ca m-am bagat in povestea asta. Poate ca mai am de invatat... si cand pa prind io ce compexitate are de fapt va scriu
Am inceput pe picior gresit oricum