Ronda 1ª-3: Cola en el parking

Enunciado original

Nos van a proponer una serie de tableros rectangulares con una serie de celdas prohibidas y tendremos que calcular el mayor número de celdas que podemos concatenar, comenzando desde la superior izquierda. Las condiciones: no podemos pasar dos veces por la misma celda (obvio), no podemos pasar por las celdas prohibidas, nos podemos mover sólo hacia la derecha y hacia abajo excepto una vez que podemos ir, en un tramo recto, hacia la izquierda o hacia arriba.

La primera idea que se nos viene en la mente es comenzar en la celda inicial e ir simulando los movimientos posibles para avanzar una celda y hacer lo mismo en la siguiente y así sucesivamente. Ir contando los movimientos y encontrar el máximo de celdas que podemos ocupar.

Pero hay que pensar un poco: en cada celda podemos elegir desde dos hasta cuatro movimientos posibles. Si elevamos 2 (ya no pensemos en 4) a las casillas del tablero máximo (500x500=250.000) es fácil ver que las posibilidades son inabordables.

Vamos a olvidarnos por un momento de que tenemos la posibilidad de volver una vez hacia la izquierda o hacia arriba y pensemos en que sólo podemos movernos a la derecha y hacia abajo.

Es evidente que no podemos pasar dos veces por una misma casilla porque vamos siempre en la misma dirección, así que por esa limitación no debemos preocuparnos. ¿Cómo saber cuántas casillas podemos ocupar?

Es simple, comenzamos colocando un uno en la celda superior izquierda y vamos recorriendo todas las celdas guardando en cada una de ellas uno más que el valor de la celda de la derecha o el de la celda de arriba (el mayor de ambos) siempre que alguna de las celdas esté permitida. Si las dos celdas están prohibidas colocaremos un cero que significará que a esa celda no se puede llegar desde la celda inicial yendo siempre a la derecha y a abajo. Estos cálculos los podemos ir haciendo conforme leemos los datos de entrada del problema y los guardamos en la variable order.

Esta variable contendrá el número de personas que contendrá la fila desde la posición inicial cuando pase por esta celda. Las celdas con valor cero son inaccesibles. Todo esto con un sólo bucle doble anidado que necesitamos, además, para leer los valores de entrada.

Ahora podemos pensar que desde cada celda podemos hacer un, y sólo uno, movimiento hacia arriba o hacia la izquierda.

Para no pasar dos veces por la misma celda, un movimiento hacia arriba desde una celda supone mover una celda hacia la derecha, luego varias hacia arriba y al final una a la derecha y desde allí hasta el final ya siempre en la misma dirección. Análogamente hacia la izquierda moveríamos uno hacia abajo, varias a la izquierda y uno hacia abajo.

Pensando así nos damos cuenta que sería bueno tener en cada celda la información de cuántas personas nos caben en la fila desde esa casilla hasta el final del tablero como máximo. Es una información parecida a la que ya tenemos calculada en la variable order, pero no es igual en primer lugar porque necesitaríamos también la información en las celdas en las que no se puedan acceder desde la casilla inicial porque pueden ser accesibles tras el movimiento hacia atrás. ¿Cómo lo hacemos?

En realidad es simple: comenzamos desde el final y vamos yendo hacia atrás. Es evidente que la celda desde la que no se puede ir a ninguna es la inferior derecha, así que comenzaríamos poniendo un uno en esa celda (si está permitida) porque desde esa celda sólo cabe una persona. Desde ahí vamos retrocediendo en la fila y después lo mismo en las filas hacia arriba. En cada celda, si está permitida ponemos uno más que el valor mayor de la celda de abajo o de la celda de la derecha (si están permitidas). Si ambas estuvieran prohibidas pondríamos uno. Así en cada celda obtendríamos el número de personas que caben en la fila a partir de esa celda.

Lo guardamos en la variable gap. Necesitaremos un segundo bucle doble.

El valor que obtengamos en la primera celda sería el número de personas que caben en la fila yendo siempre en la misma dirección y será el valor máximo de la variable order. Este es el valor que como mínimo caben en el tablero, así que inicializamos la variable p a ese valor y vamos a ir buscando valores mayores si gastamos el movimiento de retroceso en cada casilla.

Las personas totales en cada caso será el valor order de la casilla que estemos evaluando (que son el número de personas que hay hasta esa casilla) más las casillas que tenga el movimiento de retroceso más el valor de la variable gap de la celda donde termina el movimiento de retroceso (que son las personas que caben desde esta celda). Si el valor es mayor que el máximo que tenemos guardado hasta el momento en la variable p lo cambiamos. El movimiento de retroceso terminará, como muy tarde, cuando lleguemos al extremo del tablero o cuando topemos con una celda prohibida.

Este cálculo es otra bucle aunque en este caso sea triple.

En resumen las iteraciones calculando de esta forma son infinitamente menores que con el método de fuerza bruta.

Finalmente para que desde una casilla se pueda hacer un movimiento de retorno hacia arriba la celda no puede estar en la primera fila y tenemos que tener, como mínimo, dos columnas libres a la derecha. Análogamente para el movimiento de retroceso a la izquierda. Y, por supuesto, sólo podemos pensar en hacer un movimiento de retroceso desde una celda que sea alcanzable desde la celda inicial, es decir, aquellas celdas en que order sea mayor que cero.

He elegido guardar en la variable gap el valor -1 para las celdas prohibidas.

Y, en realidad, eso es todo. Como se puede ver en el programa completo es más fácil verlo escrito en C++ que explicado en español. Aquí está el fichero de datos propuesto en el concurso.

Ronda 1ª-2: Juego de monedas

Enunciado original

