Category Archives: Google

Vencido por un par de alfombras

logo_CodeJamEurope.gif

Hoy era el tan esperado Google Code Jam, lo estaba esperando con bastantes ganas desde hace unos días y despues de volver de la rutina diaria, me he puesto a intentar resolver los problemas que te planteaban (dos, uno de 500ptos. y otro de 250ptos.) en un tiempo de 60minutos.
Al entrar te indicaban la sala que te correspondía (había 30 con unos 50-60 participantes, es decir unos 1500 en total así aproximadamente), con lo cual se evitarían (más o menos…) de posibles lammers que hubiesen registrado dos cuentas para entrar, ver los problemas, resolverlos con tiempo y luego entrar con otra cuenta (lo cual no apruebo :P, prefiero caer con honor que pasar haciendo trampas). Veo las puntuaciones de mi sala (así a ojo quedandote entre los 15 primeros te asegurabas pasar) y compruebo que eran relativamente bajas en general (con hacer 1pto, te ponías el 12º), como suponía que aún faltaría mucha gente de participar y veo que haciendo el segundo (el dificil) conseguiría ponerme entre los 5primeros aprox.(todo depende del tiempo…y no se, si de lo optimo que lo hicieras), así que todo afanoso abro el primer problema

Problema de los 500ptos, dado un entero ‘n’ que corresponda con la longitud de una cadena compuesta por A’s y B’s, cuenta el número total de cadenas posibles que se pueden formar que no tengan más de ‘w’ subcadenas invertibles (por ejemplo, BA invertible en AB). Realmente era algo más complejo, pero no me aclaraba y he empezado a pensar en la representación como binario de las cadenas (te dicen A y B, pero te podías representarlo con 0 y 1, y por lo tanto operar como un numero la cadena total) y despues de estar 20minutos y ver que a los 20minutos estaba igual que hace 10minutos, he decidido dejarlo e ir a por el otro problema. 🙁 Estaba pensando más en el tiempo que en el propio problema realmente…
El segundo problema, (de 250ptos, más facil) iba de alfombras, te daban las medidas de una habitación y tenías que dar las posibles posiciones de poner un par de alfombras con unas restricciones concretas:

  • No se podían solapar
  • Un lado de la alfombra no podía ser dos veces mayor que el otro
  • Se debía dejar, al menos, una unidad cuadrada libre de parqué, representaría la entrada de la habitacion
  • El par de alfombras podían ser de cualquier tipo de medidas, diferentes, iguales…
  • SOLO DEBÍA DE HABER UN HUECO

El último punto lo pongo en mayusculas, porque como estaba al final del todo, yo agil cual gorrión, no lo he leido hasta despues de ponerme como un cosaco a programar sin parar. Termino el caso y cuando voy a hacer las pruebas veo que los casos grandes no me salían (salían muchos más), y repasando el enunciado (por si algo lo había traducido mal…) veo que no había leido esa restricción. Despues de buscar un cuchillo para el suicidio y como debería de levantarme e ir a la cocina para ello, me pongo a intentar arreglar la cosa como sea, quedaban 5min y el contador iba bajando. No me ha dado tiempo :(. Si hubiese perdido algo más de tiempo leyendo atentamente este segundo problema hubiese podido completarlo a tiempo. Mala suerte y poca sangre fria he tenido :-/, no pasa nada, ha sido una hora muy divertida :), para el proximo año espero que lo hagan de nuevo! ahí estaré :). Espero que otros que participaban hayan tenido más suerte.