018 Siruri 2-3-monotone

[•domino]

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  

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

[•cristy]

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

[•filipb]

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

[•vladcyb1]

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

[•Stilgar]

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

[•filipb]

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

[ditzone]

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 )

[nivan]

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

Cod:

#include <stdio.h>

long i,j,k,n,mod=1000000,f[1001][1001];

int main()
{
 FILE *fil=fopen("sir23.in","r");
 fscanf(fil,"%ld",&n);
 fclose(fil);

 for (i=1;i<=n;i++)
    {
     f[i][1]=i;
     f[i][2]=i*i;
     f[i][2*i]=1;
    }
 f[1][2]=1;
 f[2][3]=2;
 for (i=3;i<=n;i++)
    for (j=3;j<2*i;j++)
    for (k=1;k<i;k++)
       f[i][j]=(f[i][j]+f[i-k][j-1]+k*f[i-k][j-2]) % mod;

 FILE *g=fopen("sir23.out","w");
 fprintf(g,"%ld",f[n][n]);
 fclose(g);

 return 0;
}

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

[•domino]

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

 

[nivan]

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]

[•pauldb]

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

[•fireatmyself]

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

473176 si 732667

[•ghitza_2000]

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

[•Mishu91]

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

[•vladtarniceru]

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

[•devilkind]

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.

[•Cmaster]

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

[•cr1st18]

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.

[•freak93]

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.

[•dodgerblue]

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!