Introducción a omegaUp, parte 1

Estamos iniciando una serie de 10 posts para ayudar a nuestros nuevos usuarios a navegar con facilidad entre la gran cantidad de problemas de omegaUp, en forma de mini-tutoriales con los conceptos básicos, temas y fuentes. Esta colección de tutoriales y ligas te ayudarán a resolver muchos de los problemas de omegaUp y aumentar tu nivel de programación.

Continue reading

Introducción a Omegaup, parte 2 – Problemas básicos

Hola de nuevo. Continuando con la serie Introducción a Omegaup, esta vez vamos a hacer referencia a los problemas más sencillos de la plataforma a la fecha. Aquí se encuentra la parte 1 de esta serie.

Para estos problemas, no se requiere conocer una técnica o un algoritmo en específico: simplemente requieren implementar (o simular) lo que se describe en el problema o hacer una o dos observaciones relativamente sencillas que permiten simplificar la implementación o acortar el número de operaciones que tu programa tendría que hacer y con ello poder resolver el problema dentro de los límites.

Material de estudio

Antes de pasar a la lista de problemas, quiero empezar con las lecturas recomendadas para empezar a resolver problemas en omegaUp:

Problemas directos
Estos concursos fueron diseñados para familiarizarse con la programación competitiva en general. Son excelentes para empezar y su solución generalmente no requiere dominar una técnica en específico, más bien requieren saber usar las construcciones (ciclos, condiciones, etc…) del lenguaje correctamente:

Tienes más sugerencias de problemas o dudas sobre los existentes? Escríbelos en los comentarios.

Solución a “Mapas de bits”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12
Autor: Jorge Alberto González Martínez
Fuente: Jorge Alberto González Martínez

En el problema se describen dos formas de representar un mapa de bits.

La forma bidimensional es simplemente utilizar una matriz para representar los bits.
La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.

La solución a este problema consistía en programar el método descrito. Este método inherentemente está basado en la técnica de divide y vencerás.

A continuación, un pseudo-código que muestra la forma de llevar a cabo la transformación de un mapa de bits bidimensional a la forma reducida:


ReduceMapa(mapaDeBits)
Si todos los elementos en mapaDeBits son iguales
    Imprime el valor y termina
Si no
    Imprime D
    ReduceMapa(mapaDeBits.superiorIzquierdo)
    ReduceMapa(mapaDeBits.superiorDerecho)
    ReduceMapa(mapaDeBits.inferiorIzquierdo)
    ReduceMapa(mapaDeBits.inferiorDerecho)

El método para hacer la transformación inversa es muy parecido, sólo que para imprimir la equivalencia hay que comenzar con un mapa de bits bidimensional que nos sirva de variable auxiliar para hacer la conversión. Esta variable auxiliar se puede declarar de manera global y, cuando el método recursivo termine, simplemente imprimir su contenido:


AmplificaMapa(mapaDeBits, sección)
Si mapaDeBits comienza con un valor
    Rellenar sección del mapa bidimensional con el valor
Si no
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorDerecha)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorDerecha)

La primera vez que se llama a la función AmplificaMapa se debe entregar la representación de la forma por descomposición del mapa de bits en la variable mapaDeBits y la sección que se entrega inicialmente es todo el mapa de bits. Esto puede ser manejado por filas y columnas.

A continuación se muestra una implementación en C++ que resuelve el problema. Nótese cómo se maneja la sección sobre la que se está trabajando con cuatro variables: tl_row, tl_col, br_row, br_col. El nombre de las variables proviene de top-left row, top-left colum, bottom-right row y bottom-right colum respectivamente. Representan los índices (fila,columa) de las esquinas superior izquierda e inferior derecha.

Solución a “Pista”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14
Autor: Miguel Covarrubias
Fuente: Codeforces

Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.

Para N \le 10 se pueden checar todas las 2^N configuraciones de pistas. Para N \le 1000 funciona una dinámica O(N^2), donde los estados son (posición, altura/profundidad que se lleva hasta el momento).

Les dejo la implementación de DiegoRoque como un muy buen ejemplo de una solución a este problema.