Una vez más tenemos un problema del Google Code Jam traducido y listo para ser resuelto. En esta ocasión se trata de encontrar la distribución más óptima para un teclado de un hipotético teléfono celular. La premisa es que la distribución habitual no toma en cuenta la frecuencia con que se utilizan las teclas limitándose a ubicarlas de forma consecutiva lo cual nos lleva a tener que realizar un número de pulsaciones mayor que si se hubiera tomado en cuenta la frecuencia mencionada. Si lograramos ubicar las letras del alfabeto de modo tal que, dado un mensaje, se necesitara la menor cantidad posible de pulsaciones entonces la escritura del mensaje sería óptima.
De hecho, la respuesta al problema debe ser el mínimo número de pulsaciones que tendríamos que realizar si encontramos la distribución óptima para nuestro hipotético teclado. El texto completo del problema, que viene con una introducción a modo de relato, puede ser descargado aquí.
Espero que sigan animándose a resolver estos problemas y, que sean más quienes dejen sus comentarios que serán de mucha ayuda para quienes recién estan empezando.
Mostrando entradas con la etiqueta code jam. Mostrar todas las entradas
Mostrando entradas con la etiqueta code jam. Mostrar todas las entradas
7 ago 2008
29 jul 2008
Producto Escalar Mínimo
Nuevamente comparto con ustedes un problema del Google Code Jam 2008, esta vez corresponde al primer problema (Problema A) de la ronda de clasificación 1A. Se trata de calcular el Producto Escalar Mínimo entre dos vectores considerando todas sus permutaciones. Si no quedó claro, me disculpo y les ofrezco la traducción del problema que pueden descargar aquí.
Como ya sabrán quienes pasaron por el sitio del Google Code Jam el problema planteado debe ser resuelto para dos conjuntos de soluciones un conjunto pequeño y un conjunto grande, el tiempo entre la descarga del conjunto de prueba y la remisión de la solución es de 4 y 8 minutos respectivamente.
La idea detrás de este mecanismo es que un algoritmo que resuelva el problema pueda ser probado sin mayores optimizaciones con el conjunto de prueba pequeño que, usualmente, tiene restricciones en el rango de los datos de entrada no solamente en el número de casos. Y luego, en un segundo paso se pueda optimizar el mismo algoritmo para procesar el conjunto de prueba grande que contendrá un número mayor de casos y estará compuesto por valores también mucho más grandes. Para descargar los conjuntos de prueba y remitir sus soluciones pueden acceder a la página de la competencia.
Nuevamente, espero que se animen a resolver este problemita. Utilizando fuerza bruta se puede resolver para el caso de prueba pequeño y para el caso grande se puede utilizar alguna heurística o una estructura como un árbol. En cualquier caso, no se olviden de comentar como les fue.
Como ya sabrán quienes pasaron por el sitio del Google Code Jam el problema planteado debe ser resuelto para dos conjuntos de soluciones un conjunto pequeño y un conjunto grande, el tiempo entre la descarga del conjunto de prueba y la remisión de la solución es de 4 y 8 minutos respectivamente.
La idea detrás de este mecanismo es que un algoritmo que resuelva el problema pueda ser probado sin mayores optimizaciones con el conjunto de prueba pequeño que, usualmente, tiene restricciones en el rango de los datos de entrada no solamente en el número de casos. Y luego, en un segundo paso se pueda optimizar el mismo algoritmo para procesar el conjunto de prueba grande que contendrá un número mayor de casos y estará compuesto por valores también mucho más grandes. Para descargar los conjuntos de prueba y remitir sus soluciones pueden acceder a la página de la competencia.
Nuevamente, espero que se animen a resolver este problemita. Utilizando fuerza bruta se puede resolver para el caso de prueba pequeño y para el caso grande se puede utilizar alguna heurística o una estructura como un árbol. En cualquier caso, no se olviden de comentar como les fue.
19 jul 2008
Salvando el universo
Salvando el universo, es el título del primer problema propuesto en la ronda de calificación del Google Code Jam de este año, esta ronda culminó el día jueves 18 a las 06:00 p.m. con un total de 6773 clasificados (25 puntos como mínimo). El número total de participantes que remitieron al menos una respuesta correcta (5 puntos) fue de 7154.
El primer lugar lo obtuvo el participante cuyo nick es rem al totalizar 75 puntos en una hora con 18 minutos, la respuesta más rápida también fue de rem y fue remitida en tan solo 9 minutos con 16 segundos... increíble!!
Bueno, bueno.... basta ya de tantas estadísticas, el problema en cuestión se encuentra traducido líneas abajo, si eres un entusiasta de la programación seguramente intentarás resolverlo (obviamente, para salvar el universo) en tal caso espero un comentario tuyo en el que me cuentes como te fué.
EL PROBLEMA
Una leyenda urbana cuenta que si accedes a la página principal de Google y realizas la búsqueda de la palabra "Google", el universo se autodestruirá. Tenemos un secreto que compartir contigo... es cierto!. Por favor no lo intentes y no le digas a nadie. Muy bien, tal vez no. Solamente estamos bromeando.
Lo mismo no es muy cierto para un universo muy pero muy lejano. En aquel universo, si realizas una búsqueda en un motor de búsqueda por su propio nombre, aquel universo se autodestruirá.
Para evitar esto, se ha ideado una solución interesante. Todas las consultas realizadas en aquel universo serán combinadas y transmitidas a un sistema central que decidirá cual de las consultas se realizarán en cual motor de búsqueda. El sistema central enviará una serie de consultas a un motor de búsqueda, y puede cambiar de motor de búsqueda cuando sea necesario. Las consultas serán procesdas en el orden que son recibidas. El sistema central nunca deberá enviar una consulta a un motor de búsqueda que coincida con su nombres. Para reducir los costos el número de cambios de motor de búsqueda debe ser minimizado.
Tu tarea es indicarnos cuántas veces deberá cambiar de motor de búsqueda el sistema central, asumiendo que lo programamos de manera óptima.
ENTRADA
La primera línea del archivo de entrada contiene el número de casos, N. N casos siguientes.
Cada caso inicia con un número S -- el número de motores de búsqueda. Cada una de las siguientes S líneas contienen el nombre de un motor de búsqueda. El nombre cada motor de búsqueda no puede ser mayor a cien caracteres y contendrá solamente letras mayúsculas, minúsculas, espacios y números. No habrán dos motores de búsqueda con el mismo nombre.
La siguiente línea contiene un número Q -- el número de consultas de entrada. Las siguientes Q líneas contendrá cada una una consulta. Cada consulta será el nombre de un motor de búsqueda en el caso actual.
SALIDA
Para cada caso de entrada, la salida debe ser:
Case #X: Y
donde X es el número de casos de prueba e Y es el número de cambios de motor de búsqueda. No cuente la elección inicial de un motor de búsqueda como un cambio.
EJEMPLO:
Entrada
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol
Salida
Case #1: 1
Case #2: 0
En el primer caso, una posible solución es iniciar utilizando el motor Dont Ask, y cambiar a NSM luego de la consulta número 8.
Para el segundo caso, se puede utilizar B9, y no se requiere realizar ningún cambio.
El primer lugar lo obtuvo el participante cuyo nick es rem al totalizar 75 puntos en una hora con 18 minutos, la respuesta más rápida también fue de rem y fue remitida en tan solo 9 minutos con 16 segundos... increíble!!
Bueno, bueno.... basta ya de tantas estadísticas, el problema en cuestión se encuentra traducido líneas abajo, si eres un entusiasta de la programación seguramente intentarás resolverlo (obviamente, para salvar el universo) en tal caso espero un comentario tuyo en el que me cuentes como te fué.
EL PROBLEMA
Una leyenda urbana cuenta que si accedes a la página principal de Google y realizas la búsqueda de la palabra "Google", el universo se autodestruirá. Tenemos un secreto que compartir contigo... es cierto!. Por favor no lo intentes y no le digas a nadie. Muy bien, tal vez no. Solamente estamos bromeando.
Lo mismo no es muy cierto para un universo muy pero muy lejano. En aquel universo, si realizas una búsqueda en un motor de búsqueda por su propio nombre, aquel universo se autodestruirá.
Para evitar esto, se ha ideado una solución interesante. Todas las consultas realizadas en aquel universo serán combinadas y transmitidas a un sistema central que decidirá cual de las consultas se realizarán en cual motor de búsqueda. El sistema central enviará una serie de consultas a un motor de búsqueda, y puede cambiar de motor de búsqueda cuando sea necesario. Las consultas serán procesdas en el orden que son recibidas. El sistema central nunca deberá enviar una consulta a un motor de búsqueda que coincida con su nombres. Para reducir los costos el número de cambios de motor de búsqueda debe ser minimizado.
Tu tarea es indicarnos cuántas veces deberá cambiar de motor de búsqueda el sistema central, asumiendo que lo programamos de manera óptima.
ENTRADA
La primera línea del archivo de entrada contiene el número de casos, N. N casos siguientes.
Cada caso inicia con un número S -- el número de motores de búsqueda. Cada una de las siguientes S líneas contienen el nombre de un motor de búsqueda. El nombre cada motor de búsqueda no puede ser mayor a cien caracteres y contendrá solamente letras mayúsculas, minúsculas, espacios y números. No habrán dos motores de búsqueda con el mismo nombre.
La siguiente línea contiene un número Q -- el número de consultas de entrada. Las siguientes Q líneas contendrá cada una una consulta. Cada consulta será el nombre de un motor de búsqueda en el caso actual.
SALIDA
Para cada caso de entrada, la salida debe ser:
Case #X: Y
donde X es el número de casos de prueba e Y es el número de cambios de motor de búsqueda. No cuente la elección inicial de un motor de búsqueda como un cambio.
EJEMPLO:
Entrada
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol
Salida
Case #1: 1
Case #2: 0
En el primer caso, una posible solución es iniciar utilizando el motor Dont Ask, y cambiar a NSM luego de la consulta número 8.
Para el segundo caso, se puede utilizar B9, y no se requiere realizar ningún cambio.
9 jul 2008
Google Code Jam
El Google Code Jam, es un concurso de programación en el que cualquiera que tenga conocimientos de programación puede participar. Este año la primera ronda inicia el 16de julio y tendrá una duración de 24 horas durante las cuales será posible remitir la solución de los problemas que serán publicados, el cronograma detallado se encuentra aquí. Para participar debes inscribirte en la página del concurso con tu cuenta de GMail, si no tienes una cuenta de GMail, mmm... no, no creo que no tengas una cuenta de GMail.
Para ir calentando el ambiente, se han publicado algunos problemas para tomarlos como referencia, obviamente, la página del concurso, los problemas, las instrucciones y demás se encuentran en inglés. Por si no te va muy bien con el inglés (mmm... digamos mejor que estoy seguro que puedes traducir pero no tan rápido...), me tomé unos minutos para traducir uno de los problemas el cual puedes encontrar aquí.
Dale una mirada, plantéalo e intenta resolverlo para ello puedes utilizar el lenguaje de programación o herramienta de tu preferencia. Finalmente, animarte a que te inscribas en este concurso y demuéstres tus habilidades de programador, el primer premio es de US$10,000 y la experiencia será de hecho muy interesante.
Para ir calentando el ambiente, se han publicado algunos problemas para tomarlos como referencia, obviamente, la página del concurso, los problemas, las instrucciones y demás se encuentran en inglés. Por si no te va muy bien con el inglés (mmm... digamos mejor que estoy seguro que puedes traducir pero no tan rápido...), me tomé unos minutos para traducir uno de los problemas el cual puedes encontrar aquí.
Dale una mirada, plantéalo e intenta resolverlo para ello puedes utilizar el lenguaje de programación o herramienta de tu preferencia. Finalmente, animarte a que te inscribas en este concurso y demuéstres tus habilidades de programador, el primer premio es de US$10,000 y la experiencia será de hecho muy interesante.
28 jun 2008
Un laberinto
Te encuentras parado afuera de un laberinto perfecto. Un laberinto se denomina "perfecto" si cumple las siguientes condiciones:
La ruta que tomas a través del laberinto puede ser descrita con tres caracteres: 'W' significa caminar hacia delante hacia la siguiente habitación, 'L' significa voltear 90 grados a la izquierda (o en sentido antihorario), y 'R' significa voltear 90 grados a la derecha (o en sentido horario).
Inicias directamente fuera de la entrada, de frente al laberinto. Finalizas cuando has salido fuera del laberinto a través de la salida.
Problema
Por ejemplo si la entrada esta en el norte y la salida en el oeste, tu ruta de salida a través del laberinto mostrado sería
Si la entrada y la salida fueran invertidas, de modo tal que iniciaras fuera de la pared este y finalizaras fuera de la pared norte, tu ruta sería:
Dadas lass dos rutas a través del laberinto (entrada hacia salida y salida hacia entrada), tu código debe retornar una descripción del laberinto.
Entrada
La primera línea de la entrada provee el número de casos, N. Siguen los N casos de prueba. Cada caso es una línea con el formato:
Todas las rutas tendrán al menos dos caracteres de largo, compuestas solamente por los caracteres 'W', 'L', y 'R', y empezando y finalizando en 'W'.
Salida
Para cada caso de prueba, la salida debe mostrar una línea "Case #x:" por sí misma. Las siguientes F lineas (R lines) otorgan una descripción del laberinto F x C (R by C).
Cada línea debe tener C caracteres, cada uno representa las direcciones en las cuales es posible acceder a esa habitación. Vea la siguiente leyenda:
Limites
1 ≤ N ≤ 100.
Conjunto de datos pequeño
2 ≤ longitud(entrada_a_salida) ≤ 100,
2 ≤ longitud(salida_a_entrada) ≤ 100.
Conjunto de datos grande
2 ≤ longitud(entrada_a_salida) ≤ 10000,
2 ≤ longitud(salida_a_entrada) ≤ 10000.
Ejemplo
Entrada
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW
Salida
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3
- Esta compuesto por una malla rectangular de habitaciones, F filas por C columnas (R rows by C columns).
- Tiene exactamente dos salidas hacia fuera del laberinto: la entrada y la salida. La entrada esta siempre en la pared norte, mientras que la salida puede estar en cualquier pared.
- Existe exactamente una ruta entre dos habitaciones cualesquiera en el laberinto(esto es, exactamente una ruta que no involucre un retroceso).
La ruta que tomas a través del laberinto puede ser descrita con tres caracteres: 'W' significa caminar hacia delante hacia la siguiente habitación, 'L' significa voltear 90 grados a la izquierda (o en sentido antihorario), y 'R' significa voltear 90 grados a la derecha (o en sentido horario).
Inicias directamente fuera de la entrada, de frente al laberinto. Finalizas cuando has salido fuera del laberinto a través de la salida.
Problema
Por ejemplo si la entrada esta en el norte y la salida en el oeste, tu ruta de salida a través del laberinto mostrado sería
WRWWLWWLWWLWLWRRWRWWWRWWRWLW
Si la entrada y la salida fueran invertidas, de modo tal que iniciaras fuera de la pared este y finalizaras fuera de la pared norte, tu ruta sería:
WWRRWLWLWWLWWLWWRWWRWWLW
Dadas lass dos rutas a través del laberinto (entrada hacia salida y salida hacia entrada), tu código debe retornar una descripción del laberinto.
Entrada
La primera línea de la entrada provee el número de casos, N. Siguen los N casos de prueba. Cada caso es una línea con el formato:
entrada_a_salida salida_a_entrada
Todas las rutas tendrán al menos dos caracteres de largo, compuestas solamente por los caracteres 'W', 'L', y 'R', y empezando y finalizando en 'W'.
Salida
Para cada caso de prueba, la salida debe mostrar una línea "Case #x:" por sí misma. Las siguientes F lineas (R lines) otorgan una descripción del laberinto F x C (R by C).
Cada línea debe tener C caracteres, cada uno representa las direcciones en las cuales es posible acceder a esa habitación. Vea la siguiente leyenda:
| Caracter | Norte? | Sur? | Oeste? | Este? |
|---|---|---|---|---|
| 1 | Sí | No | No | No |
| 2 | No | Sí | No | No |
| 3 | Sí | Sí | No | No |
| 4 | No | No | Sí | No |
| 5 | Sí | No | Sí | No |
| 6 | No | Sí | Sí | No |
| 7 | Sí | Sí | Sí | No |
| 8 | No | No | No | Sí |
| 9 | Sí | No | No | Sí |
| a | No | Sí | No | Sí |
| b | Sí | Sí | No | Sí |
| c | No | No | Sí | Sí |
| d | Sí | No | Sí | Sí |
| e | No | Sí | Sí | Sí |
| f | Sí | Sí | Sí | Sí |
Limites
1 ≤ N ≤ 100.
Conjunto de datos pequeño
2 ≤ longitud(entrada_a_salida) ≤ 100,
2 ≤ longitud(salida_a_entrada) ≤ 100.
Conjunto de datos grande
2 ≤ longitud(entrada_a_salida) ≤ 10000,
2 ≤ longitud(salida_a_entrada) ≤ 10000.
Ejemplo
Entrada
2
WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW
Salida
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3
Suscribirse a:
Entradas (Atom)