Ranking de Escuelas en omegaUp

Uno de los principales enfoques de nuestro equipo este 2017 ha sido facilitar el uso de omegaUp en las escuelas. Previamente anunciamos el lanzamiento de omegaUp Escuelas, un conjunto de funcionalidades que ayuda a los profesores a administrar cursos dentro de la plataforma y crear tareas y exámenes.

En esta ocasión anunciamos el nuevo ranking de escuelas más activas del mes en omegaUp:

Ranking de Escuelas

¿Cómo funciona?

La intención del ranking de escuelas es fomentar la participación activa de las escuelas en omegaUp. Para el mes en turno, calculamos el número de usuarios activos y problemas distintos resueltos de cada escuela. El ranking colocará a la escuela con mayor número de usuarios activos en el primer lugar y el número de problemas distintos resueltos se usará como criterio de desempate.

Un usuario activo es aquel que ha resuelto al menos un problema completamente (AC) y el número de problemas resueltos es el total de problemas distintos que colectivamente han resuelto (AC) todos los usuarios registrados con una escuela.

El ranking se calcula una vez al día, los cambios en usuarios activos y problemas resueltos se verán reflejados al día siguiente. Recuerda que ambos números se calculan sólo para el mes en turno: todos los contadores de este ranking se reinician a principio de cada mes.

¿Cómo registro mi escuela?

Lo único que tienes que hacer para que tu escuela sea considerada para el ranking de escuelas de omegaUp es asegurarte de llenar correctamente tu Escuela en tu perfil de omegaUp. Para construir el ranking usamos la información del perfil de todos los usuarios de la plataforma.

Cómo editar tu escuela

Asegúrate de usar el mismo nombre de escuela que todos tus demás compañeros. Por ejemplo: ESCOM y Escuela Superior de Cómputo son considerados como diferentes nombres aunque se refieran a la misma escuela.

¿Sugerencias?

Si tienes comentarios o sugerencias sobre esta y otras funcionalidades de omegaUp déjanos tus comentarios en este post. ¿Te gustaría ayudarnos a mejorar la plataforma? ¡Contáctanos en hello@omegaup.org!

Se realiza la 1era Competencia Peruana de Informática Online en omegaUp

Image

1ra Competencia Peruana de Informática Online

1ra Competencia Peruana de Informática Online

El pasado domingo 28 de mayo de 2017 se realizó la 1era Competencia Peruana de Informática Online (CPIO). Organizada por la Federación Olímpica Peruana de Informática (FOPI), la CPIO es la primera competencia en su tipo que convoca a alumnos pre-universitarios de todo el Perú para conformar la delegación peruana rumbo a la Competencia Iberoamericana de Informática y Computación (CIIC) 2017.

Fundada en diciembre de 2016 por Aldo Culquicondor, Edson Ticona, Jonathan Quispe, L. Rodolfo Nájera, Raúl Gallegos, Rodolfo Mercado y Yesica Aquino, la FOPI busca fomentar la informática competitiva pre-universitaria, apoyando a los niños y jóvenes peruanos a desarrollarse en este ámbito, preparando una delegación que represente al Perú y consolide logros internacionales.

La CPIO es una competencia multi-nivel de programación para jóvenes peruanos, con habilidades de resolución de problemas mediante el análisis, la lógica, el ingenio y la implementación de soluciones en un computador. El concurso realizado en omegaUp contó con la participación de competidores de las principales ciudades peruanas: Arequipa, Callao, Chepen, Cusco, Ica, Lima, Piura, Pucallpa, Puno y Tacna.

Al ser la primera competencia de programación competitiva en el Perú, se espera que CPIO marque el inicio del desarrollo de la informática en los jóvenes peruanos y como consecuencia un mejor desarrollo tecnológico en aquel país sudamericano, mencionó Aldo P. Culquicondor Ruiz, presidente de la FOPI.

