Page 1 of 1

Problema cu intervale

Posted: 24 Apr 2013, 09:33
by manacher1
Salut!
Am gasit intr-o carte mai veche de informatica o problema pe care nu reusesc sa o fac. Problema e cam asa: ti se da un sir de numere naturale si query-uri de 2 tipuri: ori inlocuiesti elementul de vector de la pozitia x cu y ori pentru un interval [x,y] trebuie sa gasesti numarul(ti se garanteaza ca exista) care apare in acel interval o singura data (stiind ca toate celelate numere apar in interval de un numar par de ori si el este singurul care apare 1 data). Singura mea idee a fost sa fac primul query in O(1) doar facand actualizarea in vector si al la al doilea facand suma xor din acel interval in O(n) dar solutia mea nu este optima. Poate cineva sa imi dea cateva idea despre cum se face o problema ca asta, sau macar ce structura de date ar trebui sa folosesc?

Re: Problema cu intervale

Posted: 24 Apr 2013, 10:58
by bu7ch3r
De ce solutia ta nu este optima?
De ce crezi ca ai avea nevoie si de alta structura de date?

Re: Problema cu intervale

Posted: 26 Apr 2013, 13:46
by Sylvie Woo
Este o solutie cu O(log N) pentru ambele operatii.

Spoiler alert!
Cauta arbori de intervale... Si: ideea cu XOR-ul e buna, doar ca se aplica putin diferit in varianta asta.

Re: Problema cu intervale

Posted: 29 Apr 2013, 10:52
by Sylvie Woo
@manacher1: Ai gasit, te descurci? Ai nevoie de indicatii?

Re: Problema cu intervale

Posted: 29 Apr 2013, 12:24
by bu7ch3r
@Sylvie Woo
Eu tot nu imi dau seama de ce cu un arbore de intervale rezolvi problema mai optim?
Ma gandesc ca pentru a popula acel arbore de intervale trebuie sa rezolvi alta problema: Gasirea tuturor intervalelor cu un numar care apare doar o data.
Problema lui e mai simpla, are doar un interval. MOMENTAN :)

Sunt de acord cu arborele de intervale, dar numai in cazul in care viitoarea aplicatie va servi multiple cereri.

Acum cu XOR e destul de simplu(suma = suma ^ numar...ghici ciuperca ce-i), singura problema e ca s-ar putea sa nu-si dea seama daca in intervalul ala 0 apare odata; dar de data asta ne salveaza enuntul problemei.(asta avand in considerarea ca initializeaza suma cu 0)

Re: Problema cu intervale

Posted: 29 Apr 2013, 12:47
by Sylvie Woo
Pai stai ca nu ai inteles tu ce se cere: trebuie sa asiguri doua tipuri de query-uri: modificare si interogare. Nu zice nimeni ca doar pentru un singur interval si doar un query.
Cand se da o astfel de problema, te astepti la (posibil) miliarde de query-uri. Atat de actualizare cat si de interogare.
Daca pentru un query ai O(N) si ai M query-uri, solutia va fi de complexitate O(M*N).

Ori eu va sugerez sa cautati cu O(M * log N)!

Arborele de intervale e altceva, nu tine nicidecum toate intervalele! Optimizeaza accesul la orice interval. E un pic mai elitist (nivel de "expert", daca tot suntem pe codexpert). Dar m-as bucura ca manacher1 sa caute si sa reuseasca sa o rezolve.

Dau indicatii daca se solicita...

Re: Problema cu intervale

Posted: 17 Apr 2015, 10:56
by Sumer
Pai incepe cu nelamuririle si hai sa incercam sa le raspundem.

Re: Problema cu intervale

Posted: 21 Apr 2015, 23:15
by xxscorp
Sincer nu m-ar deranja nici pe mine sa mi se raspunda la cele doua nelamuriri ale mele:
1) Cum implementez operatia de inlocuire element
si...
2) Cum implementez operatia de gasire a numarului.

Totul eficient, desigur :biggrin:

Multumesc!