En resumen el problema trata de lo siguiente: tenemos un número de monedas (K) que podemos distribuir en una cantidad de botes (N) de la manera que queramos. Sabiendo cuántas monedas metimos en cada bote pero sin saber en qué botes las metimos se trata de saber el número mínimo de veces que tendremos que meter la mano en los botes (P) para sacar una cantidad de monedas (C) obviamente menor que la cantidad de monedas totales. A este problema se le asignaron 20 puntos. Es también un problema sencillo y en el que prácticamente con la explicación de los ejemplos te dan muchas pistas sobre la estrategia a seguir.

El número de movivimientos (P) serán la suma de los movimientos correctos, o sea en los que encontremos moneda en el bote, que serán C, es decir las monedas a sacar, más los movimientos incorrectos, o sea en los que no encontremos moneda en el bote.

Así que se trata de minimizar el número de veces que podemos fallar.

Podremos fallar tantas veces como botes haya con menos monedas que el que más tenga porque no vamos a fallar más de una vez en cada bote ni vamos a intentar sacar más monedas de un bote que las que hay en el bote que más tenga. Así que la idea es dejar el mayor número de botes con las mismas monedas (en estos botes no fallaremos nunca) y unos pocos con menos.

Se pueden seguir muchas estrategias pero la que yo elegí es repartir las monedas entre los botes (r=K/N). Recordad que en la división de enteros r*N<=K, es decir no redondea el resultado sino que lo trunca. Es lo mismo que si hiciéramos la división a mano, vamos.

Si meto r*N>=C puedo meter r o más monedas en cada bote y al sacarlas no fallar nunca porque en cuanto sacase r monedas de un bote pasaría al siguiente. En este caso, como el número de fallos es cero, el número de movimientos es igual al número de monedas a sacar (C).

Si no tengo tantas monedas la mejor solución es meter en cada bote r+1 monedas. El número de botes que puedo llenar con r+1 monedas será K/(r+1). Estos serán los botes en los que no fallo, así que podré fallar en los restantes botes. Así que el número de movimientos será C+(N-K/(r+1)).

Como se ve un problema más de lógica que de programación.

Alguien, al leer la anterior argumentación, podría objetar que si el resto de la división K/N fuera cero no sería bueno repartir r+1 monedas en cada bote sino r, y estaría en lo cierto. Lo que ocurre es que si el resto de la división es cero r*N=K y como K>=C entonces r*N>=C y estaríamos en el primer caso contemplado.

Aunque sea extremadamente simple aquí está el listado completo del programa y aquí el fichero de datos propuesto en el concurso.

Ronda 1ª-1: El etiquetador loco

Enunciado original.

El problema de menos valor de la ronda (15 puntos) y el más simple de los cuatro. Con unas matemáticas detrás de él muy asequibles y un algoritmo sencillo.

Por si alguno lo ha pensado es inviable ir simulando todas las etiquetas y contándolas hasta que lleguemos a la cantidad pedida. 2⁶³ es un número increíblemente grande como para pensar en contarlo.
Un número tan grande que necesitamos un tipo de datos especial. El último de los llegados a los lenguajes C, hasta el momento, en la categoría de enteros.
Aprovechemos la excusa para repasar estos tipos que son la base de la programación. Hay que pensar que en el ordenador la memoria se organiza en celdas en las que se guardan enteros y con ellos se modelan todos los tipos de datos. Incluso los primeros microprocesadores, allá en la época que comencé a programar cuando tenían 8 bits (y algunos 4), sólo podían hacer operaciones con enteros. Las operaciones con reales se realizaban mediante llamadas a librerías que hacían infinidad de operaciones con enteros. Afortunadamente teníamos ya los compiladores que se ocupaban de estos detalles (como ahora).

Tipos de datos enteros

Los tipos de datos enteros normales que podemos manejar en C++ son: char, short, int, long y, el que necesitaremos para este problema, el long long, que como su propio nombre indica es muy largo.

Podemos encontrarnos el tipo long especificado a veces como long int para recordarnos que es un tipo mayor que el simple int. Como a mí no me gusta escribir de más jamás empleo esta forma de escribir el tipo.

Esperamos encontrar que el tipo char ocupa 8 bits, los tipos short e int ocupan 16, el tipo long 32 y el gigante de los tipos, el long long, 64 bits. Pero cada compilador para cada procesador y en cada sistema operativo pueden asignar distintos tamaños para estos tipos, aunque los valores indicados aquí son valores mínimos que vamos a encontrar, es decir, cuando especificamos una variable int sabemos que como mínimo tendremos 16 bits disponibles, aunque en la actualidad muchos compiladores reservan 32 bits para este tipo.

Otra cosa que tenemos seguro es que el tamaño de los tipos sigue el orden especificado en la lista, es decir, el tipo short no puede ser más grande que el int.

Los números negativos se representan con el bit de mayor peso a uno y los positivos a cero, por lo tanto tenemos disponibles un bit menos para representar el valor absoluto del dato. Así si un dato ocupa 16 bits nos quedaran 15 para especificar el número sin el signo. Es decir, en este caso se pueden almacenar valores desde -2¹⁵ (-32768) hasta 2¹⁵-1 (+32767). ¿Por qué llegamos más lejos con los números negativos que con los positivos? No porque el ordenador sepa que estamos la mayor parte del tiempo en números rojos en nuestra cuenta sino porque el cero nos ocupa una posición entre los positivos.

En los tiempos en los que la memoria era un bien escaso se pensó que para muchas situaciones sólo necesitamos números positivos y era un desperdicio enorme perder 1 bit de memoria en cada posición. Así que se habilitó el prefijo unsigned que se puede anteponer a todos los tipos para indicarle al compilador que ese tipo de datos no tiene números negativos y el bit de mayor peso no es el signo sino parte del valor. Con este truco, en el ejemplo anterior, aumentamos el número máximo que se puede almacenar hasta 65535 (entre 0 y 65535).
¿Por qué esta indeterminación en los tamaños? Supongo que será para aprovechar mejor las posibilidades del procesador para el que se compile el fuente. Si el procesador en el que se va a ejecutar el programa maneja igual o mejor los datos de 32 bits que los de 16 ¿por qué forzarnos a manejar datos más pequeños?
¿Puede ser un problema tener esta indeterminación en los tamaños? Seguramente en algunos casos sí. Para poder emplear toda la información del tamaño de cada tipo y los valores mínimo y máximo que pueden almacenar tenemos constantes definidas en el fichero de cabecera climits (limits.h para C) cuya definición se puede ver aquí.
En nuestro programa necesitaremos conocer el límite superior de las variables de tipo unsigned long long que  emplearemos para los cálculos. Lo obtendremos de la constante ULONGLONG_MAX.