Luego de la competencia, quedaron seleccionados ocho competidores para representar al Perú en la CIIC el próximo 10 de junio: Joaquin Rodrigo Palma Ugarte y Stheven Julmar Quispe Llamocca de Arequipa, Anthony Dante Yataco Torres y Nicolas Ticona Valdivia de Lima, Carlos Daniel Ramos Arellano de Piura, Johan Frank Cachicatari Ticona y Marcela Veronica Apaza Vilca de Puno y Roberto Carlos Huamán Rivera de Tacna.

Con la realización de esta competencia, la organización sin fines de lucro omegaUp da un paso importante para cumplir su objetivo de aumentar el número de ingenieros de software talentosos en todos los confines de América Latina.

Anunciando omegaUp Mentores

La misión de omegaUp es incrementar el número de ingenieros de software talentosos en América Latina, por lo que nos complace anunciar públicamente el programa omegaUp Mentores. El objetivo de este proyecto es ayudar a que nuestros usuarios más activos potencialicen sus habilidades, conectándolos con gente de experiencia que puedan servirles de guía para el desarrollo de su carrera profesional.

Para ello, omegaUp ofrecerá a los coders del mes la posibilidad de recibir mentoría personalizada de ingenieros de software voluntarios con experiencia internacional, habiendo laborado en las principales empresas de tecnología del mundo, tales como Microsoft, Facebook, Amazon, Google, entre otras. Además, el usuario galardonado se hará acreedor a un diploma y un premio que podrá ser de utilidad en su desarrollo técnico o académico.

Los ganadores interactúan con sus mentores mediante videollamadas y correos electrónicos. En el mes de Enero, el usuario Jorge Salazar Cruz, estudiante del CBTis 60 en Guanajuato, México, tuvo la oportunidad de hablar con Rafael Díaz, ingeniero de software en Microsoft.

Jorge Salazar (CBTIs 60) & Rafael Díaz (Microsoft)

Jorge Salazar (CBTIs 60) & Rafael Díaz (Microsoft)

Te invitamos a continuar resolviendo problemas en omegaUp para que obtengas más puntos en la plataforma y logres mejorar dia a dia. ¡Tú puedes ser el próximo Coder del mes!

Puedes encontrar más información de cómo se calcula el coder del mes en omegaUp aquí: https://blog.omegaup.com/2014/06/el-nuevo-ranking-de-omegaup/ . Para dudas y mayor información sobre este programa, puedes contactarnos en mentores@omegaup.com

Hackathon omegaUp febrero 2017 – Resultados

En omegaUp organizamos nuestro primer Hackathon del año abierto al público, del 23 al 25 de Febrero pasados. Esta vez incluimos un divertido Bug Bash, donde invitamos a nuestros voluntarios a encontrar bugs dentro de omegaUp y reportarlos en github.

Agradecemos la participación de todos los voluntarios que estuvieron involucrados. Los resultados que tuvimos fueron muy positivos: 50 bugs nuevos fueron descubiertos en el Bug Bash y se completaron 17 pull requests, muchos de ellos arreglando bugs que se encontraron en el mismo evento.

rcrx y joemmanuel hackathoneando.

Rafael Díaz (rcxr) y Joe (joemmanuel) hackathoneando.

omegaUp ofreció como premio una tarjeta de regalo de Amazon a quién encontrara más bugs y otra más a quien reportara el bug más interesante. Felicitamos a pacopedraza por llevarse el premio. El ranking de más bugs reportados quedó así:

  1. rcxr* (15)
  2. erosethan** (13)
  3. alanboy* (12)
  4. pacopedraza (6)
  5. cruzjorgesalazar (1)

*No compite por premio por ser directivo de omegaUp for schools.
** Ganador del bug más interesante.

Y el ganador al bug más interesante por votación fue “Create course with no credentials does nothing” abierto por erosethan.

bestbug-hackathon20171

El Hackathon y el Bug Bash se concentró en el nuevo proyecto que estamos trabajando internamente para facilitar el uso de omegaUp.com en el salón de clases: omegaUp para escuelas. Los profesores que usan la plataforma podrán crear Cursos dentro de omegaUp.com con tareas y exámenes para facilitar la organización de sus clases. Estas nuevas funcionalidades estarán disponibles para el público en general más tarde este año.

