2171 - Another Range Tree Problem?

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
dovier
Posts: 1096
Joined: 6 years ago
Location: Havana, Cuba
Gender: Male
Cuba

2171 - Another Range Tree Problem?

Post by dovier » 5 years ago




ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Post by ArthurGPym » 1 year ago

Hola. Estuve intentando resolver este problema con un segment tree pero no logro evitar el time limit exceeded. Con lazy propagation podria optimizarse la actualizacion pero quisiera saber si hay una forma mas simple o eficiente de resolver este problema. Les paso el codigo del SegmentTree:
► Show Spoiler
Saludos

User avatar
isaac
Posts: 83
Joined: 2 years ago
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Post by isaac » 1 year ago

Men, ese código está muy largo y me pesa leer, asi que te voy a dar la idea esencial del problema. Tu debes saber que el Segment Tree guarda en cada nodo, informacion sobre todo el interalo que le corresponde, cierto?? Bien. A la hora de actualizar, tienes que aumentar en 1 el/los nodo/s que controla/n el intervalo [a; b] que te dan y luego hacer las queries sobre todos los a y b que te dan.

En el ejemplo de entrada:
5
1 5
2 4
3 5
1 2
4 4

Aumentas en 1 el nodo que controla el intervalo [1; 5], luego el [2; 4] y asi sucesivamente. Luego haces la query para la posicion 1, la 5, la 2, la 4 y asi hasta que evalues todas las queries para todos los extremos de los intervalos y de todas estas respuestas, toma la mayor. Date cuenta que no tienes que recorrer todo de un extremo a otro sino analizar solamente los extremos de los intervalos. De cualquier forma que agrupes los intervalos, siempre la respuesta va a estar en uno de ellos. Espero que te sirva la idea.

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Post by ArthurGPym » 1 year ago

Gracias, si, justamente eso estaba haciendo pero me daba time limit exceded, le agregue el lazy propagation al segment tree y funciono :D

saludos

User avatar
frankr
Posts: 49
Joined: 6 years ago
Location: Las Tunas
Gender: Male

Re: 2171 - Another Range Tree Problem?

Post by frankr » 1 year ago

Aunque el propio texto del problema y el título sugieren que puede haber una solución más sencilla que implementar un ST con lazy. Un ST para resolver este problema sería como tirarle con un arma nuclear, de todos modos es un buen problema para probar la implementación de un ST con lazy, y más aún, si es la primera vez que usas la estructura ;)

La solución más sencilla tiene costo temporal y espacial O(N) y es hacer un barrido de izquierda a derecha donde se lleva en todo momento cuántos segmentos están activos.

ArthurGPym
Posts: 11
Joined: 2 years ago
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Post by ArthurGPym » 1 year ago

Hola, estuve pensando la solucion O(n) que mencionas y entiendo como deberia ser pero no logro la implementacion. Probe hacer una lista de intervalos que despues ordeno segun momento de inicio y si son iguales segun final. Despues de eso recorro la lista pero no se como hacer para en cada momento ver qué intervalos estan activos.

saludos

User avatar
isaac
Posts: 83
Joined: 2 years ago
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Post by isaac » 1 year ago

Tendrías que ordenar los intervalos, insertando por separado los inicios y finales (por supuesto, teniendo algo que defina cuando es un inicio o un final). Los ordenas y simplemente es aumentar cuando inicie alguno y disminuir cuando termine alguno. La respuesta sería el mayor valor que tenga ese contador al final del recorrido completo.

User avatar
frankr
Posts: 49
Joined: 6 years ago
Location: Las Tunas
Gender: Male

Re: 2171 - Another Range Tree Problem?

Post by frankr » 1 year ago

No es necesario ordenar, si ordenas puedes subirlo a O(N Log N) dependiendo de método de ordenamiento que uses. Solo mantener la frecuencia de inicios y fines y luego cuando haces el barrido mantener un contador con la cantidad de intervalos activos.

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2171 - Another Range Tree Problem?

Post by HaZard » 1 year ago

frankr wrote:Aunque el propio texto del problema y el título sugieren que puede haber una solución más sencilla que implementar un ST con lazy. Un ST para resolver este problema sería como tirarle con un arma nuclear, de todos modos es un buen problema para probar la implementación de un ST con lazy, y más aún, si es la primera vez que usas la estructura ;)

La solución más sencilla tiene costo temporal y espacial O(N) y es hacer un barrido de izquierda a derecha donde se lleva en todo momento cuántos segmentos están activos.
Para este problema se puede usar una técnica que se llama Sweep Line en O(N log N) o por una técnica que se llama Preffix Sums: https://en.wikipedia.org/wiki/Prefix_sum, generalmente usada en DP, que funciona en O(N), es más sencilla y es la que creo que propone frankr. Saludos.
teruel

Post Reply

Return to “Problem set”