Algoritmo

No creo necesario explicar que las cajas que podemos etiquetar de forma diferente con un conjunto de L letras usando n de ellas es de L^n (L elevado a n). Si alguien no se lo cree puede mirarlo aquí.

El algoritmo que emplearemos es el siguiente:

Tomaremos el número de cajas a etiquetar (N) y le restamos una, la caja de la cual queremos saber la etiqueta.

A continuación vamos calculando las permutaciones con repetición (que es el nombre más preciso de las combinaciones de etiquetas) de L elementos (las letras que funcionan en la etiquetadora) cogidos primero de una en una (L), luego de dos en dos (L²) y así sucesivamente y vamos restando del total de cajas cada cantidad hasta el número de letras (n) en que las cajas restantes sean menores que las combinaciones que se  generan con las letras tomadas de n en n.

En este punto ya sabemos cuántas letras tendrá la etiqueta de la última caja, pero ahora nos falta saber cuál será esa etiqueta.

Aunque ya tengamos muchas menos combinaciones sigue siendo inviable ir generando todas las combinaciones. Así que pensemos en otra forma de saberlo.

En realidad el procedimiento a seguir será muy parecido al descrito antes.
Veamos el primer carácter. Con cada carácter de la primera posición tenemos L^(n-1) combinaciones de los n-1 caracteres restantes. Así que si dividimos las N cajas cajas que quedan por etiquetar para esta cantidad obtendremos el índice del primer carácter de la etiqueta de la caja final comenzando la primera letra con el índice cero. El resto de esta división serán las cajas que quedarán cuando comencemos con la letra obtenida. Así que la segunda letra de la etiqueta repetiremos el mismo proceso tomando las cajas restantes igual al resto.

Programa

Comenzamos como siempre con el bucle para los casos y la lectura de datos. No vamos a entrar en más detalles.

Como hemos visto en el algoritmo vamos a necesitar dos bucles, pero antes necesitaremos unas operaciones previas:

for (m=0; L[m]!=0; m++);  // count good keys

v[0]=m; // 1-key combinations

n=0;

N--; // boxes except the last one

La primera instrucción en un bucle que no hace nada. Por eso el final de instrucción (;) detrás de la cabecera del bucle. ¿Pero realmente no hace nada? Evidentemente no. Va a contar los caracteres que tiene la cadena de caracteres leída en el array L (char L[120]). En C++ (como en C) las cadenas de caracteres terminan con el carácter especial \x0, o sea el carácter con valor ASCII cero.

Así el bucle va incrementando la variable entera m hasta que el carácter del array en la posición m-ésima es el carácter especial final de cadena. Hay que recalcar que es seguro que el carácter final de cadena se va a encontrar al final (siempre que el tamaño de la cadena no exceda la capacidad del array) por lo que no implementamos ningún control de error para el caso de que no estuviera este carácter. Observad también que la comparación está escrita como si el contenido del array L fueran enteros. Los tipos char y unsigned char tienen la dualidad de poder trabajar con ellos como caracteres o como enteros.

Como el primer carácter del array tiene índice cero, en m obtendremos el número de caracteres de la cadena, es decir, el número de letras buenas de la etiquetadora.

En las especificaciones se fija que el número máximo de letras de la etiquetadora será de 25, así que necesitaríamos un array de, como mínimo, 26 puesto que no hay que olvidar que el array debe poder almacenar el carácter cero (a veces llamado nulo) de final de cadena. ¿Por qué lo dimensioné de 120? Ni idea. seguramente porque como me sobra la memoria...

A continuación inicializo el primer elemento del array v de tipo unsigned long long al valor m. Como se ve en la descripción del algoritmo vamos a necesitar las potencias del número de letras de la etiquetadora en los dos bucles, así que en lugar de calcularlas dos veces decidí calcularlas una sola y guardarlas en un array, es una cantidad irrisoria de memoria aunque también es un ahorro de tiempo ridículo en el programa el que nos reportará, puesto que nos ahorraremos una división por letra de la etiqueta final.

Las sucesivas potencias se calcularán multiplicando por m el valor de la potencia anterior. Es decir calcularemos m^n como m*m^(n-1). Si no guardásemos todas las potencias haríamos lo mismo y en el segundo bucle, que como vemos vamos necesitando las potencias de índice cada vez menor, lo calcularíamos como m^(n+1)/m.
La última inicialización es restar uno a las cajas para quitar la última, que es de la que queremos calcular la etiqueta, del cálculo. En realidad esta línea la añadí al final del programa. Esta es una de esas situaciones en las que dudas si con al algoritmo que has implementado deberías usar N o N-1 como dato. En vez de perder tiempo en pensar sobre ello te dejas una nota y, cuando pruebes el programa, si ves que el resultado que obtienes está desfasado en una unidad actúas en consecuencia. Es la gran ventaja de la programación como disciplina, te permite el método de ensayo y error que, por ejemplo, para un piloto aterrizando un avión no es recomendable.
Codifiquemos el primer bucle del algoritmo:

while (N>=v[n])  // how many keys we need
{
N-=v[n];  // boxes labeleds
v[n+1]=v[n]*m;  // variations with one more letter
n++;
}