Agradecemos a todos su participación para ayudar a omegaUp a cumplir su misión de incrementar el número de ingenieros de software talentosos en América Latina. Si te gustaría participar en futuros eventos, contáctanos en hello@omegaup.com.

 

Solución a “Los Callejones de Guanajuato”

Problema: Los Callejones de Guanajuato.

En este problema se nos está pidiendo que, dado un grafo conexo no dirigido, encontrar un camino tal que pasemos por todas las aristas.

Esta es una aplicación directa de un problema conocido de grafos, aunque no es tan común como otros problemas, estoy hablando de los ciclos Eulerianos.

Continue reading

OmegaUp Inc

Durante más de 5 años omegaUp ha sido un proyecto de medio tiempo para nosotros. Escribir nuevas funcionalidades es difícil ya que todos tenemos otras responsabilidades de tiempo completo. Así que hace 7 meses comenzamos a considerar la opción de formalizar nuestro proyecto y convertirnos en una organización establecida legamente, que nos permitiera recibir ingresos y contratar a desarrolladores que se dedicaran de tiempo completo a diseñar y mantener la plataforma.

Esta fue la primera reunión que tuvimos al respecto, donde analizamos las ventajas y desventajas de incorporarnos. A lo largo de los meses siguientes trabajamos revisando requerimientos legales, escribiendo nuestros by-laws y en general, estableciendo las bases de lo que sería OmegaUp como una entidad legal. Decidimos que una organización sin fines de lucro en Estados Unidos era lo más apropiado, tanto por la naturaleza de lo que hacemos, así como por nuestra ubicación física.

Después de mucho trabajo, el 7 de octubre del 2016 recibimos la confirmación por parte del IRS de que nuestra organización es exenta del impuesto federal bajo el IRC sección 501(c)(3). Esto significa que OmegaUp es reconocida como una caridad publica a nivel estatal y federal y por ende todos sus donantes pueden deducir de sus impuestos las contribuciones que hagan a OmegaUp. También nos califica para recibir legados, transferencias o regalos.

Como parte del proceso de incorporación, se formó un comité directivo cuya responsabilidad será la de mantener la salud, preservación y progreso de esta organización. Cada uno de los miembros del comité directivo representara los intereses de los donantes y de la gente beneficiada con este proyecto.

 Más información sobre la organizacion puede encontrarse en http://omegaup.org

 

Concursos recomendados

Respondiendo a los comentarios que hemos recibido sobre la organización de la lista de concursos en la Arena, hemos implementado el concepto de Concursos Recomendados:

Concursos recomendados

A partir de ahora tendremos una lista separada para los Concursos Recomendados actuales y pasados. Para pedir que tu concurso sea marcado como recomendado escribe un email a omegaup-soporte@googlegroups.com.

Los únicos requerimientos son:

  • Que el concurso sea formalmente establecido (sea parte de una olimpiada, concurso de ACM u algún otro concurso de programación).
  • Que el creador del concurso se comprometa a mantenerlo en buen estado respondiendo las clarificaciones que pueda.
  • Idealmente los Concursos Recomendados deben tener problemas nuevos aunque no es estrictamente necesario.
  • El tamaño del concurso no importa.
  • Concursos privados que cumplan estos requerimientos y que se planean hacer públicos posteriormente también cuentan.

Esperamos sus comentarios.

Invasion Zombie

Hola!, este es mi primer post en Omegaup y voy a describir mi solución para el problema Invasion zombie.

Hace un año encontré este problema, me pareció interesante y logre resolverlo, aunque algo tricky. Hace unos días me tope con este problema nuevamente y lo resolví por segunda ocasión, pero con una solución más simple, al menos eso creo.

Primer solución

La idea principal tanto en la primera como en la segunda solución es diseñar una función f(d) que nos retorne el número de colonias infectadas después de d días, nos interesa el mínimo valor de d tal que el número de colonias infectadas sea mayor o igual a C. Una propiedad importante es la siguiente, f(d) nunca decrece, es decir f(d) <= f(d+1). Esta propiedad nos permite utilizar búsqueda binaria para encontrar las respuesta en O(\lg_{2}(n)).

