Imprimă pagina - 1387 Split

Titlul: 1387 Split
Scris de: Eugenie Daniel Posdarascu din Mai 04, 2013, 09:57:13

Aici puteti discuta despre problema Split (http://infoarena.ro/problema/split).

Multumin lui Olariu Ciprian (http://infoarena.ro/utilizator/scipianus) pentru adaugarea problemei.

Titlul: Răspuns: 1387 Split
Scris de: Darius-Florentin Neatu din August 09, 2013, 19:42:15

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 (http://www.infoarena.ro/job_detail/982548)
unde gresesc?:D

Titlul: Răspuns: 1387 Split
Scris de: Salajan Razvan din August 10, 2013, 14:14:06

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;}
        }

Titlul: Răspuns: 1387 Split
Scris de: Darius-Florentin Neatu din August 10, 2013, 14:39:48

ms. s-a rezolvat :D

Titlul: Răspuns: 1387 Split
Scris de: Alghisi Alessandro Paolo din Decembrie 02, 2013, 20:26:46

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Eugenie Daniel Posdarascu din Mai 04, 2013, 09:57:13