387 Distincte

[•DITzoneC]

Aici puteţi discuta despre problema Distincte.

[•Dorin]

Am citit solutia la problema, si nu prea reusesc sa imi dau seama cum se poate face suma elementelor dintr-un dreptunghi in timp logaritmic ? Imi puteti da vreo idee va rog ?

[...] De fapt nu imi dadeam seama cum pot sa calculez suma valorilor atribuite fiecarui punct  ... In range query 2D trebuie sa afli doar numarul lor ... dar cred ca m-am prins ... tks

[•wefgef]

Solutia de 100 de puncte foloseste un simplu arbore de intervale sau un arbore indexat binar. Daca vrei sa afli mai multe despre range query 2D poti consulta articolul de aici.

[•Dorin]

Am 2 rezolvari cu acelasi rationament una implementata cu arbori de intervale, si una cu arbori indexati binar si la niciuna nu iau mai mult de 25 de P (Wrong Answer).
Rationamentul meu este urmatorul :
Cu un arbore determin suma primelor i numere. Cu un altul determin suma primelor x numere care au cel mai apropiat element egal cu el din partea stanga pe o pozitie mai mica sau egala cu x ( in cazul in care nu exista un astfel de element am pozitia 0 ) ;
Ordonez query-urile dupa capatul dreapta;

Cod:

for(i = n; i; i--)  
{
     cat timp am capat dreapta egal cu i 
     {
           calculez suma elementelor care au cel mai apropiat element, din partea stanga egal cu el, pe o pozitie mai mica sau egala cu capatul stanga din care scad suma elementelor pana la capatul stanga
     }
     elimin din al 2lea arbore valoarea reprezentanta pentru pozitia i 
}

Banuiesc ca rationamentul meu este gresit, dar nu reusesc sa imi dau seama care parte ?
Daca aveti careva vreo idee ... help please

[•gabitzish1]

Nu reusesc sa trec de 35.. iau doar primele 7 teste + WA. Am vazut ca au fost mai multi in situatia asta. Cum ati trecut peste treaba asta?

[•reking]

Cod:

int calculeaza (int x,int y)
{
    int i,sum=0;
    bool h[NMax]={0};
    for (i=x;i<=y;i++)
    {
        if (h[v[i]]) i++;
        else
        {
            sum=sum+v[i];
            h[v[i]]=1;
        }
    }
    return sum;
}

Ce este gresit la acest subprogram care calculeaza suma elementelor distincte intre pozitiile x si y ([x;y])
in v[] retin elementele vectorului si h[] e un fel de vector caracteristic (am incercat sa fac un fel de hash...nu prea ma pricep)

[•klamathix]

Invata sa faci debug .

[•SebiSebi]

Sari peste niste elemente datorita conditiilor. Pune

Cod:

if(h[v[i]]==0) 
       sum=sum+v[i];
h[v[i]]=1;       

Oricum problema se rezolva folosind arbori de intervale.

Si apoi ar trebui sa faci ce spune Mihai.

[•reking]

Mersi. ^_^
Mi-a mers...ce-i drept mi-a mers doar pe cateva teste, pe restul TML...momentan o las asa pentru ca nu stiu 'arbori de intervale' .