Problema cu intervale

Intrebari despre limbajul C++, standardul C++, STL, OOP in C++ sau alte subiecte nelegate de VisualC++
Post Reply
manacher1
Junior
Junior
Posts: 1
Joined: 24 Apr 2013, 09:23
Judet: Bucureşti

Problema cu intervale

Post by manacher1 » 24 Apr 2013, 09:33

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?



User avatar
bu7ch3r
Membru++
Membru++
Posts: 326
Joined: 17 May 2011, 15:17
Judet: Iaşi
Location: Sofia
Contact:

Re: Problema cu intervale

Post by bu7ch3r » 24 Apr 2013, 10:58

De ce solutia ta nu este optima?
De ce crezi ca ai avea nevoie si de alta structura de date?
Cu stima,
Lupu Claudiu

User avatar
Sylvie Woo
Junior
Junior
Posts: 12
Joined: 18 Nov 2011, 13:02

Re: Problema cu intervale

Post by Sylvie Woo » 26 Apr 2013, 13:46

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.

User avatar
Sylvie Woo
Junior
Junior
Posts: 12
Joined: 18 Nov 2011, 13:02

Re: Problema cu intervale

Post by Sylvie Woo » 29 Apr 2013, 10:52

@manacher1: Ai gasit, te descurci? Ai nevoie de indicatii?

User avatar
bu7ch3r
Membru++
Membru++
Posts: 326
Joined: 17 May 2011, 15:17
Judet: Iaşi
Location: Sofia
Contact:

Re: Problema cu intervale

Post by bu7ch3r » 29 Apr 2013, 12:24

@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)
Cu stima,
Lupu Claudiu

User avatar
Sylvie Woo
Junior
Junior
Posts: 12
Joined: 18 Nov 2011, 13:02

Re: Problema cu intervale

Post by Sylvie Woo » 29 Apr 2013, 12:47

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

Sumer
Junior
Junior
Posts: 1
Joined: 17 Apr 2015, 10:52
Judet: Botoşani

Re: Problema cu intervale

Post by Sumer » 17 Apr 2015, 10:56

Pai incepe cu nelamuririle si hai sa incercam sa le raspundem.

xxscorp
Junior
Junior
Posts: 7
Joined: 31 Jan 2011, 15:01
Judet: Timiş

Re: Problema cu intervale

Post by xxscorp » 21 Apr 2015, 23:15

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!

Post Reply