Vamos restando a N las distintas potencias de m que equivalen al conjunto de cajas etiquetadas con las permutaciones de m elementos tomados de n en n. Usamos la potencia calculada en la iteración anterior y calculamos la potencia de la siguiente. Por ello el bucle termina en el momento que el valor de la potencia que vamos a emplear es mayor que el número de cajas restantes, lo que equivale a decir que es la cantidad de letras en la etiqueta cuyas permutaciones no vamos a terminar.
¿Es esta implementación correcta? Parece que sí y, de hecho, funcionará en la mayor parte de los casos, pero no en todos. Por lo tanto no es correcta. He de admitir que esta fue la versión del programa con la que me descargué el fichero de datos del concurso y que, por supuesto no me funcionó y tuve que modificar en los 6 minutos de la cuenta atrás. ¡Una locura de nervios!
¿Dónde está el fallo?
Es fácil ver que estamos calculando una potencia más de la que necesitamos puesto que es cuando calculamos esa potencia que se pasa del valor de N cuando nos damos cuenta que el bucle ha terminado. Con los límites del problema habíamos llegado a la correcta conclusión que todos los cálculos que tuvieran que ver con el número de cajas, como las potencias que vamos calculando, nos caben en una variable de tipo unsigned long long, por lo tanto la última potencia que empleemos sí cabrá en esta variable pero ¿alguien nos asegura que la siguiente potencia, la que va a ser mayor que el número de cajas, también va a caber? La respuesta es no. Puede haber casos en que esa siguiente potencia no quepa en tal variable y las retorcidas mentes del concurso lo encontraron y lo propusieron.
La dificultad era que como usé las opciones optimizadas del compilador, el programa no comprueba que el resultado de una operación sea mayor que el máximo por optimización del tiempo, en lugar de arrojar un error lo que hace es devolver un número erróneo y que no cumple con la condición de final de bucle, posponiendo el error. Afortunadamente, en mi compilador, el número que me devolvía el cálculo era cero, con lo que el resto de potencias valía cero, el bucle no terminaba nunca y obtenía un error de ejecución cuando comenzaba a escribir ceros más allá del límite del array v.
¿Qué se me ocurrió para resolverlo? Pues calcular el valor máximo del cual podría calcular la siguiente potencia así:

maxPot=ULLONG_MAX/m;

Es evidente que si multiplico este valor por m obtendré el máximo valor que cabe en una variable de tipo unsigned long long. Ahora antes de calcular la potencia para la siguiente iteración comparo con este valor. Si el valor de la potencia actual es mayor que este valor no necesitamos calcular la siguiente potencia porque el valor va a ser más grande que el número de cajas puesto que va a ser mayor que el máximo ULLONG_MAX.
Así el bucle quedaría:

maxPot=ULLONG_MAX/m;
while (N>=v[n])  // how many keys we need
{
N-=v[n];  // boxes labeleds
if (v[n]>maxPot)
{
n++; break;  // too big, must be last one
}
else
{
v[n+1]=v[n]*m;  // variations
n++;
}
}

Y ahora el bucle final. Vamos calculando la división entre las potencias que hemos guardado y los restos restando el producto del cociente por el divisor. En cada iteración escribimos ya la letra de la etiqueta que hemos calculado. Al final del bucle el resto que nos quede es el índice de la última letra de la etiqueta.

while (--n>=0)  // calculate last label (with n+1 letters)
{
int nk=(int) (N/v[n]);
cout << L[nk];
N-=nk*v[n];
}
cout << L[N] << endl;

Y no hay nada más que hacer. Como siempre aquí está el fuente del programa completo y aquí el fichero de datos que me propusieron en el concurso.

Facebook Hackercup 2014. Ronda primera

Comienza la parte estresante del concurso.

Esta fase tiene 24 horas de plazo para resolver cuatro problemas propuestos. El orden de clasificación el mismo de todo el concurso (explicado en esta entrada) y el objetivo para pasar a la siguiente ronda quedar empatado a puntos con el concursante que haya quedado en la posición 500 de la ronda.

Así que no puedes saber cuántos problemas debes resolver para clasificarte.

Aunque parezca una excusa, la fecha de celebración de la ronda me perjudicó (¿cómo no me preguntó la gente de Facebook si me venía bien?) porque se celebró el sábado 7 de diciembre. En España estaba entre los días 6 y 8 ambos festivos y, al coincidir el 8 en domingo, el lunes 9 también era festivo. ¿Así que cómo podía desaprovechar estos días y no salir de viaje? Pues no haciéndolo. Así que participé en esta ronda con un portátil con Windows Vista sin mis herramientas habituales de Linux, con una mala conexión de Internet, sin un sitio adecuado para concentrarme y con muchas ganas de pasear por el idílico paisaje que me tentaba a unos metros de la ventana...

El resultado sólo presenté bien los dos primeros problemas propuestos. En el tercero me lié la cabeza de una forma inexplicable y no sólo no lo presenté sino que gasté el tiempo que debía haber dedicado al cuarto que presenté con un error que no detecté.

En resumen: posición 971 con 35 puntos. Y fue una lástima porque el 500 clasificado tuvo 40 puntos y pasó hasta el concursante clasificado en la posición 936.
Aquí podéis ver los problemas propuestos en esta fase.

Calificación 3: Tennison

Enunciado original.

Como nos adelantaba la mayor puntuación de este problema sobre los anteriores es el más complicado de los tres de la fase de calificación. La dificultad estriba en que tenemos que darnos cuenta de un detalle del problema que nos va a permitir resolverlo por un método que no es el directo. Pero no adelantemos acontecimientos.

El problema trata de calcular la probabilidad de un evento, en este caso la victoria del jugador Tennison en un partido de tenis (¿a qué podía jugar si no con ese nombre?). Los problemas de probabilidad se resuelven sumando la probabilidad de todos los casos favorables, es decir los casos en los que sucede el evento. Sólo hay que preocuparse de generar todos los casos, sin repetir ninguno, calcular bien la probabilidad de cada caso individual y, por supuesto, sumar correctamente eligiendo la precisión adecuada.

