Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
537 lines (384 sloc) 32.6 KB

TECNOMATE 2017

sitio oficial

Categoria SECUNDARIA

Problema 1: General Exam

Para poder responder las queries necesitamos almacenar los datos ingresados en un arreglo. Una vez cargados los datos, la solución más sencilla es ordenar el arreglo de mayor a menor y para cada querie la respuesta será el elemento que se encuentra en la posición p_i-1 del arreglo (p_i es el valor leído en la i-ésima querie);

Problema 2: Krapeskar

Greedy, implementación.

Lo difícil de este problema es implementar las funciones para obtener el mayor y el menor número con los dígitos de un número dado. Es evidente que el mayor se forma ordenando los dígitos del número en forma descendente (de mayor a menor), y el menor, al revés.

Una vez hecho esto, simplemente usamos la función que nos brinda el enunciado, agregando en algún lado el control de que el número no tenga todos sus dígitos iguales; en tal caso la respuesta es -1.

Problema 3: Blue Lagoon

El problema tiene un caso tricky para un pajaro que es el siguiente:

1 5
1 3 0

En ese caso tomaría 1 vuelta atrapar a ese pájaro.

Luego lo que debo hacer es contar para cada pájaro las vueltas necesarias para atraparlo. Recorriendo los puntos a donde vuela, si el punto en el que estoy es menor al anterior, di una vuelta. Teniendo en cuenta el caso del 0.

La mayor cantidad de vueltas es la respuesta.

Problema 4: Travel To Mars in primo speed

Con ir de a un número comprobando si es primo y sumando los 10 primeros, ya tenemos la solución del problema. Una función para comprobar si número es primo es por ejemplo:

//C++
bool is_prime(int n){
	if(n < 2) return false;
	for(int x = 2; x*x <= n; x++){
		if(n%x == 0)return false;
	}
	return true;
}

Calcular las horas y los días es una simple división al tener la velocidad calculada.

Problema 5: Virus

Greedy.

La suma ideal/óptima se logra armando los pares con el número más grande y el más chico. Entonces, ordenando un vector con los virus, y tomando los "extremos" para armar los pares, conseguimos el resultado. En caso de ser N impar, el virus del "medio" es el que se ignora.

Problema 6: Maquina de Cafe

Al ser sólo 3 pisos, se pueden probar las 3 posibles situaciones (que la máquina esté en cada uno de ellos), y mostrar la óptima (la que de menos tiempo T).

1. Si la maquina esta en Planta baja. T = a2*2 + a3*4
2. Si la maquina esta en el 1er Piso. T = a1*2 + a3*2
3. Si la maquina esta en el 2do Piso. T = a1*4 + a2*2

Problema 7: Building Walls

Este problema tiene una implementación tediosa al tener que en una misma línea tomar dos valores nombre del titan y altura.

Hay un par de funciones que se deben saber para poder tomar una sola línea:

string temp;
getline(cin,temp);

Con getline podemos tomar una linea entera, y guardarlo en un string. O sino se puede ir tomando caracteres hasta que haya un salto de linea:

char linea[]="";
char c = getchar();
while(c!='\n'){
	linea += c;
}

Luego es cuestión de parsear esa línea, lo más directo es ir recorriendola de atrás para adelante, de a un carácter hasta encontrar un espacio.

De esta manera, tenemos de un lado el string que represente el nombre del titan, y del otro su altura.

Hay muchas formas de pasar un string a número, vamos a mostrar 2:

La más directa, pero que hay que utilizar una librería:

#include <sstream>
string altura;
int height;
istringstream (altura) >> height;

Y la otra menos directa, pero sin utilizar librerías:

string altura;
int height = 0;
for(int i=0; i < altura.length(); i++){
	height += (altura[i]-'0') * pow(10,(altura.length()-1 - i));
}

Luego de tener estos datos es solo cuestión de comparar si la altura es mayor a la de la pared, e imprimir el nombre del titán si así lo es.

Problema 8: Image

La solución es sencilla, solamente debemos implementar lo que nos dice el enunciado; esto puede generar alguna complicación pero no hay nada extra que pensar. Básicamente, para cada caso podemos leer la "imágen" en una matriz de caracteres e imprimir cada fila a/n veces y, al imprimir una fila, imprimir b/m veces cada caracter.

//C++
for(int i=0;i<n;i++)
	for(int f=0;f<a/n;f++) //cada fila a/n veces
	{
		for(int j=0;j<m;j++)
			for(int c=0;c<b/m;c++) //cada columna b/m veces
				cout << imagen[i][j];
		cout << "\n";
	}

Problema 9: Super Primes: Engage!

Si se toma el N como un string. Es bastante directo. Debemos analizar hacer 2 cosas:

  1. N es primo?. Esto se sabe fácil pasando N a int. Y analizando con cualquier algoritmo de primos si lo es.
  2. Todos los digitos de N son primos? Esto se sabe recorriendo digito por digito (caracter a caracter), y vamos viendo si el mismo es primo. Esto es directo si sabemos los primos de un dígito {2,3,5,7}.

Luego es solo armar una estructura condicional donde si cumple las dos condiciones es Super, si es solo la primera Primo, y sino Nada.

Problema 10: What is the Fastest?

Lo importante de este problema es tomar los datos como float o double.

Comparandolos de esta manera, con una usar una estructura if{}else if{} else solucionamos este problema.

Categoria Algoritmos

Problema 1: Máquina de Café

Problema 6 de Secundaria

Problema 2: Palindrome Double

Probablemente el problema más difícil de este nivel.

Primero es importante aclarar que un palíndromo real es todo número real (incluídos los enteros) que se leen igual al derecho y al revés (definición de palíndromo), incluyendo el punto. Es decir que por ejemplo:

  1. 121, 8, 330.033 y 66.66 son palíndromos reales
  2. 122, 10, 121.0121 y 66.6 no son palíndromos reales

Entonces podemos decir que un palíndromo real es un número entero palíndromo o un número real no entero en el que la parte decimal es el reflejo de la parte entera. Teniendo esto en mente es sencillo observar que entre dos números enteros consecutivos existe 1 y sólo 1 palíndromo real no entero, ya que el reflejo de la parte entera es único. De esta forma podemos reducir el problema a los siguientes casos (a verificar en el orden dado):

  1. Si el número ingresado (X) es un palíndromo, la respuesta es 0. Por ejemplo 12.21 -> 0 (12.21)
  2. Si el palíndromo real cuya parte entera es igual a la parte entera de X (y la parte decimal es el reflejo de X) es mayor que X, la respuesta será la diferencia entre estos números. Por ejemplo 13 -> 0.31 (13.31)
  3. Si el menor entero mayor que X es palíndromo, la respuesta es la diferencia entre este entero y X. Por ejemplo 120.022 -> 0.978 (121)
  4. Si ninguno de los casos anteriores se verifica entonces la respuesta es la diferencia entre el palíndromo real cuya parte entera es igual al menor entero mayor que X (y la parte decimal es el reflejo de este entero) y X. Por ejemplo 900.019 -> 1.09 (901.109)

Problema 3: Help Girafales!

Problema complicado de solucionar si no se conoce la estructura map<string, string>.

Proponemos una solucion que utiliza vector.

Creamos dos vectores de strings, uno para guardar los nombres y otro para las firmas.

Luego vamos cargando los nombres y firmas a comprobar. Linea por linea lo que hacemos es:

  1. Buscar el nombre en el vector, para conocer su indice i.
  2. Comparamos la firma correcta firmas[i], con la ingresada.
  3. Para comparar lo hacemos caracter a caracter, y vamos contando las diferencias. Esto se puede hacer con un simple for.
  4. Si las diferencias son mayor que 1, le sumamos 1 a nuestra respuesta.

Problema 4: Image

Problema 8 de Secundaria.

Problema 5: Train Swapping

En resumen el problema nos pregunta ¿Cuál es la mínima cantidad de operaciones a realizar para ordenar un conjunto de números, si la única operación permitida es intercambiar dos números que estén en posiciones adyacentes (swap)?. El ordenamiento burbuja es un algoritmo bien conocido que justamente hace esto. Como la entrada es pequeña podemos simplemente correr este ordenamiento y contar la cantidad de swaps que se realizan, que será nuestra respuesta; la complejidad para cada caso será O(L^2). También hay otras formas de pensarlo y soluciones más eficientes, con complejidad O(LlogL) por ejemplo.

Problema 6: Hunting Digletts

Es clave entender que el enunciado nos dice que las cuevas forman un conjunto de circuitos o ciclos. Luego, digamos que dichas cuevas forman K circuitos: C_1,C_2,...,C_k y sus longitudes (cantidad de cuevas que contiene) son respectivamente: L_1,L_2,...L_k; entonces cada Diglett viajará por alguno de estos circuitos y especificamente el Diglett que viaja por C_i se asomará cada L_i segundos a la superficie. Finalmente es bastante intuitivo pensar que todos los Digletts se asomarán al mismo tiempo cuando el tiempo transcurrido sea múltiplo de todos las longitudes de los circuitos. Es decir que para encontrar el mínimo debemos calcular el mínimo común múltiplo (mcm) de estas longitudes, mcm(L_1,L_2,...,L_k).

Entonces, primero debemos obtener las longitudes de los circuitos, que es bastante sencillo. Luego debemos calcular el mcm, y la forma mas sencilla de hacer esto es teniendo en cuenta lo siguiente:

  1. mcm(a,b,c) = mcm(mcm(a,b),c) = mcm(a,mcm(b,c)) (es decir que la "operación" mcm es asociativa y conmutativa)
  2. mcm(a,b) = (a*b)/mcd(a,b). Siendo mcd el máximo común divisor, que puede calcularse de manera sencilla usando el Algoritmo de Euclides. A continuación dejamos una implementación del mismo:
//C++
int mcd(int a,int b)
{
	if(b==0) return a;
	return mcd(b,a%b);
}

Problema 7: Sort!, sort! and sort!!!

Está más que claro que lo que debemos hacer es ordenar un conjunto de números según varios criterios.

Para ordenar un conjunto de números, sea cual sea el algoritmo que apliquemos (selección, inserción, burbuja, merge, etc.), en alguna parte del código seguro compararemos pares de números para conocer su orden relativo. Si por ejemplo queremos ordenar de menor a mayor, en algún lugar tendremos algo parecido a:

//C++
if(x<y)
{
	//x estará antes que y en el orden final
	...
}
else
{
	//y estará antes que x en el orden final
	...
}

Luego, para resolver el problema podemos pensarlo igual que un ordenamiento "común" pero donde la condición de precedencia será un poco más compleja. Una forma sencilla de hacer esto es armar una función que reciba dos números como parámetro y retorne un valor de verdad indicando si el primer parámetro precede al segundo o no. Si dicha función por ejemplo la llamamos comparar, el código de arriba cambiaría a:

//C++
if(comparar(x,y))
{
	//x estará antes que y en el orden final
	...
}
else
{
	//y estará antes que x en el orden final
	...
}

Entonces sólo resta implementar correctamente dicha función y aplicar algún método de ordenamiento que conozcamos. Acorde al problema, una definición de compararque hicimos nosotros y es correcta es la siguiente:

//C++
bool comparar(int a, int b) //retorna verdadero si a precede a b
{
	if(a%m!=b%m) return a%m<b%m; 
	if(a%2!=b%2 && a%2!=-(b%2)) return (a%2)!=0;
	if(a%2==0) return a<b;
	return a>b;
}

Por último, es importante observar que la cantidad de números a ordenar puede ser bastante grande (hasta 10.000), por lo que casi seguro (no lo probamos) usar un algoritmo de ordenamiento de complejidad O(N^2) nos de TLE (por ejemplo: inserción, selección, burbuja), mientras que un método más eficiente, como merge sort, de AC.

Extra: en C++ existe una librería llamada algorithm que contiene a la función sort (entre otras), que nos ahorraría tener que implementar el método de ordenamiento; con sólo almacenar la entrada en un arreglo y definir la función de comparación ya podemos solucionar el problema (click aquí para más información). En la mayoría de los demás lenguajes también existen métodos que trabajan de forma similar.

Problema 8: The Greater One Digit Number

La primer observación importante es: los números pueden ser muy grandes (hasta 10^100, es decir 100 dígitos), por lo que no entrarían en una variable numérica (en la mayoría de los lenguajes, particularmente cierto en C++), debemos usar una cadena de caracteres para leerlos o hacerlo dígito por dígito como si fueran caracteres.

Luego de leer los números (o mientras los leemos) tenemos que calcular las sumas de sus dígitos y estos valores seguro entrarán en una variable de tipo int de C++, por ejemplo, ya que a lo sumo estas sumas valdrán 99*9 = 891.

Una vez hecho esto, simplementa resta seguir calculando sumas de dígitos de los números resultantes hasta que estas sumas tengan un solo dígito y finalmente responder acorde a lo que pide el enunciado (if-else).

Problema 9: Super Primes Engage

Problema 9 de Secundaria.