Diseñar una función que determine el número de colonias infectadas, dependiendo del background de cada uno, es la parte interesante, y es donde difieren las dos versiones, bueno, un poco.

Este es el código de la primer versión, no voy a entrar en detalles porque ni yo me acuerdo bien que trucos aplique, pero la idea es parecida a la de la de la segunda versión, lo que cambia es la estrategia.

Segunda versión

Bueno, empecemos, trascurridos d días, ¿cuántas colonias han sido infectadas?

Simulemos la invasión y veamos si podemos encontrar un patrón.

zombies-pattern

No es complicado llegar a la siguiente fórmula:

f(d) = d^{2} + (d+1)^{2}

Si el espacio de la ciudad fuese ilimitado nuestra función de verificación sería algo parecido a:

Sin embargo, el espacio de la ciudad es limitado y habrá casos como los siguientes:

zombies-sc1

zombies-sc2

Entonces nuestro objetivo es encontrar el área delimitada por la ciudad (un cuadrado de N * N unidades), lo cual se pone un poco tricky. La siguiente imagen nos ayudará a entender el código de la solución sin entrar en tantas explicaciones.

zombies-solution

Es decir, el área total menos el área de los triángulos superior, inferior, izquierdo y derecho. Obsérvese que los triángulos pueden traslaparse y por lo tango estaríamos restando esas áreas 2 veces, por ello tenemos que calcular las áreas de traslape (nw, ne, se y sw en la imagen) y regresar lo a la suma total.

Lo que sigue es la implementación:

Espero que les sea útil, dudas, comentarios o correcciones son bienvenidas.

Solución a “Splatoon”

Problema: Splatoon.

Este problema pide llevar a un inkling desde el inicio de una calle hasta el final siguiendo sus reglas de movimiento.

Ignoremos por un momento el hecho de que los inklings pueden pintar el piso y con ello alterar la calle en donde se realiza la carrera. Si los inklings no tuvieran esta habilidad, se puede hacer un algoritmo de fuerza bruta intentando todas las operaciones posibles, es decir, hacer una búsqueda en amplitud para encontrar el camino más corto, en donde el estado está representado únicamente por la posición en donde se encuentre el inkling.

Recuerda que en las búsquedas es importante marcar visitados para que la complejidad del algoritmo no se vuelva exponencial.

Para cada posición, se tienen dos posibles operaciones, saltar, o caminar, ambas toman 1 segundo y la distancia a la que se llega depende directamente del color sobre el que se está parado. El movimiento de saltar es muy fácil pues solo hay una casilla donde se puede caer, pero el movimiento de avanzar difiere cada vez pues depende directamente del color de las siguientes casillas.

Es posible hacer un ciclo para ver hasta donde puedes llegar avanzando desde la casilla en donde estás, y agregar a la búsqueda el lugar más lejano a donde puedas llegar. Sin embargo, si únicamente registramos la última casilla a donde se puede llegar, casos como el siguiente se nos escaparán:

En la solución superior, primero se avanza todo lo que se puede en la pintura naranja hasta llegar a la casilla azul, de ahi ya sea saltando o avanzando únicamente se puede llegar a la casilla blanca, y de ahí, no importa lo que hagas, te tomará dos segundos llegar al final.

En cambio, en la solución inferior, se avanza solo 3 casillas en la pintura naranja, lo cual es 1 casilla menos del máximo, de ahí se hace un salto el cual nos deja de nuevo en pintura naranja, desde donde podemos llegar caminando hasta el final en un total de tan solo 3 segundos, 1 segundo menos que la solución anterior.

Por lo tanto, no es suficiente visitar la distancia máxima, también hace falta visitar la distancia máxima – 1. Si intentamos hacer cosas similares con otro color de pintura, o más deteniéndonos todavía más atrás del máximo, no hay realmente ninguna ventaja, por lo que el caso presentado anteriormente es el único caso especial.

