344 Bcrc

[•bogdan2412]

Aici puteţi discuta despre problema Bcrc.

[•devilkind]

cam ce complexitate ar trebui la problema asta?? in afara de n*t nu prea am multe idei

[•Marius]

O(M*N) cu deque.

[•stocarul]

Am încercat și eu o rezolvare în O(M²).
Intâi am adăugat cutia virtuală cu numărul de ordine 0, ce se află în încăperea 1, cu timpul = 0, iar numărul de bomboane = 0.
DP[ i ]=numărul maxim de bomboane ce se pot obține din primele i cutii, luând din cutia  i (dacă se poate lua din cutia i)
Recurența ar fi:
DP[ i ]=max(DP[ j ] + B[ i ]),  0 <= j < i și distanța dintre cutiile i și j (încăperile lor) e mai mică decât diferența de timp dintre cele două cutii.
Soluți ar fi max(DP[ i ]), 0 <= i <= M.

E ceva greșit în gândirea asta?

Le: Am găsit greșeala până la urmă. Ideea era bună, dar fraieru de mine nu verifica mai întâi dacă în cutia pe care o continui am putut ajunge.

[•vendetta]

Salut!
Am facut o rezolvare M*N cu deque dar iau doar 40 de puncte;(pe restul iau tle)
Din cele citite mai sus aceasta ar fi complexitatea oficiala; si totusi care ar fi problema ?

[•Impaler_009]

Am murit de gat cu problema asta..  

Am stat doua zile sa optimizez solutia oficiala cu deque.. dar orice faceam nu-mi iesea pe testul 5. Desi am vazut in surse mai vechi de 100 ca inregistra si cu 2000-4000 ms (n-ar trebui sa iasa din timp?). Pe a mea in schimb am dus-o pana la 600 ms pe testul 4(al doilea cel mai mare) dar pe 5 tot nu-mi iesea.

Pana la urma, cand chiar nu mai mergea nimic, mi-a venit ideea sa combin rezolvarea asta cu o idee ce o implementasem eu initial: cu un vector bst sa inregistrez cea mai buna valoare care se poate obtine o data cu luarea cutiei de bomboane i. Considerand cutia i, aveam nevoie de maximul bst[j] cu j<i accesibil din acest punct. Dar cutiile aparute cu n/2 timp in urma erau automat accesibile (distanta maxima intre 2 camere e n/2), deci din acelea aveam nevoie doar de maxim. Pe restul, aparute relativ devreme, trebuia sa le pastrez intr-o coada, deoarece nu erau neaparat accesibile (distanta dintre cutia i si acestea trebuie sa fie mai mica decat intervalul de timp) si trebuiau verificate.  O solutie care, desi, in best case face O(m*n/2), tinde la O(m^2) in worst case (atunci cand toate cutiile apar intr-un interval de timp sub n/2)

Solutia nu intra pe 4 teste, dar culmea, pe testul 5 scotea 40 ms!! Am dedus deci ca testul acela probabil se caracterizeaza prin intervale de timp mari intre cutiile de bomboane ceea ce face deque-ul mai greoi de construit (ori asta, ori chiar sunt batut in cap si imi scapa ceva). Asadar, am combinat rezolvarile intr-o singura sursa, si am facut un fel de "cautare binara" cu evaluatorul ca sa vad ce conditie sa pun sa intre numai testul 5 pe rezolvarea a doua (lucru de care nu prea sunt mandru) si am luat suta.

Cod:

Solutia cu Deque:

deque <int> D;

int s,l,n,m;
bool use;
int t,prevt,c,b,bst[2050][2];  //bst=numarul maxim de bomboane colectate fiind in camera i la momentul de fata ; ar trebui sa fie bst[2050][50001] dar nu avem nevoie decat de starea curenta si cea din urma

void deque_in (int i)
{
    while ( !D.empty () && bst[use] >= bst[D.back()][use]) D.pop_back ();
    D.push_back (i);
}

void deque_out (int i)
{
    if (i==D.front ()) D.pop_front ();
}

int main ()
{
    fin>>n>>m;
    for (int j=0; j<=1; j++) for (int i=1; i<=n; i++) bst[j]=-1;  //-1 inseamna ca nu am ajuns deocamdata in punctul i

    bst[1][0]=0; bst[1][1]=0;
    int MAXV=0;

    for (int j=1; j<=m; j++)
    {
         fin>>t>>c>>b;
         int T = t - prevt;

         if (T==0)       // caz particular pentru T==0 pt rapiditate
         {
            bst[c][use] += b;
            prevt=t;
            if (bst[c][use]>MAXV) MAXV=bst[c][use];
            continue;
         }

         if (T>=n/2)      //caz particular pentru T>=n/2 pt rapiditate
         {
             for (int i=1; i<=n; i++) bst[use]=MAXV;
             bst[c][use] += b;
             prevt=t;
             MAXV=bst[c][use];
             continue;
         }

D.clear ();                                     //golesc deck-ul dupa fiecare pas
         for (int i=n-2*T+1; i<=n; i++)  deque_in (i);   //indicii deque-ului sunt:
         int i=1;                                                //i-elementul ce trebuie adaugat
         int s=n-T+1;                                            //s-elementul curent (central al deque-ului pt care facem solutia)
         int l=n-2*T;                                             //l- elementul ce trebuie scos
        
         for (i=1; i<=n; i++)
         {
             deque_in (i);
             deque_out (l);
             bst[1-use] = bst[D.front()][use];
             s++; l++;
             if (s>n) s=1;
             if (l>n) l=1;
         }
         
         if (bst[c][1-use]!=-1)  bst[c][1-use] += b;
         use=1-use;
         prevt=t;
         if (bst[c][use]>MAXV) MAXV=bst[c][use];
    }
    fout<<MAXV;
}

EDITARE: Nu stiu de ce mi-a venit deabia acum ideea sa fac deque-ul fara STL. Problema era ca functia D.clear () ia timp O(N) in timp ce implementat de "mana", trebuie sa setezi decat indicii start=1; last=0; ca sa resetezi deque-ul.. Asa am luat suta frumos.. Mi se trage de la faptul ca mi-am autoimpus in ultima vreme sa folosesc STL-ul ca sa-l invat. Evident, nu e intotdeauna bine.

Editat de moderator: Nu posta consecutiv, editeaza mesajele anterioare. Foloseste tag-ul [ code ] [/ code ] cand postezi cod.