infoarena

Aici puteţi discuta despre problema Siruri 2-3-monotone (http://infoarena.ro/problema/sir23).

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)?

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

Sau se poate face oricand un O(1)  :P  :P  :P

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 :P)

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

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

: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 ??  :P  :P  :P
 :wink:

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).

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?!?

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 :D.. deci pentru problema ta, daca N-ul creste, iti creste si numarul de initializari => complexitate O(N) !!

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 ?  :twisted:  :twisted:

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

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

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...

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)

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...

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

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 :

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 .  8)

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

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

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".


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).
 \:D/

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

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

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 :wink:
Am inceput pe picior gresit oricum  :mrgreen:

De ce s-o lasi balta? Mai citeste ce ti s-a explicat, pana la urma vei intelege...  :-'

va rog...imi spune-ti care sunt solutiile pentru n=2 si n=3?...nu rezultatele ci...numerele cerute...

Pentru n = 2: (1,1), (1,2),(2,1),(2,2) -> 4 moduri
 Pentru n = 3: (1,1,2), (1,1,3), (1,2,2), (1,2,3), (1,3,2), (1,3,3), (2,1,3),(2,2,3),(2,3,3) -> 9 moduri

 ___________________________________________
 Si apropo de complexitate: e O(N) spatiu si O(N) memorie. Ar fi fost O(1) daca  ar fi fost pur si simplu o formula (de genul n^2+5-17*32)... sper ca nu am rascolit prea tare trecutul  :mrgreen: Parerea mea...

Ce observatie matematica trebuie ca sa reduc de la N^3 la N^2 complexitatea acestei probleme? Nu prea ma prind... :-k

imi poate da cineva linku catre sol de pe campion ca am tot cautat prin toata arhiva si nu am gasit nimik..... :(  pls

Linkul este http://www.liis.ro/~campion/problems.php?mode=view_round&group_number=2&year=2004&round_number=5 ( gaseai arhiva din 2004, runda a 5-a, grupa mijlocie...)

La campion gasesti din cate tin eu minte o solutie de complexitate O(n^3)... ar fi de preferat sa se incerce gasirea unei solutii in n^2 .. nu doar crearea unor constante folosind programul in n^3 de pe siteul campion. ( aici fiind limitele un pic mai mari )

Imi zice shi mie cineva cum de iau doar 40 puncte cu urmatoarul program care foloseste o recurenta:



e ciudat mai ales ca eu nu vad ce are de nu merge.... pare perfect ----> Doar ca ia 40 puncte cu TLE pe restul !!!!!!!!  ](*,)   Exista ceva mai rapid ca O(n^3)  ca eu nu vad?????? :?:

1. Daca nu vezi, nu inseamna ca nu exista
2. Puteai sa vezi cu un calcul simplu sau cu un program oarecare ca un algoritm O(n^3) nu se incadreaza in 1 secunda cu n=1000 mai pe nici un procesor
3. Nu are rost sa postezi cod, citeste Regulamentul
4. Daca citeai ce s-a mai scris mai sus , vedeai ca exista un algoritm O(n^2)
5. Relaxeaza-te si foloseste moderat "!" si "?", cat si smiley-urile

 :ok:

1. Am inteles
  2. Nu am citit mai sus, deoarece cum nu mi-a mers problema am intrat si am postat
  3. Stiu k e o tampenie ca nu am facut calculul ca nu merge O(n^3)
  4. O sa incerc sa nu mai folosesc !

Ah... shi uitasem sunt agitat de la cola (daia pun multe ! ? shi smile-uri)

[Editat de bogdan2412: Nu mai postati de doua ori consecutiv, editati-va posturile anterioare]

Poate sa-mi spuna si mie cineva cat da pentru n=17 si n=28? Multumesc mult.

473176 si 732667

Imi spune si mie cineva unde gasesc solutia de pe campion? ca imi apare arhiva goala. sau daca nu sa imi spuna si mie cineva cum as gasi o solutie de O(n^3)? O sa gasesc eu apoi calculele matematice necesare sa o fac in O(n^2).... :D

