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.
User avatar
dovier
Posts: 1096
Joined: Fri Nov 11, 2011 9:32 am
Location: Havana, Cuba
Gender: Male

2171 - Another Range Tree Problem?

Postby dovier » Thu Nov 29, 2012 12:00 am




ArthurGPym
Posts: 11
Joined: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Postby ArthurGPym » Sun Oct 09, 2016 9:44 pm

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: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Postby isaac » Mon Oct 10, 2016 1:24 pm

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: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Postby ArthurGPym » Tue Oct 11, 2016 10:19 am

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: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 2171 - Another Range Tree Problem?

Postby frankr » Thu Oct 13, 2016 11:31 am

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: Sat Jul 30, 2016 5:43 pm
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Postby ArthurGPym » Sun Oct 16, 2016 3:06 pm

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: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 2171 - Another Range Tree Problem?

Postby isaac » Sun Oct 16, 2016 11:55 pm

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: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 2171 - Another Range Tree Problem?

Postby frankr » Tue Oct 18, 2016 11:48 am

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 2171 - Another Range Tree Problem?

Postby HaZard » Thu Oct 20, 2016 3:38 pm

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


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest