Algunas soluciones - IEEEXtreme Bolivia

===== Teams =====
Facil

===== Strings with Same Letters =====
Facil

===== Mohammed Refaat (Grafos) =====
Nos dan un grafo con pesos en las aristas y nos piden el camino mas corto entre dos nodos. Para esto usamos el algoritmo de Dijkstra.

===== Chess Knights (Grafos) =====
Vemos cada casilla como un nodo, un nodo esta conectado a otro si se puede llegar a el con un movimiento del caballo. Con esto en mente, el problema se convierte a encontrar el tamaño del componente en el que se encuentra la casilla inicial; este problema se resuelve con DFS, BFS o Union Find.

===== Triangles Area =====
No resuelto :(

===== Difficult Routes =====
No resuelto, ni lo entendimos :(

===== Make Psycho (DP) =====
El problema mas frustrante que resolvimos durante el contest.
Podemos dividir el problema en dos partes:
1) Eliminar todos los numeros ordinarios (no Psycho) de la lista que nos dan en la entrada
2) Con la nueva lista, decir si podemos formar un subconjunto tal que la suma de sus elementos sea igual a K

La primera parte es bastante sencilla, hacemos la verificacion de si un numero es Psycho usando una criba de Eratostenes o con fuerza bruta (el tamaño de entrada y los numeros son pequeños).

La segunda parte se puede resolver con programacion dinamica viendo las posibilidades de tomar o no tomar un elemento para el subconjunto resultado, la funcion top-down es la siguiente:
bool f(int posicionEnLista, int suma)
{
// casos base
	si suma = 0, return verdadero
	si posicionEnLista == finalLista, return falso
	si suma < 0, return falso
// memoizacion
    si ya visitamos este estado, devolver respuesta
// resolver problemas mas pequeños recursivamente
	resultado = f(posicionEnLista+1, suma + lista[posicionEnLista]) | f(posicionEnLista+1, suma)
	return resultado
}

Esto nos da una complejidad de O(n*k), con n = 100, k = 10^5 y 2000 casos, la solucion da TLE :(
Al no tener idea de como resolver los problemas que faltaba ni de otra posible solucion para este problema, decidimos seguir intentando. Y despues de 9 intentos, logramos obtener el AC! Luego de intentar todo fueron dos optimizaciones las que hicieron el truco:

La primera fue generar todos los numeros psycho hasta 1100 (limite superior del problema) y declarar un arreglo con estos valores de forma explicita ya que solo hay 49
ej: int psychoNumbers[49] = {4, 9, 16, 25, ...};

La segunda y mas importante es volver el DP a su forma bottom-up iterativa.

Aunque la complejidad sigue siendo O(n*k), el tiempo de ejecucion baja mucho..... ¯\_(ツ)_/¯

===== Train Passengers =====
Lees la capacidad y las rutas que hara el tren ahora lees 3 enteros por cada ruta la cantidad que salen, entran y se quedan tienes que verificar que la ruta no sea invalida.Pondremos un totaldepasajeros=0 y le restamos la cantidad de totaldepasajeros si esta es menor a 0 entonces es invalido (1era opcion) totaldepasajeros sumas la cantidad que entran si esta es mayor > la capacidad de entrada entonces es invalido (2da opcion) ahora  si la cantidad de personas que entran<la cantidad de personas que se quedan invalido(3ra opcion) y al final verificas que totaldepasajeros=0 si no (el problema te pide que cuando llegue al final no tiene que tener pasajero ) invalido (4ta opcion)

===== Easy One =====
El mas facil

===== Super Ants =====
No resuelto :(

===== Football Hooliganism (Greedy) =====
Primero unimos todas las celdas de ancho 1 verticales poosibles
01										      0A
01				=======>			          0A
11  marcando celdas de 1's unidas con letras  BA
10										      B0
00											  00

Llamaremos a cada conjunto de celdas consecutivas "segmento". La figura de arriba tiene 2 segmentos, A y B.
Guardamos cada inicio y final de segmento.
Cada segmento en el que inicio = final, es un confinamiento solitario.
Ahora, para eliminar un confinamiento solitario debemos extender su celda hacia la derecha/izquierda, esto provoca que quitemos una posicion de un segmento (ya que es la que usaremos para eliminar el confinamiento solitario y todas las celdas pertenecen a un segmento).

Tenemos 3 posibilidades al eliminar una parte de un segmento:
1) Eliminamos el inicio o final de un segmento
2) Eliminamos una parte del medio y dividimos el segmento en dos partes
3) Si tambien es un confinamiento solitario, eliminamos todo el segmento

Por cada confinamiento solitario vemos estas tres posibilidades, si no generan un nuevo confinamiento solitario, alargamos la celda solitaria y eliminamos un (o dos en el tercer caso) confinamiento solitario.

La solucion seria: ConfinamientosSolitariosOriginales - ConfinamientosSolitariosArreglados
Complejidad: O(n)

===== deltree =====
No leido