214 Subsiruri

[ditzone]

Aici puteţi discuta despre problema Subsiruri.

[•lucicanu]

Am si eu o intrebare intrebatoare: ce au testele 8 si 10?
Programul merge perfect pe restul testelor, iar la 8 si 10 primesc "incorect sau fisier de iesire lipsa". Sunt convins ca algoritmul e corect, toate variabilele sunt long int, vectorii respecta restrictiile etc. Nu stiu ce sa-i fac...
Daca poate cineva sa ma ajute as fi foarte recunoscator...

[•bogdan2412]

Ai uitat sa faci modulo 9901 pe parcursul programului probabil... Nu ti s-a mai raspuns odata pe forumu vechi?

[nivan]

 Hmm... cum %&*$%%&^$ :
TEST 1   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 2   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 3   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 4   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 5   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 6   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 7   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 8   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 9   ...[0.01s]...   RUN ERROR - Invalid memory reference
TEST 10   ...[0.01s]...   RUN ERROR - Invalid memory reference
 

 Cand eu o compilez pe linux si merge!  Destul de ciudat.

[u-92]

o compilezi.. dar de rulat? baga mai multe teste si daca totul e ok si persista mesajul pune undeva codul sa vedem.. mi s-a mai intamplat si mie sa am ceva constante declarate la inceputul programului si sa nu compileze din cauza asta pe infoarena

[•cos_min]

Cod:

Acest numar se va afisa modulo 9901.

Este restrictie in enuntul pb, nu este o optimizare.

[•ciprianf]

Sunt incepator si.......nu prea stiu cum sa fac cu problema asta,adica nu stiu cum sa determin subsecventele alea....imi poate explica si mie cineva daca este amabil?

Later Edit: Am aflat ca trebuia facuta cu dinamica, am invatat dinamica, si ma rog, iau pe program doar 80 de pcte , WA la testele 8 si 10.....am vazut ca au mai fost discutii privind aceste 2 teste...este vre-un caz special ?Am pus si %9901

Later later edit: am rezolvat-o pana la urma....eu puneam initial doar la sfarsit %9901, si am corectat punanad peste tot %9901 cand adunam.... erau mai mult de 2 miliarde de posibilitati la un test? ca altfel daca nu iesea din long nu-mi explic de ce ar fi dat WA

[•DITzoneC]

Imagineaza-ti un test de genul

Cod:

2 1 4 3 6 5 ... n n-1

Rezultatul pentru acest test este 2^n/2 care depaseste cu mult 2 miliarde.

[•Robytzza]

se pot repeta 2 subsiruri??    ca prima oara practic cautam toate posibilitatiile si luam 80 cu 2 TLE si acuma nu le mai formez .. fac ceva in genu c[ i ] = c[j]  daca b[ i ]<b[j]+1 si c[ i ]++ daca sunt egale iar numarul de subsiruri maxime le gasesc adunand la fiecare b[ i ] maxim c[ i ] la nr ce e gresit?   

Editat de admin: Ai grija cand pui chestii de genu [ i ] sa lasi spatii intre i si acolade, deoarce altfel iti face textul italic.

oky ms

[•DITzoneC]

Acolo nu trebuie sa faci c[ i ] ++, trebuie sa ai c[ i ] += c[ j ](in cazul in care sunt egale) deoarece poti sa iei toate subsirurile care se termina in j nu doar unu din ele.

[•Robytzza]

   uneori ma uimesc cu ce greseli pot sa fac .ms 

[•andrici_cezar]

nu inteleg deci incerc sa fac problema dar nu imi gaseste toate subsirurile imi gaseste doar trei cum ar trebuii sa le iau pe toate?

[•pauldb]

Foloseste cu incredere punctuatia. E bine sa scrii corect, daca vrei sa fii ajutat.

Daca inteleg eu bine ce intrebi, pentru a rezolva problema ai nevoie de programare dinamica.

[•andrici_cezar]

bine! o sa o caut si o sa invat acesta cautare dinamica! ,  dar unde o gasesc?

[•pauldb]

Programare dinamica, nu cautare dinamica. Din cate am auzit, un inceput bun ar fi cartea doamnei Cerchez despre programare dinamica. Eu personal am invatat rezolvand cat mai multe probleme de acest gen.

Uite un tutorial care s-ar putea sa-ti fie de folos (sau macar sa te lamuresti putin cum sta treaba).

[•andrici_cezar]

Dami unul in romana ca eu nu prea inteleg engleza

[•cristiprg]

numarul de subsiruri cum se afla ? un hint, ceva, pls

[•DraStiK]

numarul de subsiruri cum se afla ? un hint, ceva, pls

e tot programare dinamica:
tii un vector v[ i ]=numarul de subsiruri de lungime maxima pana la pozitia i

daca nu iti dai seama de relatie dami un pm

[•ssergiuss]

Pic testele 8 si 9. Rezolv problema cu dinamica, dar nu'mi dau seama ce gresesc. As fii recunoscator celui ce mi'ar da ceva sugestii .

[•ctlin04]

dar care e relatia de recurenta pentru v?

[•maritim]

Presupunem ca Best[ i ] = 7 si descoperi ca Best[ i ] = 7 se poate forma de pe doua pozitii anterioare cu Best[ i ] = 6, dar acestea doua la randul lor se pot forma din 2 si 3 posibilitati si tot asa in continuare prin recurenta.

Multa bafta !

[•ctlin04]

ms pentru hint (Lambru Andrei Cristian) aveam cam aceeasi idee numai ca nu mi se primea s-o implimentez, acum insa am mai analizat si pina la urma am luat 100 

PS: pentru ce care au probleme cu testul 8 si 10, puneti peste tot unde lucrati cu vectorul in care tineti numarul de subsiruri mod 9901 si totul se primeste pe 100p...

[•ion_caliman]

Spuneti-mi va rog cineva ce nu fac corect in algoritmul meu, primesc WA si nu gasesc greseala

Cod:

#include <fstream>
using namespace std;
ifstream f("subsiruri.in");
ofstream g("subsiruri.out");
int v[2000],n,i,j,best[2000],nr[2000],lmax,num;

int main()
{
    f >> n;
    for (i=1; i<=n; i++) f >> v[i];
    for (i=1; i<=n; i++)
    {
        best[i]=1;
        nr[i]=1;
        for (j=1; j<i; j++)
        if (v[j]<v[i] && best[j]+1>best[i])
        {
            best[i]=best[j]+1;
            if (best[i]>lmax) lmax=best[i];
            nr[i]=nr[j];
        } else if (v[j]<v[i] && best[j]+1==best[i]) nr[i]=(nr[i]+nr[j])%9901;
    }
    for (i=1; i<=n; i++) if (best[i]==lmax) num=(num+nr[i])%9901;
    g << lmax << '\n' << num;
}

Pe testele mele mergi bine

[•PlayLikeNeverB4]

Chiar daca ai luat 100, ar fi bine sa initializezi lmax cu 1, in caz ca lungimea maxima e 1.

[•VisuianMihai]

nu inteleg... cum imi dau seama daca trebuie %9901? dece tocmai 9901? care e logica?