Problema 10: Building Walls

Problema 7 de Secundaria.

Categoria Paradigmas

Problema 1: Easy Problem

La dificultad de este problema estaba en la implementación, ya que es tediosa y díficil de seguir, pero básicamente es hacer lo que pide.

Paso a explicar brevemente lo que realizamos nosotros en nuestra solución:

  • Mantenemos 5 estrucuturas:
    1. Un vector probAc de 9 posiciones, donde guardamos cada AC que consiguio un problema.
    2. Otro vector timeAc de 9 posiciones, donde para cada problema vamos sumando los tiempos en que fueron aceptados.
    3. Otro vector submitAc de 9 posiciones, donde para cada problema vamos guardando la cantidad de submits que necesito para el accepted.
    4. Y un mapa teamsAc <string, map<char, int> donde vamos guardando si un equipo metio un problema. Por ej, mapa["rejoint"]['A'] = 1, significa que el equipo rejoint metio el problema A.
    5. Y por último un mapa teamsRe <string, map<char, int> donde vamos contando para cada equipo, la cantidad de R(rejecteds) que tuvo con un problema.
  • Lo que vamos haciendo es leer las entradas y hacer lo siguiente:
    • Si el problema dio R, al equipo le sumamos uno en teamsR.
    • Si dio A y el equipo todavía no metio este problema (nos fijamos en teamsAc):
      1. Sumamos en uno probAc, en el indice del problema que corresponda.
      2. Sumamos el tiempo en timeAc, en el indice del problema que corresponda.
      3. En submitAc sumamos 1 + teamsRe[team][prob], ya que necesitamos la cantidad de rejecteds que tuvieron más el accepted.
      4. Y guardamos en teamsAc el dato que este equipo ya metio este problema.

Por último, al momento de generar la salida, vamos recorriendo las 4 primeras estructuras para mostrar y calcular los datos.

Seguramente se puede simplificar utilizando menos estructuras, pero le dejamos al lector esta tarea, teniendo la idea de la solución.

Problema 2: Amusing numbers

Primero, es sencillo observar que hay 2^x números de x dígitos, dado que los dígitos solo pueden ser 5 o 6. Sabiendo esto podemos observar lo siguiente:

  1. Si 1 <= k < 3, el k-ésimo número tiene 1 dígito
  2. Si 3 <= k < 7, el k-ésimo número tiene 2 dígitos
  3. Si 7 <= k < 15, el k-ésimo número tiene 3 dígitos
  4. Si 15 <= k < 31, el k-ésimo número tiene 4 dígitos

De forma general: si 2^j-1 <= k < 2^(j+1)-1, el k-ésimo número tiene j dígitos

Ahora entonces, para cada caso de prueba podemos obtener j de manera sencilla con una iteración. Además esta forma de obtener la cantidad de dígitos es muy eficiente, ya que 2^50-1>10^15 y entonces j será menor que 50.

Una vez que obtenemos j podemos decir que tenemos un rango [l,r) con un tamaño de 2^j, donde l = 2^j-1 y r = 2^(j+1)-1. En este rango inicial se encuentran todos los números con j dígitos, y es bastante intuitivo pensar que podemos dividir al rango en dos partes:

  1. [l, (l+r)/2) -> los números cuyo dígito más significativo es 5
  2. [(l+r)/2, r) -> los números cuyo dígito más significativo es 6

Una vez que identificamos en que mitad se encuentra nuestro k, sólo es cuestión de seguir aplicando esta división del rango en el que estamos parados sucesivamente y así lograr obtener la respuesta. Nuestra implementación de esta parte final de la solución:

//C++
typedef long long ll;

void solve(ll l,ll r,ll k) // [l,r)
{
	ll m;
	while(l<r-1)
	{
		m=(l+r)/2;
		if(k<m)
		{
			r=m;
			cout << '5';
		}
		else
		{
			cout << '6';
			l=m;
		}
	}
	cout << "\n";
	return;
}

Con la explicación dada es fácil ver que la complejidad de la solución es O(log k)

Problema 3: How to Handle the Fans

Este problema se soluciona con una estructura particular de datos que se llama Segment Tree.

Es una de las primeras estructuras "raras" que se aprenden al momento de entrar en la Programación Competitiva, así que recomendamos leer sobre la misma.

La solución sale con una implementación dinámica de Segment Tree (ya que los valores se modifican), para nuestra solución utilizamos RMQ de la implementación que tenemos en nuestro notebook robadatomada del Diego. Link a la implementación de RMQ

