Deprecated: mysql_connect(): The mysql extension is deprecated and will be removed in the future: use mysqli or PDO instead in /home/olimpiada_informatica/ask.icpc-bolivia.edu.bo/qa-include/qa-db.php on line 66
Ayuda con "Dancing Elephants" (IOI Tailandia) - Olimpiada de Informatica - Q&A
Bienvenido al sitio de Preguntas y Respuestas (Q&A) de la Olimpiada de Informatica, donde tu podras realizar preguntas y recibir respuestas de otros miembros de la comunidad.

Most popular tags

spoj ioi obi abierto icpc uva

32 questions

42 answers

15 comments

4,723 users

Ayuda con "Dancing Elephants" (IOI Tailandia)

0 votes
Como puedo obtener los 100 puntos en este problema?? intente usando el solucionario oficial pero no lo entiendo del todo. Alguien podria ayudarme?

Problema:

http://bo.spoj.com/problems/TH_ELEPH/

Solucionario:

http://www.ioi2011.or.th/hsc/tasks/solutions/elephants.pdf

Saque 38.24 puntos
asked Mar 4, 2014 by Daydreamer (M Wilde) (2,480 points)

1 Answer

+2 votes
Ese es el puntaje por fuerza bruta.

Para obtener 100 puntos, no siempre es posible con la siguiente mejor solución, muchas veces requiere 2 o más optimizaciones. Es mejor ir paso a paso.

Para mejorar tu puntaje, sería bueno mejorar dicha solución. Una búsqueda por fuerza bruta es O(N). Como podrías mejorar la búsqueda para no hacerla lineal?

Una pista es la siguiente:

Dado que las posiciones son muy grandes, es dificil introducir elementos en una estructura de datos que tenga que reservar espacio (interval tree por ej. ), pero hay una técnica para poder sortear este obstáculo.

 

Para eso, necesitamos comprimir los datos, hacer que todos los números sean consecutivos, pero para esto necesitamos procesar los datos de forma "offline", es decir, despues de haber leido toda la entrada. Ya que despues de tener todos los datos, ya podemos comprimir los números que vayamos a usar.
answered Mar 9, 2014 by gareve (220 points)
Como se procesan datos de forma "offline"? y como se comprime?

Related questions

0 votes
0 answers
–2 votes
1 answer
asked Jan 15, 2014 by ronaldo
+1 vote
1 answer
...