Una búsqueda en amplitud bien hecha que considere este caso sacará 30 puntos, una que no considere este caso sacará únicamente 5 puntos. Da perfectamente en tiempo y memoria porque a lo más tendremos un total de 1000 estados.
Sin embargo, la parte interesante de este problema es que los inklings son capaces de alterar el estado de la calle usando la pintura que traen en su tanque para poder recorrer más rápido la calle, utilizando hasta D disparos de tinta.

En este caso, necesitamos agregar una segunda dimensión al estado de nuestra búsqueda, ahora no sólamente es suficiente con guardar el lugar en donde estamos, sino que es necesario guardar también cuanta tinta queda en el tanque. En este caso, agregamos una operación más, la cual es pintar, la cual cuesta 0 segundos, nos avanza 0 casillas y nos quita una unidad D de pintura.

Si hacemos esto, nuestro espacio de búsqueda crece del N que era en la solución de 30 puntos, a N x D, lo cual es 1000 x 1000 y aún da en tiempo y memoria.

No obstante, la operación de pintar altera el mapa, por lo que si no guardamos también en el estado que las casillas siguientes ahora son de otro color, pintar no servirá de nada. Podríamos agregar una dimensión más a la búsqueda para considerar este caso, pero esto solo le agregaría complejidad innecesaria a la búsqueda.

La clave está en que pintar toma 0 segundos, por lo que podemos convertir la operación de pintar en una operación compuesta, que sea pintar y avanzar.

Pintar y avanzar toma 1 segundo, y nos permite avanzar 4 casillas hacia adelante siempre, por lo que hacer una operación de pintar y avanzar nos lleva del estado (i, d) al estado (i + 4, d – 1) con un costo de 1 segundo.

El detalle con esta solución, es que estamos ignorando de nuevo el caso especial explicado en la solución de 30 puntos, por lo que si se nos olvida que es posible ahorrarnos un segundo en ciertas ocasiones, sacaremos entre 35 y 90 puntos dependiendo de la implementación.

Para sacar los 100 puntos, es necesario agregar una operación más, la cual es pintar, avanzar y saltar, la cual nos lleva del estado (i, d),  al estado (i + 6, d – 1) con un costo de 2 segundos. Y como esta operación toma 2 segundos en vez de tan solo 1, no es suficiente con utilizar una cola común y corriente para hacer la búsqueda en amplitud, sino que es necesario utilizar una estructura de datos más avanzada, como una cola de prioridad o un montículo que nos ayude a ordenar los estados y elegir siempre con el tiempo más pequeño.

 

Solución a “Los Chocolates del Agente Nieves”

Problema: Los Chocolates del Agente Nieves

En este problema tenemos un tubo de chocolates los cuales se van a vender uno cada día, pudiendo vender únicamente los que están en ese momento en los extremos. El precio por vender un chocolate es igual al precio base de chocolate multiplicado por el número de días que se han vendido chocolates (empezando en 1).

El objetivo es encontrar la mayor ganancia posible al vender todos los chocolates.

 

Si lo quisiéramos resolver como una búsqueda, ¿qué tendríamos que considerar? En una búsqueda, nos importa obtener dos cosas, el espacio de búsqueda (es decir, cómo estará representado nuestro estado y qué valores puede tener), y las operaciones en nuestra búsqueda.

En cuanto a nuestros estados en la búsqueda, nos importa saber qué chocolates aún tenemos disponibles y cuántos días han pasado. Podríamos empezar teniendo N valores booleanos por cada chocolate y un número para saber cuántos días han pasado, por ejemplo, si tenemos 3 chocolates y aún no vendemos nada, tendríamos el estado (1, 1, 1, 1), si ya vendimos el primer chocolate, tendríamos (0, 1, 1, 2), si vendimos el tercer chocolate tendríamos (1, 1, 0, 2) y si vendemos los chocolates 1 y 2, tendríamos (0, 0, 1, 3). Sin embargo, esta representación es un poco inútil, ya que en el peor de los casos, tendríamos 1000 chocolates, lo cual hace un estado de 1000 posibles valores.