El único cambio que hicimos fue cambiar el MAXN por el que pide el problema.

Problema 4: Queue (Pro)

Probablemente el problema más difícil de esta categoría.

Algunos puntos clave sobre nuestra solución son los siguientes:

  1. Supongamos que contamos con tres estructuras claves
    1. Un vector de pares (pair<int,int> en C++), ordenado de menor a mayor, donde cada elemento es un par <altura, cantidad de personas más altas a la izquierda>. Llamemos a este vector V, y a las componentes del i-ésimo par <h_i, c_i>
    2. Un vector que contendrá la respuesta final al problema e iremos llenando a medida que avanza el prorgama, llamemosló ANS
    3. Un conjunto de posiciones disponibles (que aún no han sido ocupadas) ordenado de menor a mayor, llamemosló S
  2. Si recorremos a V en el orden que se encuentra, cuando vayamos a procesar la j-ésima persona (cada par de V representa una persona) estaremos seguros de lo siguiente:
    1. Todos las personas previamente procesadas no son más altas que la actual.
    2. Todas las personas que sean procesadas posteriormente serán más altas que la actual o tendrán la misma estatura pero se ubicarán más a la derecha que la persona actual en el orden final de la respuesta. Esto último es así porque justamente V está ordenado de menor a mayor (cuando la altura es igual se ordena de menor a mayor teniendo en cuenta el segundo campo del par).

Con esto en mente es fácil pensar que, entonces, para saber la posición final de h_j (es lo que importa de cada persona para responder) simplemente basta con encontrar la (c_j)-ésima posición disponible en S. Es decir que podemos resolver el problema utilizando el siguiente pseudocódigo:

  1. Para cada elemento de V, si llamamos j a la posición de V en la que nos encontramos en cada paso
    1. Insertar la altura h_j en el vector ANS, en la posición correspondiente al valor que indique el (c_j)-ésimo elemento de S
    2. Eliminar de S el elemento utilizado

Para lograr el aceptado además necesitamos hacer esto de manera eficiente, y la clave está en qué estructura usar para S (ya dijimos que V y ANS podían ser vectores). Para el que conoce el set de C++, parece ser la estructura más adecuada, sin embargo no existe función o método que encuentre el k-ésimo elemento de un set de forma eficiente. Lo único que existe (o al menos eso creo) es la función nth_element pero tiene una complejidad lineal, y necesitamos complejidad logarítmica para lograr el aceptado.

Esto nos lleva a tener que utilizar una nueva estructura, y la que aparece es un árbol balanceado. En si, los set de C++ están internamente implementados sobre árboles balanceados, pero no cuentan con la funcionalidad que necesitamos. Para salvar este problema podemos implementar uno a mano o usar uno que ya existe y está implementado en una librería un poco rara de C++ (más información aquí).

Problema 5: Atoms in the Lab

El problema fácil de la categoría.

Analizando un poco el crecimiento de los atomos podemos ver que cumple la siguiente función:

Total Atomos en tiempo t = f(t) = n * k^t

Entonces esto se puede solucionar a lo bruto probando dentro de un bucle for con t, hasta que nos de más que m.

La otra parte importante del problema es tomar los datos como long long ya que el long o int queda chico para el problema.

Hay una entrada tricky, que puede dar unos WA que es cuando n > m.

Problema 6: RK Sorting

Este problema sale teniendo en cuenta dos cosas:

  1. La estructura en la que guardamos nuestros "datos".
  2. Armando una función de comparación para el sort.

La estructura en particular que arme yo es media rebuscada (puede salir con otra).

Lo que hago primero es cargar un map<int, pair<int,int>> donde la key es el número que se lee, y en el par cargo la cantidad de apariciones y el primer indíce.

Luego con ese map, cargo un vector de ternas pair<pair<int,int>,int>(número, cantidad de apariciones, primer indíce), y luego ordeno el vector con la función de sort que defini según lo que pide el problema.

Problema 7: Encode Integer

Este problema era bastante sencillo. Tal vez el enunciado no era del todo claro pero en resumen decía: dado un entero N, encontrar el menor entero M (M>0) tal que el producto de los dígitos de M sea igual a N. La solución es simplemente intentar poner todos los dígitos 9 posible, luego todos los 8, luego los 7 y así hasta el 2. Esto es bastante fácil de implementar. Hay dos casos que debemos manejar por separado:

  1. Si N = 0 la respuesta es 10 (notar que el enunciado dice M>0)
  2. Si N = 1 la respuesta es 1.

