El comentario de anonimo en mi post anterior me ha descubierto una cosa que no conocía: la Programación Competitiva. Yo pensaba que esto era un invento de Google pero resulta que ya estaba inventado. Un gran aporte. Muchas gracias. Le he estado dando bastantes vueltas y he decidido mantener mi mente "virgen" porque lo que me interesa es saber hasta donde puedo llegar con mis limitaciones actuales, no preparame para ganar un concurso. El año que viene ya veremos si opino lo mismo. |
![]() |
Round 1A
Gracias a un "papá miedo" tuve la "suerte" de despertarme a las 3 de la mañana así que aproveché para ver los tres problemas y hacerme una idea de la dificultad. Vi asequibles tanto el "Problem A. Charging Chaos" como el "Problem B. Full Binary Tree" pero el "Problem C. Proper Shuffle" era más difícil.
Al día siguiente vi que el corte estaba en hacer los dos primeros problemas sin cometer equivocaciones así que tomé nota para la siguiente.
Round 1B
Tras haber solicitado el correspondiente permiso marital para poder pasar la tarde frente al ordenador empiezo por el primer problema.Problem A. The Repeater
Lo que nos piden
En el primer problema nos piden cual es el número mínimo de pasos necesarios para igualar varias cadenas de texto cadenas de texto siguiendo dos reglas:
- Si hay dos caracteres consecutivos iguales se puede eliminar uno de los dos.
- Si hay un caracter se puede duplicar.
Por ejemplo, si tenemos la cadena "aaabcc" y queremos llegar a "abbbcc" tenemos que pasar por "aabcc", "abcc" y "abbcc". ¿Fácil no?
Aquí tenemos unos ejemplos del concurso:
- Caso 1:
Cadenas:
- mmaw
- maw
- Caso 2:
Cadenas:
- gcj
- cj
- Caso 3:
Cadenas:
- aaabbb
- ab
- aabb
- Caso 4:
Cadenas:
- abc
- abc
- Caso 5:
Cadenas:
- aabc
- abbc
- abcc
La solución
La solución consiste en primero comprobar si el problema tiene solución y en caso de tenerla averiguar cuantos pasos son necesarios para llegar desde una cadena a la otra. Si has hecho este problema probablemente esto te sonará un poco raro pero me explicaré más adelante.
#!/usr/bin/python # -*- coding: utf-8 -*- import sys import time def getValue(inputFile,dataType="string"): line="" value=0 while len(line)< 1: line=inputFile.readline() if dataType=="string": value=line.split()[0] elif dataType=="integer": value=int(line.split()[0]) elif dataType=="float": value=float(line.split()[0]) return value def reducedCase(case): char="" reduced="" i=0 while i< len(case): if not(char==case[i]): char=case[i] reduced=reduced+char i=i+1 return reduced def testPossible(cases): # For each case test if removing duplicates make them the same reduced=reducedCase(cases[0][0]) possible=1 i=1 while i< len(cases) and possible==1: if not(reduced==reducedCase(cases[i][0])): possible=0 i=i+1 return possible def convert(case1, case2): # Try to find the number of steps to translate case1 to case2 steps=0 diff=0 i=0 j=0 char=case1[0] while i< len(case1) and j< len(case2): found=0 while i< len(case1) and found==0: if char==case1[i]: i=i+1 else: found=1 found=0 while j< len(case2) and found==0: if char==case2[j]: j=j+1 else: found=1 steps=steps+abs(i-j-diff) diff=abs(i-j) if i< len(case1): char=case1[i] return steps ### solve it! ### def solveIt(cases): res=1 # Reducir duplicados en todos y comprobar que sale la misma cadena para ver si # es posible resolverlo possible=testPossible(cases) if possible==1: i=1 while i< len(cases): #Elegir uno como plantilla e igualar el resto. steps=convert(cases[0][0],cases[i][0]) cases[i][1]=steps i=i+1 res=0 for case in cases: if case[1]>res: res=case[1] else: res=-1 return res if __name__=='__main__': # Open input and output files inputFile=open(sys.argv[1],'r') outputFile=open(sys.argv[2],'w') # Get number of cases NoC=int(getValue(inputFile)) # for each case for i in range(NoC): # get case data inputs=getValue(inputFile,"integer") cases=[] while inputs>0: case=getValue(inputFile,"string") cases.append([case,-1]) inputs=inputs-1 # solve problem res=solveIt(cases) # write data if res==-1: outputFile.write("Case #"+str(i+1)+": Fegla Won\n") print "Case #"+str(i+1)+": Fegla Won" else: outputFile.write("Case #"+str(i+1)+": "+str(res)+"\n") print "Case #"+str(i+1)+": "+str(res) # Close input and output files inputFile.close() outputFile.close()
Resultados
En el ejemplo que viene la entrada es:
5 2 mmaw maw 2 gcj cj 3 aaabbb ab aabb 2 abc abc 3 aabc abbc abcc
Y la salida correcta es:
Case #1: 1 Case #2: Fegla Won Case #3: 4 Case #4: 0 Case #5: 3
Sin embargo a mi me sale mal el último resultado y me empiezo a poner nervioso:
Case #1: 1 Case #2: Fegla Won Case #3: 4 Case #4: 0 Case #5: 2
19:45
"La cagamos Luis"
... dijo Carlos Sainz cuando se enteró de que su motor llevaba estando defectuoso desde la salida.
Resuelvo el problema que he descrito pero no el que me piden y a estas horas ya no me da tiempo a rectificar.
Para resolver el problema hay que tener en cuenta todas las cadenas simultáneamente y yo las he tenido en cuenta de una en una
En el último caso yo obtengo como resultado 2 porque aabc->abc->abbc y aabc->abc->abcc . Así que como mucho necesito dos pasos pero lo que en realidad hay que hacer entiendo es pasar a la vez todas las cadenas a una sóla de esta forma:
["aabc","abbc"]->["abc","abbc"]->["abc","abc"]->["abcc","abcc"]Y de ahí salen los tres pasos.
No tengo tiempo para volver a rediseñar el programa así que se acabó esta ronda para mí.
¿Round 1C?
"En habiendo agotado" todos los permisos maritales que tenía para el Google Code Jam, me tengo que retirar de esta convocatoria así que ya veremos el año que viene si aprendo a leer.
Creo que me tendré que conformar con presentarme al Tuenti Challenge 4 y acabar mi curso de mongodb para desarrolladores y mi curso de mongodb para administradores avanzados.