Afortunadamente no nos han hecho introducirnos en el complicado sistema de tanteo de un partido de tenis y se han limitado a tener en cuenta la puntuación de último nivel de este deporte, es decir, los sets. Por contra nos han alargado la duración del partido ya que si los partidos reales se juegan normalmente al mejor de tres o cinco sets, esto es gana el jugador que primero se anota dos o tres sets, en nuestro problema gana el jugador que antes se anote K sets, donde K puede ser tan grande como cien. O lo que es lo mismo, Tennison puede jugar un partido al mejor de 199 sets...

Teoría de probabilidades (básico)

Un poquito de teoría de seguro innecesaria:

Aunque estemos acostumbrados a hablar de probabilidades como tantos por ciento, matemáticamente la probabilidad de un suceso se expresa con un número real entre cero (suceso imposible) y uno (suceso seguro). 

La probabilidad de que sucedan dos sucesos independientes entre sí es el producto de las probabilidades de que sucedan cada uno por separado. O sea como la probabilidad de que al tirar una moneda salga cara es 0.5, la probabilidad de que al tirar dos veces salgan dos caras es de 0.25 (0.5 multiplicado por 0.5).

La probabilidad de que suceda uno de varios sucesos excluyentes entre sí, osea que no pueden suceder a la vez, es la suma de las probabilidades de cada suceso individual. Así por ejemplo la probabilidad de sacar una cara y una cruz al tirar dos monedas es la suma de sacar primero una cara y luego una cruz (0.25 como vimos en el párrafo anterior) y la de sacar primero una cruz y luego una cara, es decir, 0.5 (0.25 + 0.25).

Método fuerza bruta

Como decía al principio nos piden que calculemos la probabilidad de que Tennison gane un partido. El evento ganar el partido se traduce en que gane K sets antes que lo haga su oponente. En cada set que comienza Tennison tiene dos probabilidades diferentes de ganarlo en función del tiempo que haga: sol o lluvia. En realidad lluvia es equivalente a no sol, lo que nos simplifica la vida. El problema reside en que conocemos la probabilidad de que haga sol al comienzo del partido pero ésta va a variar a lo largo del mismo en función del resultado. Si Tennison gana el set la probabilidad de sol puede aumentar o puede quedar igual, y si lo pierde la probabilidad puede disminuir o puede quedar igual. Las probabilidades de que aumente o disminuya o no según quién gane el set son fijas durante todo el partido y las cantidades en que se  incrementa o disminuye la probabilidad del sol también son fijas. ¡Menos mal!

Algoritmo:

Veamos cómo resolveríamos el segundo de los casos propuestos como ejemplos:

Se trata de un partido a dos sets en los que la probabilidad de victoria con sol es de 0.6 y sin sol de 0.2, la probabilidad inicial de sol es de 0.5 y las probabilidades de que aumente la probabilidad de sol con la victoria en 0.1 es 1 (siempre sube) y la de que baje 0.1 con la derrota es 1 también.

Comienza el partido, la probabilidad de que vayan 0-0 es 1 obviamente.

Tenemos dos posibilidades (con 0-0) que haya sol con probabilidad 0.5 y que llueva con probabilidad 0.5.

Tennison puede ganar el primer set en ambas condiciones, así que la probabilidad de que gane el primer set es la suma de las probabilidades de que lo gane con sol más que lo gane con lluvia. Con sol tendrá una probabilidad de 0.5*0.6=0.3 (producto de las probabilidades de que haga sol y que gane con sol) y con lluvia, análogamente, 0.5*0.2=0.1. Por lo tanto la probabilidad de vencer el primer set es 0.3+0.1=0.4. Obviamente si no gana el set lo pierde, por lo que la probabilidad de que pierda el primer set es 1-0.4=0.6.

Así que la probabilidad de que el resultado sea 1-0 es 0.4 y 0-1 0.6. En ambos casos nadie gana ni pierde el partido.

Vamos a seguir la rama de posibilidades (sí, todos los eventos se organizan en un árbol) del 1-0. Como Tennison ha ganado el último set la probabilidad de sol puede aumentar o no, así que tenemos dos posibilades: que el resultado sea 1-0 y la probabilidad de sol aumente hasta 0.6 o que el resultado sea 1-0 y la probabilidad de sol permanezca en 0.5. El primero caso tiene una probabilidad de 0.4*1=0.4 (producto de la probabilidad acumulada hasta el resultado 1-0 por la probabilidad de que aumente la probabilidad de sol), el segundo caso tendrá 0.4*(1-1)=0, suceso imposible por lo que no tendremos que avanzar por esta rama más.

Continúa el partido, la probabilidad de que gane el 2º set será otra vez la suma de que gane con sol o lluvia: 0.6*0.6+0.4*0.2=0.44. Hay que multiplicarlo por la probabilidad de que haya ganado el primer set y que la probabilidad haya subido hasta 0.6, o sea: 0.4*0.44=0.176. En este momento Tennison gana el partido así que esta es la probabilidad de la primera combinación de eventos que conducen a la victoria. Lo sumamos.

La probabilidad de que pierda el set será 1-0.44=0.56 que también tendremos que multiplicar por 0.4 para obtener la probabilidad de que el resultado sea empate después de ganar el primer set (perdiendo el primer set también se puede llegar a la condición de empate): 0.4*0.56=0.224. Nuevamente la probabilidad de sol puede bajar hasta 0.5 con probabilidad de 1 o quedar en 0.6 con probabilidad de 0. Así la probabilidad de empate 1-1 con probabilidad de sol de 0.5 será 0.224*1=0.224 y la probabilidad de empate 1-1 con probabilidad de sol 0.6 será 0.224*0=0.

Siguiendo el partido desde 1-1 con probabilidad de sol 0.5, la probabilidad de victoria del set en estas condiciones es 0.5*0.6+0.5*0.2=0.4, así la probabilidad del 2-1 es 0.224*0.4=0.0896 que acumularíamos con los 0.176 del 2-0 quedando una probabilidad de victoria hasta aquí de 0.176+0.0896=0.2656.