Nuestra implementación del caso general:

//C++
vector<int> ans;
for(int i=9;i>=2;i--) while(n%i==0)
{
	ans.push_back(i);
	n/=i;
}
if(n!=1) cout << "-1\n";
else
{
	for(int i=ans.size()-1;i>=0;i--) cout << ans[i];
	cout << "\n";
}

Categoria Libres

Problema 1: Grouping Dishes

Lo complicado del problema es parsear la entrada. Hay varias formas de hacer esto. Cuando ya tenemos parseada la entrada, es cuestion de guardar cada ingrediente en un map<string, vector<string>>. Donde la key es el ingrediente, y se le va asociando las diferentes comidas.

Por último es cuestión de recorrer el map, y solo mostrar aquellos ingredientes que tengan más de 1 comida asociada.

Para que las comidas esten lexicograficamente ordenadas, es solo cuestión de mostrarlas ordenada por un sort.

Problema 2: Reverse Pairs

Nuestra solución se basa en el siguiente pseudocódigo:

  1. Declarar alguna estructura de datos correspondiente (más info al final)
  2. Mientras haya más datos que leer
    1. Leer el siguiente número (llamemosló X)
    2. Buscar en la estructura todos los números que sean mayores que 2*X y sumar la cantidad encontrada a la respuesta
    3. Insertar X en la estructura.
  3. Mostrar la respuesta

Como el conjunto de datos puede ser grande, ninguno de los pasos 2.1 y 2.2 puede hacerse revisando todos los elementos de la estructura, ya que la complejidad total sería cuadrática (TLE). Para lograr el Aceptado necesitamos encontrar una estructura que nos permita hacer ambos pasos en complejidad logarítmica, derivando en una complejidad total O(NlogN) si N es la cantidad de datos de entrada.

El paso 2.3 nos sugiere que lo más sencillo es insertar los datos de forma ordenada (de menor a mayor por ejemplo). Además esto acarrea una ventaja para con el paso 2.2: para saber cuántos de los números de la estructura son mayores a algún valor podemos obtener la posición del upper bound del valor dado y restársela al tamaño (cantidad de elementos) de la estructura.

Sin embargo hay pequeñas complicaciones para implementar esto en C++ (no se como es en Java y otros lenguajes) que a continuación mencionamos y salvamos.

Analizando un poquito la solución sugerida previamente parece que la estructura a usar es un multiset (los valores pueden repetirse), pero el problema es que "obtener la posición del upper bound del valor dado" sigue siendo complejidad lineal respecto al tamaño del set porque no podemos hacer diferencia de iteradores de un set ni nada que nos de la posición de un elemento (o un iterador a un elemento) o su upper bound en complejidad logarítmica.

Entonces la solución que nos queda es usar algún árbol balanceado que nos permita insertar elementos y saber sus posiciones (o las de su upper bound) siempre con complejidad logarítmica. En si, los sets de C++ están implementados sobre árboles balanceados internamente, pero evidentemente algo les faltó y para resolver este problema tenemos que usar algo como un "set mejorado". Por suerte existe una estructura ya definida en una librería bastante rara que tiene implementada esta mejora (para más información click aquí).

Al momento de usarla hay que tener cuidado en cómo manejar el hecho que los datos pueden repetirse. Por lo que yo se, no existe forma mágica de hacer que este set mejorado se transforme en un multiset mejorado, debemos hacerlo "a pata", pero después de pensarlo un ratito podremos ver que es bastante sencillo de hacer.

Problema 3: Friend Circles

Este problema es encontrar las componentes conexas en el grafo dado en el input. Al ser bi-direccional, se pueden contar corriendo simples DFS.

Problema 4: Binary Watch

Aclaración: en la competencia el problema solicitaba que se muestre la cantidad de horas que cumplen con lo enunciado y no que las muestre a cada una de ellas.

Este problema sale con brute force(fuerza bruta).

Haciendo un doble for anidado:

for(h=0;h<12;h++){
	for(m=0;m<60;m++){
		if(cant_bits(h)+cant_bits(m) == N) count++;
	}
}

Luego mostramos nuestra variable count(contador), y listo.

Formas de contar bits, hay varias, pero compartimos la que usamos:

int cant_bits(int x){
	int cant=0;
	for(int i=0;i<6;i++){ //controla los 6 bits menos significativos
		if(x&(1<<i)) cant++;
	}
	return cant;
}

Problema 5: Kill Process

Aclaración: el link de arriba contiene otro análisis de la solución (más profundo y detallado).

Este problema es cuestión de armar el árbol con el input dado, y luego, teniendo el PID a eliminar, sólo necesitaremos de hacer un DFS (solamente hacia abajo en el árbol) desde ese nodo, e ir guardando los PID que vamos recorriendo en algún contenedor (vector por ejemplo).

Por último simplemente ordenamos el vector y lo mostramos.

Problema 6: Climbing Stairs

Aclaración: en el contest el límite era N<=50, no sabemos cuál es el del juez del link de arriba (probablemente sea el mismo).

Si se analiza el problema se puede ver la siguiente recursividad:

f(n) = f(n-1) + f(n-2)
con
f(0) = 1
f(1) = 1

Es Fibonacci!! Pero, en el caso de que la entrada sea 0, la respuesta es 0. Este es el caso tricky que puede romper el análisis.

Como N<=50, una implementación recursiva directa de Fibonacci va a dar TLE, ya que su complejidad es O(2^N). Para solucionar este problema y conseguir la eficiencia necesaria podemos memorizar los cálculos en la recursividad (DP) o hacer el cálculo del N-ésimo fibonacci de forma "ascendente"; ambas soluciones de complejidad O(N), que es más que suficiente para el problema.

Extra: existe una solución del cálculo del N-ésimo Fibonacci con complejidad O(logN) basada en exponenciación de matrices para el que quiera investigar (no se asusten, no es tan complicada).

Problema 7: The Cube

Este fue el único problema que no nos salió en la competencia (logramos el aceptado después que terminó).

Para resolver el problema en algún sentido se podría decir que definimos un grafo implícito donde cada nodo está dado por la posición en el tablero que tienen "el cubo" (inicialmente en B) y "la persona" (inicialmente en S). Entonces lo que debemos hacer ahora es encontrar el camino mínimo entre el nodo inicial (B,S) y el nodo final, que será alguno en el que "el cubo" este en la posición de T y "la persona" en cualquier lado. Entonces simplemente podemos correr un Dijkstra para calcularlo.

Todo nodo tiene a lo sumo 4 nodos adyacentes porque la persona se puede mover arriba, abajo, derecha o izquiera. Siempre para que dichos movimientos sean posibles debemos llegar a una casilla vacía o también puede pasar que nos movamos a la casilla en donde se encuentra "el cubo", y entonces debemos mover el cubo a la casilla siguiente, en el mismo sentido que se movió "la persona".

La complejidad final de la solución es O(r^2c^2 log(r^2c^2)), que es suficiente. Durante la competencia estabamos intentando implementar una solucion O(rc log(rc)), pero se volvía todo mucho más difícil de implementar y no logramos hacerlo de forma correcta.

Problema 8: FNDI's Network

Calcular la suma de las distancias del árbol de cobertura mínimo del grafo completo en el que los nodos son todos los puntos del input. Se puede usar Prim o Kruskal, nosotros no tuvimos complicaciones (usamos Kruskal con UnionFind), pero sabemos de equipos que sí obtuvieron varios WA, muy probablemente haya sido por precisión.

Problema 9: El Dorado

Existe una dinámica que resuelve este problema de manera bastante sencilla (no sabemos si hay otra solución, pero sospechamos que sí, y más eficiente que la nuestra). La función recursiva que implementamos es F(i,k) = sumatoria_j_desde_i+1_hasta_n(F(j,k-1)) con a_j>a_i Donde en F(i,k), i indica que a_i es el último (más a la derecha) entero que forma parte de la subsecuencia creciente y k indica cuántos elementos más debemos agregar a la subsecuencia para encontrar una válida.

Para implementar la suma inicialmente lo hicimos directamente como dice la fórmula de arriba pero obtuvimos TLE, la complejidad es O(n^2*k). Para obtener el aceptado hicimos algunas mejoras que a nuestro entender no cambian la complejidad a grandes rasgos (misma función O), pero fue suficiente. Estas mejoras fueron:

  1. Antes de llamar a F, cargamos un vector para cada elemento que contiene cuales son los elementes que pueden ser siguientes a este.
  2. Agregamos un caso base que retorna 0 cuando k>n-i
You can’t perform that action at this time.