Podemos mejorar esto solo guardando únicamente los índices a los extremos del tubo, ya que ya sabemos que aún tenemos todos los chocolates entre estos dos valores. Eso transforma los estados anteriores a los siguientes estados respectivamente: (1, 3, 1), (2, 3, 2), (1, 2, 2). y (3, 3, 3). Esto vuelve al estado muchísimo más manejable, pues cada valor puede valer únicamente entre 1 y 1000.

Ya que tenemos nuestro estado, definimos las operaciones que hay que hacer para ir entre estado y estado, y estas operaciones son únicamente 2, vender el chocolate de la izquierda, o vender el chocolate de la derecha, si estamos en el estado (1, 3, 1) y vendemos el de la izquierda, nos lleva al estado (2, 3, 2), y si vendemos el de la derecha, nos lleva al estado (1, 2, 2). Podemos continuar estas instrucciones recursivamente sobre los estados que resulta y generar un árbol de búsqueda:

Una vez teniendo el árbol de búsqueda, podemos proceder a darle valor a cada uno de los nodos. Del nodo inicial (1, 3, 1), si decides vender el chocolate de la izquierda, obtendrás una ganancia igual a lo que te de el nodo (2, 3, 2) más el precio del chocolate 1 multiplicado por el número de días, que en este caso es 1, y si decides vender el chocolate de la derecha, la ganancia será lo que de el nodo (1, 2, 2) más el precio del chocolate 3 (múltiplicado por 1). De las dos opciones, tomaremos el máximo.

Llenemos ahora el resto del árbol de búsqueda con estos datos:

De aquí podemos ver dos cosas, la primera es que los nodos de hasta abajo, que son nuestros nodos hoja, tienen el mismo valor en el chocolate izquierdo como en el derecho, por lo que el valor máximo que podemos obtener de ellos es el precio de ese único chocolate por el número de días que llevamos. Y la segunda cosa es que tenemos nodos repetidos, por lo que cuando hagamos nuestra búsqueda, necesitamos guardar cálculos que ya hayamos hecho para no calcular un mismo estado más de una vez.

Nuestro árbol de búsqueda ya está terminado, así que es hora de convertirlo a una función matemática. Nuestra función recibe como entrada un estado, en este caso el chocolate más a la izquierda que nos queda, el más a la derecha y el nivel en el que estamos, y dado lo que aprendimos de nuestro árbol de búsqueda, regresará el siguiente valor:

Con esto, y considerando que debemos evitar repetir valores duplicados, es más que suficiente para resolver el problema con el método que más te guste, ya sea dinámica o memorización, aunque hay un pequeño problema para guardar los valores visitados.

Vamos a necesitar un arreglo de 1000 x 1000 x 1000 si es que queremos guardar un arreglo que se identifique de esta forma:

arreglo[izquierda][derecha][nivel]

Y esto es mucho más de lo que cabe en memoria, por lo que tenemos que encontrar una forma de reducir la memoria que necesitamos.

Lo que nos tenemos que dar cuenta es que la variable nivel es innecesaria, pues puede calcularse utilizando el número de chocolates que nos quedan en el tubo y el número de chocolates que teníamos originalmente:

nivel = total – chocolates_en_el_tubo + 1

Y para calcular el número de chocolates que nos quedan en el tubo solo se necesitan el índice del chocolate más a la izquierda, y más a la derecha, que ya tenemos en nuestro estado.

chocolates_en_el_tubo = derecha – izquierda + 1

Despejando:

nivel = total – derecha + izquierda – 1 + 1

nivel = total – derecha + izquierda

De esta forma, podemos eliminar el nivel de todos nuestros estados y cambiar el valor de nivel de todas las fórmulas por el valor de arriba. Esto simplifica nuestro arreglo de visitados de 1000 x 1000 x 1000 a un arreglo de tan solo 1000 x 1000, lo cuál es suficiente en tiempo y memoria.