La derrota conduciría al 1-2 y la pérdida del partido.

Seguiríamos analizando desde el 0-1 con probabilidad de sol 0.4 que tenía una probabilidad de 0.6. La probabilidad de victoria en este caso sería 0.4*0.6+0.6*0.2=0.36, multiplicado por la probabilidad acumulada 0.6*0.36=0.216 que multiplicado por 1 nos da la probabilidad de empate 1-1 con probabilidad de sol 0.5 es 0.216. La derrota del set provoca la pérdida del partido por lo que no tenemos que seguir analizando esa rama.

Desde el 1-1 con probabilidad de sol 0.5 la probabilidad de victoria del set es 0.4, así que la victoria 2-1 tendrá una probabilidad de 0.216*0.4=0.0864. Lo sumamos con la probabilidad acumulada y obtendremos la probabilidad de victoria: 0.352

Rutina re-entrante:

Así es como vamos a codificar el algoritmo de esta solución, con una rutina re-entrante o, lo que es lo mismo, una función que se llama a sí misma.

Como hemos visto resolviendo el problema a mano, partimos de un resultado, una probabilidad de sol y una probabilidad de que suceda esta situación en el partido. Todos estos serán los parámetros de llamada a nuestra función: el número de sets ganados, el número de sets perdidos, la probabilidad de sol y la probabilidad acumulada del evento.

Con esas condiciones calculamos la probabilidad de que Tennison venza en el siguiente set.

Si al vencer alcanza los K sets incrementa la probabilidad de victoria en el producto de la probabilidad de vencer el set por la probabilidad acumulada del suceso. Si no llega a K sets tendremos dos posibilidades: que aumente o no la probabilidad. Esto se traducirá en dos llamadas a la misma función en donde el número de sets ganados se habrá incrementado en uno, la probabilidad de sol habrá aumentado en una llamada y en la otra no y la probabilidad acumulada se habrá multiplicado por la probabilidad de victoria y por la probabilidad de que aumente le probabilidad de sol en el primer caso o de que no aumente en el segundo.

Y lo mismo considerando una derrota en el set. En este caso si el número de sets perdidos alcanza K no hacemos nada.

La función tendría este aspecto:

void nextGame(int gw,int gl,double psun, double p)

{

if (psun>1.0) psun=1.0;

if (psun<0.0) psun=0.0;

double win=psun*ps+(1-psun)*pr;

if (++gw==K)

{

pwin+=p*win;  // win

}

else

{

nextGame(gw,gl,psun+pu,p*win*pw);

nextGame(gw,gl,psun,p*win*(1-pw));

}

gw--;

double lost=1-win;

if (++gl==K)  // lost

{

plost+=p*lost;

}

else

{

nextGame(gw,gl,psun-pd,p*lost*pl);

nextGame(gw,gl,psun,p*lost*(1-pl));

}

gl--;

}

Las dos primeras instrucciones obligamos a que la probabilidad de sol no se salga de los límites.

Todas las variables que se emplean, excepto los parámetros de la función, están definidas fuera de las funciones del programa, incluso fuera de la función main, para que su ámbito sea global a todo el programa.

Cada nivel del árbol nos generará una nueva llamada a la función. El compilador se ocupa por nosotros de guardar los parámetros de llamada a la función, de acordarse dónde tiene que regresar cuando acabe de explorar el árbol, etc.

El peligro de usar este tipo de algoritmos es olvidarse de programar alguna condición de finalización, es decir, en algún momento la llamada a la función debe terminar sin llamarse a sí misma otra vez.

El segundo peligro es la cantidad de memoria que va a emplear. Hay que tener en cuenta que cada parámetro de llamada y cada variable definida local en el interior de la función necesitan memoria para ser almacenada en cada nivel de llamadas a la función puesto que los valores son distintos aunque la variable se llame igual.

Nuestro problema se resolverá haciendo una llamada desde el método main a esta función con los siguientes valores:

nextGame (0,0,pi,1.0);

donde pi es la probabilidad inicial del sol, dato del problema y 1.0 es la probabilidad del resultado 0-0.

Problema del método de fuerza bruta:

Aquí está el programa completo, ¿pero resuelve el problema?

La respuesta es lamentablemente no. De hecho yo ni siquiera hubiera llegado a programar este método porque el número de casos que se pueden generar es inabordable. De hecho vemos que en cada llamada a la función nos genera 4 llamadas como mínimo hasta que alcancemos el nivel K, luego puede que alguna rama no esté completa. Pero incluso contando sólo con nivel 100 en el último nivel del árbol habrá 4^100 casos, que es una cantidad con 60 cifras. No creo que su ordenador sea capaz de evaluar tantos casos. De hecho ni siquiera el caso del ejemplo en el que K=25 terminará con este programa.

Me ha venido bien para explicar el funcionamiento de las rutinas re-entrantes y para ver cómo se resuelven en general los problemas relacionados con probabilidades, que no es poco.

Algunas veces implementar un método que sabes que no va a funcionar por ineficiente puede servirte como base para ver cómo evoluciona el problema y, entonces, encontrar la idea brillante que resuelva el problema.

Método paso a paso

En este caso nos damos cuenta que hay demasiados caminos posibles, pero muchos de ellos conducen a los mismos resultados. De hecho en el ejemplo que hicimos a mano ya vimos que pasábamos dos veces por el resultado 1-1.

Osea que hay relativamente pocos resultados intermedios diferentes en el partido. Si K=100 está claro que se jugarán menos de 200 sets. Si hemos jugado N juegos pueden repartirse entre los dos jugadores de N+1 formas distintas por lo que tendremos muchas menos de 200x200 posibilidades diferentes. Eso es muy poco para un ordenador.

Podríamos ir avanzando juego a juego y calculando la probabilidad de cada resultado a partir de las probabilidades del nivel con un juego menos. Igual que en el método de la fuerza bruta iríamos sumando las probabilidades de todos los resultados que supongan la victoria de Tennison.

