Solución a “Poema Equino”

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

Los límites de este problema permitían hacer una búsqueda sobre todos los estados posibles de los caballos sobre el teclado, ya que si el estado es (\text{poema},\text{fila caballo}_1,\text{columna caballo}_1,\text{fila caballo}_2,\text{columna caballo}_2), solamente hay 100 \times (4 \times 10)^2 = 160,000 estados distintos.

Además, como el problema no pide la cantidad mínima de movimientos no hace falta hacer una BFS (búsqueda en amplitud), sino que una DFS (búsqueda en profundidad) utilizando el mismo stack del lenguaje es suficiente. Para simplificar la implementación, se podían utilizar varias observaciones. Particularmente, no importa qué caballo es el 1 o el 2, por lo que en vez de escribir código para mover a ambos basta con añadir una transición que cambie los roles de los caballos en cada estado. Esto además de simplificar la implementación sirve como una poda ya que ¡reduce la cantidad de estados a la mitad! (¿por qué?). También, se puede aprovechar que los operadores booleanos en C/C++ evalúan a 1 cuando son verdaderos y a 0 cuando son falsos, lo cual es bastante útil para indexar arreglos.

Varios competidores fallaron en su primer intento por no revisar que los caballos no podían ocupar la misma tecla al mismo tiempo. ¡Cuidado!

La siguiente solución implementa las simplificaciones descritas anteriormente.

Solución a “Carretera”

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

Para obtener los puntos de la primer subtarea bastaba notar que las condiciones especificadas significan que hay dos bloques de coches yendo en diferentes sentidos que inicialmente no se intersectan y eventualmente lo harán, por lo que la respuesta simplemente es el máximo de los anchos de estos bloques.

Este código obtiene los primeros 30 puntos:

Para el resto de los puntos: Sea f(t) el ancho necesario para la fotografía en el segundo t. La observación crucial es que f es una función unimodal: es decir, existe un punto t_0 tal que f es decreciente a la izquierda de t_0 y es creciente a la derecha.

Computar f(t) para t fijo es trivial: basta con obtener el coche más a la izquierda y más a la derecha en el segundo t, lo cual toma tiempo O(N). Como f es unimodal, podemos utilizar búsqueda ternaria o búsqueda binaria para encontrar el mínimo de la función en tiempo O(\lg T), donde T es el tamaño del rango a evaluar. Con eso obtenemos un algoritmo con complejidad O(N \lg T), suficiente para obtener todos los puntos del problema.

El siguiente código implementa la solución anterior con búsqueda binaria.

omegaUp presentado en la International Olympiad in Informatics 2014

IOI Journal

 

Del 13 al 18 de Julio del 2014 se llevó a cabo la International Olympiad in Informatics (IOI) en Taipei, Taiwán. En paralelo a la IOI, el comité organiza la publicación de la revista IOI Journal donde los países participantes pueden publicar artículos sobre la olimpiada en general, tanto técnicos como reportes y explicaciones de cómo es la olimpiada alrededor del mundo. Dichas publicaciones se presentan durante la IOI, en la IOI Conference.

Este año México participó en el IOI Journal Volumen 8 con la presentación del paper de omegaUp:

omegaUp: Cloud-Based Contest Management System and Training Platform in the Mexican Olympiad in Informatics
L.H. CHÁVEZ, A. GONZÁLEZ, J. PONCE. 

El paper explica la motivación y el funcionamiento detrás de omegaUp. Es un buen documento introductorio para quienes deseen apoyar en el proyecto. También pone a omegaUp como pionero en el uso de la nube y seccomp-bpf para evaluadores de concursos en líneaEl resto de los papers publicados este año y en años pasados está aquí.

 

Trucos para ser más cool

Después de un rato de investigación y experimentación, por fin me tomo el tiempo para escribir este post y presentarles algunos trucos que, considero, podrían ayudarles a simplificarse la vida cuando programen y, obviamente, a ser mucho más cool.

¿Cansado de importar librerías como asíatico en TopCoder? ¡Aquí está la solución!

Muchas veces es nefasto encontrar varios (sino es que miles) errores al compilar a causa de librerías que hemos olvidado incluir. Existe una librería que, al incluirla, agrega todas las librerías estándar de C++ a nuestro código, ¡incluso las de la STL!

¿Que clase de brujería es esta? Seguramente se estarán preguntando. Muy sencillo, solo necesitan escribir la siguiente línea de codigo: #include <bits/stdc++.h>

(Actualización) Gracias a el comentario de lhchavez por remarcar el hecho de que esta línea funciona únicamente con el compilador gcc. Pese a esto, gran parte de los evaluadores actualmente usan gcc, por lo que podemos confiar en su uso, al menos en omegaUp. En caso de que la librería anterior no siga siendo soportada por omegaUp, les informaremos oportunamente.

¡Mi mami dice que cin/cout es malo y no debo juntarme con ellos!

Si no me equivoco, durante mucho tiempo se ha tratado a scanf y printf como el pan de cada día para la entrada y salida en los concursos de programación, al menos en México. Mientras tanto, se satanizó a cin y cout por ser lentos (o especiales, como dice mi mami) para realizar entrada y salida eficiente.

Sin embargo esto siempre fue un mito, los métodos cin/cout son incluso más eficientes que scanf/printf, solo había que descubrir el por que no lo notamos.

Resulta que cin/cout son muy buenos amigos de scanf/printf. Como son tan buenos amigos, al realizar la lectura y salida no querían alejarse demasiado, por lo que cin/cout tenía que sincronizarse para estar siempre a la par de scanf/printf.

Para no hacer el cuento largo, hay una forma de desactivar la opción de sincronización entre cin/cout y scanf/printf, solo es necesario incluir al inicio del main:

cin.tie(0);
ios_base::sync_with_stdio(0);

Con esto podemos usar cin y cout sin temor a obtener TLE por lectura lenta, ¡Yaaay!

¿Y eso es todo? ¿Ya puedo disfrutar de cin y cout?

Casi. Antes de cantar victoria hay un último detalle para evitar los TLE. Gracias a un último experimento, encontramos que cuando se presentaban outputs muy grandes, cin/cout optimizado seguía lanzando TLE cuando scanf/printf no.

¡Tranquilos! También es posible evitar este error. El problema se presentaba porque comúnmente usaríamos lo siguiente: cout << numero << endl. Sucede que endl, además de imprimir un salto de línea, hace flush en el flujo de salida, lo cual es considerablemente costoso al imprimir muchas líneas y entorpece el rendimiento.

Para que la salida sea eficiente, recomendamos que uses el salto de línea literal "\n".

Con los dos trucos anteriores, la eficiencia de cin/cout mejora generalmente un 5-10% los resultados obtenidos por scanf/printf. Bastante cool, ¿no?

Aunque el objetivo original no es ganar unas cuantas centésimas de segundo en eficiencia, sino dar la oportunidad a aquellos olímpicos que no manejan scanf/printf para seguir usando cin/cout sin enfrentarse a más complicaciones.

Finalmente les dejó un ejemplo de cómo usar todo lo anterior en un código de C++. Espero que algo de esto les pueda ayudar en el futuro. Les deseo lo mejor :)

#include <bits/stdc++.h>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

int main(){
        optimizar_io

        int a, b;
        cin >> a >> b;
        cout << a + b << "\n";

        return 0;
}