Imi puteti da un hint cum sa fac dinamica, ca am incercat sa tin o matrice A[ i ][ j ] = numarul de posibilitati de a pune elementul i pe pozitia j, insa recurenta nu prea imi iese si vreau sa stiu daca asta este calea cea buna :)

nivan,uite de ce iei 40 de puncte
Test Timp executie Memorie folosita Mesaj Punctaj/test
1 0ms 8kb Corect! 10
2 20ms 540kb Corect! 10
3 0ms 12kb Corect! 10
4 0ms 12kb Corect! 10
5 1052ms 2256kb Time limit exceeded. 0
6 1052ms 2720kb Time limit exceeded. 0
7 1052ms 2540kb Time limit exceeded. 0
8 1052ms 2848kb Time limit exceeded. 0
9 1052ms 3788kb Time limit exceeded. 0
10 1052ms 3120kb Time limit exceeded. 0
Punctaj total 40
sper ca nu te superi,am trimis sursa ta :)

Acel post era de acum 4 ani. Uita-te si tu mai atent inainte sa postezi ceva. Si incearca de acuma sa rezolvi singur problemele, nu are sens sa trimiti sursele altora. Nu castigi nimic daca ai mai multe puncte in arhiva.

se poate ca o metoda backtracking sa se incadreze in timp?
//probabil ca nu!ca deja de la n=30 moare programul

rezolvarea in O(N^2) consta in a declara un vector s cu semnificatia : s[ i ] = nr de siruri de lungime i cu elemente din multimea {1,..,i} ??

Later edit: Imi poate da careva un indiciu pt rezolvarea in O(n^2) ?

eu am rezolvat problema folosind o matrice opt(i,j) = nr de siruri 2-3 monotone de lungime i cu valori din multimea {1,2,...,j}, complexitate O(n^3). M-am mai gandit si in felul urmator: opt(i,j) = nr de siruri 2-3 monotone de lungime i cu ultimul element j ...
oare asa pot ajunge la O(n^2) ?

Editat de moderator : Nu mai posta de mai multe ori consecutiv. Editeaza-ti posturile anterioare.

O idee pe care am oferit-o o data ar fi o dinamicain 3 dimensiuni d[ i ][j][k] pentru siruri de lungime i cu valori intre 1 si j si cu ultimele elemente avand o ordine k. Iti las tie problema gasirii numarului de elemente pe care trebuie sa le considiri si recurenta dinamicii. Rezolvarea asta ar fi cam O(N^2) cu o constanta maricica dar accectabila.

Salut,

Ma tot chinui la problema asta si nu ii dau de cap. Insa am cateva idei, cel putin legat de partea de "organizare".

Ok, in principal ma gandeam sa tin o matrice S, unde S[ i ][ j ] - numarul de siruri de dimensiune i cu elemente de la 1 .. j.

Acum legat de partea de recurenta - o pot lua in 2 directii:
1. sa incerc sa calculez S[ i+1 ][ j ] - practic sa "redistribui" numerele de la 1 la j tinand cont ca am o pozitie in plus
  - de la o valoare a lui i incolo, pt fiecare j, i >> j (sa zicem), S[ i ][ j ] = 0, intrucat nu exista suficiente numere care sa satisfaca relatia de monotonie
2. sa incerc sa calculez S[ i ][ j+1 ] - practic sa mai adaug o valoare in lista de valori cu care pot construi sirurile

As incerca sa ma gandesc mai departe pe varianta 2, insa nu reusesc sa "controlez" in niciun fel valorile retinute pana in punctul S[ i ][ j ], astfel incat sa pot construi recurenta fara sa adun chestii de 2 ori, sa omit cazuri, etc.

M-ar ajuta orice fel de sugestie legata de ce informatie in plus ar mai trebui sa contina matricea de programare dinamica, ce ar mai fi relevant. De asemenea, orice problema aseamanatoare, sau principiu de programare dinamica, care sa imi dea idei si din care sa pot invata. M-am blocat la problema asta acum ceva timp, acum am reluat-o si sunt in acelasi punct.

Multumesc si o zi faina!