Lamentablemente tenemos una variable adicional. En cada momento del partido no sólo importa el marcador sino la probabilidad de que haya sol, y esta es una variable real, no entera. Si fuera entera podríamos añadir una dimensión más a nuestra tabla de probabilidades y calcular la probabilidad de todos los resultados y todas las probabilidades de buen tiempo.

¿Podemos convertir un real entre cero y uno en un entero? La respuesta es sí si el número de decimales está limitado. ¿Está limitado en nuestro problema? ¡Bingo! La respuesta es sí. Entre las condiciones del problema nos indican que todas los datos de probabilidades van a venir con tres decimales. Como vamos a sumar o restar cantidades de tres decimales a la probabilidad de buen tiempo siempre se van a mantener en tres decimales. Así que si multiplicamos por mil se convertirá en un entero entre 0 y 1000.

1000x200x200 sigue siendo una cantidad manejable por un ordenador.

Así que el algoritmo será construir una tabla en el que el primer índice será el número de sets jugados. Variará entre 0 y 2*K-1. El segundo el número de sets ganados por Tennison. Variará entre 0 y N para el nivel de N sets jugados (primer índice). Y el tercer índice será la probabilidad de sol. Variará entre 0 y 1000.

En el nivel 0 del primer índice el segundo sólo puede valer 0. las probabilidades del tercer nivel (entre 0 y 1000) valdrán todas 0 excepto la probabilidad correspondiente con la probabilidad de sol inicial del problema.

Calcularemos el nivel N+1 a partir del nivel N. Calcularemos la probabilidad de victoria para cada probabilidad de buen tiempo e iremos sumando la posición de la tabla correspondiente al nivel N+1 correspondiente al resultado de ganar o perder el set y mantener o incrementar/disminuir la probabilidad de buen tiempo.

El algoritmo es mucho más sencillo que el de fuerza bruta. Consiste simplemente en un triple bucle anidado e. igual que en el caso de fuerza bruta, una variable en donde acumular las propiedades de los eventos que conducen a una victoria del partido.

Aquí está el programa completo, no creo que necesite una mayor explicación.

Flags en streams

Bueno sí que podemos aclarar un pequeño trozo del programa, la salida de resultados para cumplir con las especificaciones del formato de salida:

cout.setf(ios::fixed, ios::floatfield);

cout.setf(ios::showpoint);

cout << "Case #" << t << ": " << setprecision(6) << pwin << endl;

Hemos empleado el método setf, con dos formatos diferentes, para establecer el modo de salida de los datos que enviemos al stream.

La primera llamada establece la escritura de reales en notación en coma fija en vez de notación científica.

La segunda llamada fuerza a que se visualice el punto decimal.

Finalmente, en la cadena de operadores << que hacen salir los resultados al stream, hemos añadido una llamada que no produce ninguna salida de datos sino que acomoda la forma en que saldrán los siguientes datos (setprecision), en este caso fuerza a que salgan 6 decimales.

Aquí está la descripción completa del método setf y aquí la descripción de setprecision.

Calificación 2: Baloncesto

Enunciado original

Este es el tipo de problemas más sencillos. Aquellos en los que el propio enunciado del mismo te da el algoritmo para solucionarlos.

Sólo voy a dar un pequeño truco que empleo cuando tengo que ordenar algo por varios criterios de tal forma que se van empleando los sucesivos cuando los anteriores son iguales: convierto todos los valores del criterio en un único número y así simplifico la comparación.

Por ejemplo, en el caso del ranking de los jugadores se van a ordenar por su porcentaje de tiro en primer lugar y por su altura en el segundo. Construiré un número con ambas cantidades en los que las cifras de más valor de este número se correspondan con el criterio principal de la comparación (porcentaje de disparo) y las de menos valor con la altura. Como el rango de la altura tiene 3 cifras multiplico el porcentaje de tiro por 1000 y sumo ambas cantidades. Es fácil ver que ahora con una sola comparación puedo ordenar los jugadores.

Como en todos los problemas nuestro programa comienza con la lectura del número de casos a resolver y un bucle externo para estos casos:

cin >> T;

for (t=1; t<=T; t++)

{

}

Y ahora, para cada caso, realizaremos los siguientes pasos: lectura de datos del problema, ordenar los jugadores en los dos equipos, simular los minutos del partido realizando los cambios, ordenar alfabéticamente los nombres de los jugadores que estén en juego al final del tiempo del partido y escribir los resultados.

Lectura de datos. Definimos un struct para guardar los datos de cada jugador y creamos un array de variables de este tipo. Como adelanté en vez de guardar los dos datos para calcular el ranking de un jugador los voy a condensar en uno solo.

struct

{

    char name[25];

    long rank;

} students[30];

Y la lectura efectiva de los datos:

cin >> N >> M >> P;  // lectura datos

for (n=0; n<N; n++)

{

    long shot,height;

    cin >> students[n].name >> shot >> height;

    students[n].rank=shot*1000+height;

}

Para ordenar los jugadores en los dos equipos, como siempre en programación y como no me cansaré de repetir, lo primero que necesitamos es una estructura de datos que representen a los jugadores de los equipos:

struct

{

    int nstudent;

    long timeplay;

    bool play;

} teams[2][15];

El primer campo es el vínculo al array de los datos de los jugadores anterior, el segundo acumulará el tiempo que lleva en juego y el tercero un booleano que indica si el jugador está en el campo o en el banquillo. Es un array bidimensional para separar los datos de los equipos.

Este array lo rellenaremos usando el bien conocido médodo de la burbuja, ya empleado en otros problemas (descrito en esta entrada del blog):

for (n=1, tm=0, p=0; n<=N; n++)  // ordenar en equipos

{

    long maxrank=0;

    int stmax=0;

    for (int i=0; i<N; i++)

    {

        if (students[i].rank>maxrank)

        {

            maxrank=students[i].rank;

            stmax=i;

        }

    }

    teams[tm][p].nstudent=stmax;

    teams[tm][p].timeplay=n;

    teams[tm][p].play=(p<P);

    students[stmax].rank=0;

    np[tm]=p+1;

    if (++tm>1)  // siguiente puesto en equipos

    {

        p++; tm=0;

    }

}

