Imprimă pagina - 387 Distincte

Titlul: 387 Distincte
Scris de: Adrian Diaconu din Martie 25, 2007, 13:27:08

Aici puteţi discuta despre problema Distincte (http://infoarena.ro/problema/distincte).

Titlul: Răspuns: 387 Distincte
Scris de: Oltean Dorin din Aprilie 11, 2008, 18:49:39

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 :-k ? Imi puteti da vreo idee va rog ?

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

Titlul: Răspuns: 387 Distincte
Scris de: Andrei Grigorean din Aprilie 11, 2008, 22:07:04

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 (http://infoarena.ro/arbori-de-intervale).

Titlul: Răspuns: 387 Distincte
Scris de: Oltean Dorin din Aprilie 12, 2008, 12:40:11

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 :sad: ?
Daca aveti careva vreo idee ... help please

Titlul: Răspuns: 387 Distincte
Scris de: Gabriel Bitis din Decembrie 29, 2008, 18:09:13

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?

Titlul: Răspuns: 387 Distincte
Scris de: Cretu Bogdan din Iunie 27, 2013, 17:42:48

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) :D

Titlul: Răspuns: 387 Distincte
Scris de: Mihai Calancea din Iunie 27, 2013, 17:51:32

Invata sa faci debug :).

Titlul: Răspuns: 387 Distincte
Scris de: Pirtoaca George Sebastian din Iunie 27, 2013, 17:53:30

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.

Titlul: Răspuns: 387 Distincte
Scris de: Cretu Bogdan din Iunie 27, 2013, 18:15:58

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' .

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Martie 25, 2007, 13:27:08