507 Interclasare

[•DITzoneC]

Aici puteţi discuta despre problema Interclasare.

[•DITzoneC]

S-a actualizat veriful problemei si s-au reevaluat solutiile trimise.

[•cosgb]

E ceva special la interclasare? ca tot iau 0 si nu inteleg de ce  . La cel mai lung subsir crescator nu cred k am gresit nimic din moment ce am 100 la arhiva educationala pe el(aici am modificat pt <=, pt k la arhiva educationala e strict <). help 

[•gabor_oliviu1991]

incearca sa vezi daca iti merge pentru exemplul asta:

Cod:

4
5 1 1 1
5
1 1 1 1 1

nici eu nu prea imi dau seama cum sa fac, si dupa zicala: "prietenii la nevoie se cunosc", vreo idee?

[•cosgb]

Pt testul ala imi da
8
1 1 1 1 1 5 1 1 1
Eu unul fac interclasarea celor doua siruri, sa zicem N si M,  punand minimul dintre N[ i ] si M[j] in vectorul de interclasare. Si apoi algoritmul pt determinarea lungimii celui mai lung subsir crescator  . E vreo hiba in ideea mea? K toate testele pe care mi le-am dat mi-au dat.   

[editat de moderator] cand folosesti vectori cu indicele i lasa spatii -> V[ i ], altfel forumul va interpreta ca urmeaza text italic.

[•gabor_oliviu1991]

Lungimea e buna, dar sirul nu. Ar trebui sa dea

Cod:

8
5 1 1 1 1 1 1 1 1

Din cate am inteles eu. Probabil trebuie ceva interclasare mai speciala...

[•devilkind]

Uite testul pe care pica:

Cod:

4
1 10000 3 4
2
5 6

tie iti da interclasarea 1 5 6 10000 3 4 cu cmlsc 4 in timp ce interclasarea 1 10000 3 4 5 6 are cmlsc 5.

[•cosgb]

Ms. Acum am inteles  . Nu ma gandisem la cazul ala. Dar iau 40 pt k imi da fiecare sir interclasat gresit  . Se accepta orice sir interclasat care respecta conditiile problemei sau numai cele obtinute dupa ideea din exemplu?

[•devilkind]

Se accepta orice sir.

[•cosgb]

Ok. Ms. Uitasem sa pun 1 conditie intr-un while so mai mergea cativa pasi in plus si daia nu-mi dadea sirul . Ms pt ajutor

[•dornescuvlad]

Salut! E ceva neinregula cu evaluatorul la problema aceasta?
Am rezolvat primul subpunct pentru punctaj partial (40 %) in felul urmator:
Normalizez valorile din cei doi vectori, iar folosind arbori indexati binar, determin subsirul maximal crescator pentru fiecare dintre ei.
In cele din urma, afisez suma lungimilor celor doua subsiruri maximale crescatoare.E aceasta abordare gresita?
Am dat in jur de 10 exemple cu n,m <= 2500 si vad ca nu pica pe niciunul.  

L.E : Abordarea era buna, uitasem eu sa setez AIB`ul la 0, dupa ce il foloseam prima oara

[•ion_caliman]

Poate sa-mi zica cineva ce nu fac bine la interclasare ?

[•ctlin04]

poate sa ma ajute cineva la pasul "cum se face inerclasarea corecta a sirurilor?", pls macar un hint

[•S7012MY]

Din cate imi amintesc e ca la interclasarea a 2 vectori sortati

[•ctlin04]

ms, Trimbitas Petru, o sa incerc

[•gapdan]

Eu interclasez asa:

Cod:

 i=1;
    j=1;
    int k=0;
    while (i<=n && j<=m)
    {
        if (a[i]<b[j]) {v[++k]=a[i],++i;}
            else {v[++k]=b[j],++j;}
    }
    if (i<=n)
    {
        while (i<=n)
            {
                v[++k]=a[i];
                ++i;
            }
    }
    else if (j<=m)
    {
        while (j<=m)
        {
            v[++k]=b[j];
            ++j;
        }
    }

poate sa-mi spuna cineva ce gresesc? pentru punctul 1 am incercat sa fac SCM pe fiecare vector si apoi sa fac suma si iau tot 0, la fel pe sirul asta interclasat...aveti idee de ce?

[•Archazey]

Salut,
Prima data luasem doar 40 de puncte afisand lungimea maxima,dupa am facut si algoritmul de determinare a unei interclasari bune,dar degeaba,imi afiseaza mesajul "Nu exista subsir crescator de lungime maxima!   ",am luat si exemplele din comentarii,si imi afiseaza bine.
Eu am pastrat in doi vectori SCM pentru fiecare sir,dupa faceam interclasarea astfel incat in sirul obtinut sa imi apara elementele din subsirul maximal total in ordine.
Am si o sursa aici,este vorba de functia Interclasare(),daca cineva ma poate ajuta....va rog nu ezitati.Macar un test de mi-ar da....
http://ideone.com/ThZ3lv

[•mihaimusat]

nu imi dau seama de ce primesc KBS 11 in conditiile in care limita de memorie este de 5120 kb,iar sursa mea are 2 kb.Ce are evaluatorul ? 

[•madalomar]

nu inteleg de ce imi spune : Nu exista subsir crescator de lungime maxima!    imi da corect pe orice test incerc, si, din curiozitate, am incercat si sa determin scmax pe vectorul interclasat de lungime m+n, si imi da corect. aveti idei?

[•klamathix]

La ce te referi când zici că îți dă corect dacă afișezi scmax pe vectorul interclasat? Local pe testele tale sau pe infoarena? Mie îmi pare ok evaluatorul. Încearcă să testezi în sursele pe care le trimiți că e corect șirul. Dacă pare suspect, scrie-mi mesaj privat și rezolvăm dacă e vreo problemă la noi.

[•Barbumatei]

Draga evaluator,

Testele acestei probleme nu suporta fiecare optiune de rezolvare. Eu am luat 100 de punte pe problema scmax care se refera la cel mai lung subsir ordonat(in O(n log n)), dar evaluatorul imi spune ca"Sirul nu e obtinut prin interclasare!", desi interclasez prin interclasare. Puntacjul luat de mine este de 94. Mie mi se pare ca testele trebuie imbunatatite. Va rog remediati aceasta problema  

[•Barbumatei]

Puncte*

[•Djok]

Folosești tablouri de 10000 elemente, cu indexare de la 1. Asta poate fi o problemă. Mai adaugă un +5 la fiecare tablou

[•Barbumatei]

Multumesc. Esti un geniu. Pentru prima ora indexez si eu de la 1  M-ai salvat ca o zi m-am chinuit la problema! Multumesc inca o data enorm!

[•vladrochian]

Draga evaluator,

Testele acestei probleme nu suporta fiecare optiune de rezolvare. Eu am luat 100 de punte pe problema scmax care se refera la cel mai lung subsir ordonat(in O(n log n)), dar evaluatorul imi spune ca"Sirul nu e obtinut prin interclasare!", desi interclasez prin interclasare. Puntacjul luat de mine este de 94. Mie mi se pare ca testele trebuie imbunatatite. Va rog remediati aceasta problema  

Puțin cam arogant tu așa. Ar fi drăguț dacă în general atunci când nu îți merge ceva, în loc să dai vina pe teste și evaluator, prima reacție ar fi să îți pui problema că e ceva greșit cu soluția ta și să verifici mai bine. Spun doar că mentalitatea asta ajută mai mult.