En realidad no es una burbuja puesto que no vamos cambiando el orden de los elementos del array en el que están guardados los datos. Lo que hacemos es buscar el máximo valor en la tabla, guardar el índice del jugador en el array que representa a los equipos y guardar cero en el valor rank del jugador para que ya no vuelva a salir al buscar el máximo de la tabla porque todos los valores rank son estrictamente mayores de cero.

A parte de la variable n que controla la longitud del bucle necesitamos otras dos porque tenemos que ir guardando los valores uno en cada equipo. Lo controlamos con los índices tm y p que evolucionan con la comparación del final de bucle.

Si el jugador es elegido, dentro de su equipo, en un orden menor que el número de jugadores que juegan a la vez (P) la variable play mostrará que están en juego (true).

Finalmente en el campo de la estructura destinada a guardar el tiempo de juego guardo el número de orden en el que se ha elegido el jugados (n). ¿Por qué? Por la misma razón que en la ordenación de los jugadores. En vez del tiempo añado en la parte baja del número el número de orden de selección y el tiempo multiplicado por 100. Así, en caso de empate a tiempo de juego se me ordenarán por el número de orden de selección y nuevamente la comparación se simplifica.

Simulamos el tiempo de juego con un bucle:

for (m=0; m<M; m++)  // rotaciones

{

  for (tm=0; tm<2; tm++)  // por equipo

    if (np[tm]>P)  // hay banquillo

    {

      long maxtime=0, mintime=100000;

      int npmax=0, npmin=0;

      for (n=0; n<np[tm]; n++)  // buscar cambio

      {

        if (teams[tm][n].play)  // esta jugando

        {

          teams[tm][n].timeplay+=100;  // tiempo de juego

          if (teams[tm][n].timeplay>maxtime)

          {

            maxtime=teams[tm][n].timeplay;

            npmax=n;

          }

        }

        else  // esta en banquillo

        {

          if (teams[tm][n].timeplay<mintime)

          {

            mintime=teams[tm][n].timeplay;

            npmin=n;

          }

        }

      }

      teams[tm][npmax].play=false;  // cambio

      teams[tm][npmin].play=true;

    }

}

Por cada minuto de juego necesitaremos un bucle para hacer los cambios en los dos equipos.

Si el número de jugadores de un equipo, guardado en el array np, no es mayor que el número de jugadores que juegan a la vez no hay que hacer cambios. De ahí la primera instrucción del bucle.

Finalmente un bucle que recorre todos los jugadores del equipo. Buscaremos el que tenga el máximo valor de timeplay para los jugadores que estén en juego, a los que incrementaremos en 100 este valor para indicar que han jugado 1 minuto más, y el mínimo de entre los que están en el banquillo. Al final del bucle haremos el cambio que sólo supone cambiar de estado el campo play de los jugadores afectados.

Ya se ha terminado el partido. Ahora cogemos los nombres de los jugadores que han quedado en el campo y los ordenamos alfabéticamente:

vector<int> nstplay;  // Lista ordenada de jugadores en juego

vector<int>::iterator it;

for (tm=0; tm<2; tm++)

    for (n=0; n<np[tm]; n++)

        if (teams[tm][n].play)

        {

            for (it=nstplay.begin(); it!=nstplay.end(); ++it)

                if (strcmp(students[*it].name, students[teams[tm][n].nstudent].name)>0)

                {

                    nstplay.insert(it, teams[tm][n].nstudent);

                    break;

                }

            if (it==nstplay.end())

                 nstplay.push_back(teams[tm][n].nstudent);

       }

Otro método de ordenar elementos es partir de cero e ir añadiendo los elementos en una lista ordenándolos conforme los añadimos. Para ello partimos con una lista vacía y vamos añadiendo los elementos a ordenar. Al insertar un nuevo elemento, buscamos en la lista de los elementos ya añadidos el primero que es posterior al que se inserta en este momento y se inserta justo antes de éste. Si es posterior a todos los elementos de la lista se añade al final. Cuando se terminan de añadir los elementos, obviamente, en la lista quedan ordenados.

Recorro, con dos bucles anidados, a los jugadores de los dos equipos e inserto en un vector el número del jugador si está en el campo de juego según el algoritmo descrito en el párrafo anterior.

La clase vector, que ya hemos empleado con anterioridad (ver entrada), no es la más eficaz, pese a tener métodos para realizar las acciones de insertar y añadir al final, porque al insertar elementos en mitad de la lista mueve físicamente los elementos una posición hacia abajo, al fin y al cabo no deja de ser un array. Como el número de elementos es pequeño podemos permitirnos este lujo de ineficiencia y emplear una clase que, al poder trabajar con ella como si fuera un array, hace nuestro programa más amigable.

Para recorrer el vector, aunque se podría recorrer por su índice, empleamos un iterator, que es un índice a una posición en el vector. Los métodos begin y end del vector devuelven el primer elemento del vector y una posición después del último elemento del vector.

La variable iterator funciona como un puntero del tipo del elemento guardado en el vector, así que el operador * nos devuelve el valor del elemento al que apunta el iterator.

Todo el trabajo está hecho, sólo queda escribir el resultado:

cout << "Case #" << t << ":";

for (it=nstplay.begin(); it!=nstplay.end(); ++it)

    cout << " " << students[*it].name;

cout << endl;

No hay nada que comentar de este código. Como siempre aquí os dejo el programa completo y el fichero de datos de entrada del concurso.

Estos dos fueron los únicos problemas de esta fase que me dio tiempo a realizar (como siempre montones de cosas por hacer que quitan el tiempo de estos pequeños pasatiempos). Me facilitaron el paso a la siguiente fase en la posición 2369. Aquí me podéis ver en la clasificación de la ronda.