1387 Split

[•eudanip]

Aici puteti discuta despre problema Split.

Multumin lui Olariu Ciprian pentru adaugarea problemei.

[•Dddarius95]

salut. am si eu o problema aici...nu stiu unde gresesc la calcularea lui k....fixez pe j...si caut  in 1..j-2 pe i si in j+2...n-2 pe k....am luat testele de la oni....si pe alea si pe cele de pe infoarena tot 50p iau. ideea e ca pe toate testele de la oni  imi calculeaza bine i si j . k-ul e gresit pe 5 teste(si din astea 5 pe 3 da si alta suma)....da un k mai mare cu o unitate decat e in out-ul din evaluator....
secventa de cod care mi.l calculeaza pe k este...

Cod:

        int Dreapta=0;
        int K=-1;
        minim=min(a[j+1],a[j+2]);
        maxim=max(a[j+1],a[j+2]);
        for(int k=j+3;k<=n-2;k++)
        {
            int aux=maxim-minim+MaxD[k+1]-minD[k+1];
            if(aux>Dreapta){Dreapta=aux;K=k;}
            if(a[k]<minim)minim=a[k];
            if(a[k]>maxim)maxim=a[k];
        }

k-ul cautat il salvez in variabila K
si apoi mai aveam sa reactualizez solutia...
* minD=cel mai mic element care se  afla la dreapta pozitiei i
* MaxD=cel mai mare element =//=

am dat de curiozitate sa faca K=k-1; si atunci iau 20p, dar pe alte teste....
sursa se gaseste aici http://www.infoarena.ro/job_detail/982548
unde gresesc?

[•vendetta]

Prima greseala : pierzi cazul cand K = j + 2; A 2-a : minimul  si maximul sunt doar pe intervalul j+1..k-1 (trebuie pe j+1..k);

Cod:

int Dreapta=0;
        int K=-1;
        minim=min(a[j+1],a[j+2]);
        maxim=max(a[j+1],a[j+2]);
        for(int k=j+2;k<=n-2;k++)
        {
            if(a[k]<minim)minim=a[k];
            if(a[k]>maxim)maxim=a[k];

            int aux=maxim-minim+MaxD[k+1]-minD[k+1];
            if(aux>Dreapta){Dreapta=aux;K=k;}
        }

[•Dddarius95]

ms. s-a rezolvat

[•alexalghisi]

Buna . Am si eu o solutie de complexitate O ( N x N ) la aceasta problema , ca si solutia oficiala , doar ca a mea nu intra in timp  . Atata timp cat numarul de operatii este acelasi , nu inteleg de ce nu ar trebui sa intre ambele la fel de lejer .

Solutia aeste aici : http://www.infoarena.ro/job_detail/1046306