Page 1 of 1

2171 - Another Range Tree Problem?

Posted: Thu Nov 29, 2012 12:00 am
by dovier

Re: 2171 - Another Range Tree Problem?

Posted: Sun Oct 09, 2016 9:44 pm
by ArthurGPym
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

Re: 2171 - Another Range Tree Problem?

Posted: Mon Oct 10, 2016 1:24 pm
by isaac
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.

Re: 2171 - Another Range Tree Problem?

Posted: Tue Oct 11, 2016 10:19 am
by ArthurGPym
Gracias, si, justamente eso estaba haciendo pero me daba time limit exceded, le agregue el lazy propagation al segment tree y funciono :D

saludos

Re: 2171 - Another Range Tree Problem?

Posted: Thu Oct 13, 2016 11:31 am
by frankr
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.

Re: 2171 - Another Range Tree Problem?

Posted: Sun Oct 16, 2016 3:06 pm
by ArthurGPym
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

Re: 2171 - Another Range Tree Problem?

Posted: Sun Oct 16, 2016 11:55 pm
by isaac
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.

Re: 2171 - Another Range Tree Problem?

Posted: Tue Oct 18, 2016 11:48 am
by frankr
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.

Re: 2171 - Another Range Tree Problem?

Posted: Thu Oct 20, 2016 3:38 pm
by HaZard
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.