Posted on

Cambios en el ranking

Continuando con los cambios en el ranking de omegaUp, a partir de hoy sólo los problemas resueltos marcados como públicos van a contar puntos para calcular el score. Este cambio es con la intención de hacer el ranking más justo con problemas visibles a todos.

De igual forma, el Coder del Mes también será calculado sólo con problemas públicos.

Desafortunadamente varios competidores cayeron bastantes posiciones en el ranking. Ayúdenos a convencer a su problemsetter favorito a que los problemas se publiquen al finalizar los concursos.

Posted on

Solución a “Jardinero”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 6
Autor: Saúl Germán Gutiérrez Calderón
Fuente: Saúl Germán Gutiérrez Calderón (recopilado de los ACM-ICPC World Finals 2010, problema I)

En este problema, una búsqueda exhaustiva con podas bastaba para que corriera en tiempo.

La búsqueda podía tener como estado al renglón y a la columna en la que se estaban, más las casillas por las que ya se había pasado más el numero de la siguiente casilla a esconderse que se necesitaba.

Las podas que se utilizaron en la solución oficial fueron las siguientes (otras podas podrían también conseguir 100 puntos):

  1. Que pasara el tiempo en el que se debería llegar a un escondite.
  2. Que se pasara por un escondite cuando no se debía.
  3. Que no fuera capaz de llegar al siguiente escondite a tiempo.
  4. Que el camino que se llevaba volviera imposible una ruta válida. Si la ruta dejaba a algunas posiciones “encerradas” o dividía al mundo en dos, entonces la ruta actual no llevaba a ningún recorrido valido. Esto se podía checar haciendo una búsqueda en profundidad o en amplitud desde alguna posición no visitada (la posición (0,1) es bastante conveniente porque siempre estará libre).

Aquí está el código de la solución:

Posted on

Solución a “Contraseña Binaria”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 7
Autor: Orlando Isay Mendoza Garcia
Fuente: Christian Adan Hernández Sánchez

Podemos ayudarnos de la imagen para comprender mejor esta explicación:

En ella aparecen de forma descendente a la izquierda los números pares comenzando desde el dos, y su representación binaria a la derecha. En la parte superior aparece el valor de cada cifra en decimal.

Tomando en cuenta el límite del problema, sabemos que si sumamos B(i) para cada par menor o igual a N, en el peor de los casos tendríamos que realizar 500,000,000,000,000 veces la función. Aún si lograramos calcularla en una operación nuestro programa excedería el tiempo límite.

En cambio, haciendo cálculos notamos que:
2^{50} \approx 1,000,000,000,000,000. Lo cual significa que a lo más habrán 50 columnas en la tabla (ya que en la forma binaria cada cifra representa una potencia de 2).

Dado que sabemos que en una suma el orden de las cantidades a sumar no importa, podemos determinar que es lo mismo sumar los valores de forma horizontal, tanto como de forma vertical. Sumando los valores de las columnas solo tomaría 50 operaciones. La columna 1 podemos ignorarla ya que al ser pares los números de la lista ninguno contendrá un 1 en la última cifra.

Observando la siguiente imagen, vemos que la columna C se forman grupos de tamaño C (por ejemplo, en la columna 4 se forman grupos de cuatro elementos),que contienen una la mitad de 1s y la otra de 0s. También podemos ver que en la columna 2 no hay 0s antes del primer grupo, en columna 4 hay un 0, en la que sigue hay 2, luego 4,etc (área en color gris). Podemos notar que ese espacio aumenta en base a potencias del dos.

Teniendo el número N habrán N / 2 números en la lista. Para calcular la cantidad de grupos completos que se forman en cada columna dividimos N menos el espacio lleno de ceros en esa columna, entre el número de la columna en el que estemos; a su vez, esta cantidad la multiplicamos por, el número de la columna entre dos. Sin embargo, puede que nos falten de contabilizar los 1s que pudieran estar en un grupo que no se completo. Esto se arregla sumando a lo anterior, el mínimo entre el resto de la división anterior y, el número de la columna entre dos.

Código:

Posted on

Solución a “Planetas”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 4
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves

La observación principal de este problema es que siempre hay N-1 lugares estables para el meteorito, y que cada uno de éstos se encuentra entre parejas consecutivas de planetas. Primero notemos que ningún lugar estable puede estar más a izquierda que todos los planetas, ya que la fuerza neta sobre éste lo haría moverse a la derecha. Por la misma razón, no pueden haber lugares estables después del último planeta hacia la derecha.

Ahora, para ver que siempre hay un lugar estable entre cualquier pareja consecutiva de planetas hay que analizar la función que describe la fuerza entre el meteorito y el planeta: \frac{1}{\left | X_i - M \right |}. Supongamos que el meteorito está entre los planetas i e i+1. Cuando M \approx X_i la fuerza que atrae al meteorito hacia el planeta i es suficientemente grande para forzar al meteorito a moverse a la izquierda sin importar la fuerza de los planetas que se encuentren a la derecha (nota que el denominador se hace muy pequeño). Lo mismo ocurre con el planeta i+1 cuando el meteorito está muy cerca de él. Pero esto quiere decir que existe un único punto p entre los dos planetas en el que la fuerza neta sobre el meteorito es 0. (Este argumento se puede formalizar utilizando cálculo.)

Además, es sencillo observar que el meteorito se movería a la izquierda si estuviera entre el planeta i y el punto p, y a la derecha si estuviera entre el punto p y el planeta i+1. Por lo tanto, podemos hacer una búsqueda binaria para encontrar el punto p para cada pareja de planetas consecutivos.

Como hay N-1 parejas y calcular la fuerza neta sobre el meteorito en algún punto arbitrario toma tiempo O(N), la complejidad total de este algoritmo es O(N^2 I) donde I es la cantidad de iteraciones que realice la búsqueda binaria. También hay que ordenar los planetas, ya que la descripción del problema no asegura que vendrán ordenados. Por lo tanto, la solución final tiene complejidad O(N \lg N + N^2 I).

El siguiente código implementa esta solución: