weblogs : arhuaco : Primera ronda del Code Jam 2009

Después de la clasificación al Code Jam 2009 estaba pesimista y creo que esta vez tuve suerte porque logré enviar la solución fácil (pequeña) del problema A en 33.67 minutos y esos 9 puntos parecen ser suficientes para pasar a la siguiente ronda (puesto 855 entre los 1000 que pasaron).

Esta es la solución. Edité un poco para mejorar el programa pero no cambio mucho el algoritmo.

#!/usr/bin/python

import sys

def BN(num, base):
    ret = ''
    while num:
        ret = str(num % base) + ret
        num /= base
    return ret

know = {}

def happy(n, base):
  nn = n
  seen = set([n])
  while n != 1:
    if (n, base) in know:
      return know[(n, base)]
    sum = 0
    for d in BN(n, base):
      d = int(d)
      sum += d * d
    n = sum
    if n in seen:
      break
    seen.add(n)
  know[(nn, base)] = (n == 1)
  return n == 1

def solve(b):
  n = 2
  while True:
    for i in b:
      if not happy(n, i):
        break
    else:
      return n
    n += 1

f = open(sys.argv[1])
NTEST =  int(f.readline())
for i in xrange(NTEST):
  print ('Case #%d:' % (i + 1)),
  print solve(map(int, f.readline().strip().split()))

Lo mejor es calcular la suma de una vez. Debí escribir algo así:

def BN(num, base):
    sum = 0
    while num:
        tmp = num % base
        sum += tmp * tmp
        num /= base
    return sum

Será interesante ver que optimización se puede hacer para computar rápido ya que esta solución no logra completar a tiempo la entrada grande.

Demoré unos minutos (unos 25 creo) entendiendo bien el problema B y probando cosas en tablero. Vi una estrategia pero no parecía fácil de programar en el tiempo que quedaba. Tal vez la pruebe luego.

Decidí intentar el problema C pero no logré ver la solución (de la entrada pequeña) en la hora y un poco más que quedaba. Es interesante ese problema. Luego estudio la solución leyendo código ajeno.

Cuando quedaba media hora decidí esperar y ya no pensé mucho en el problema C.

En la siguiente ronda solo pasan 500 personas de 3000. Estudiaré para quedar lo más lejos posible del último pero realmente no espero pasar.

No tengo un nivel competitivo y al pasar a la segunda ronda ya siento que gano medalla de oro :-) No estoy dispuesto a invertir el tiempo necesario para ser muy competitivo en esto. Cada vez es más difícil mejorar.

Loading... Discussion

• codejam