¡Buenas tardes chicos!
Este Sábado 07/07 habrá una competencia en HackerRank. Los problemas serán seleccionados de las competencias de USACO (USA Computing Olympiad).
Será de 16:00 hs a 20:00 hs y consistirá de tres/cuatro problemas.
En cuanto a dificultad, está pensado para competidores de nivel 3 (Silver/Gold de USACO)
Link para la competencia: https://www.hackerrank.com/simulacro-oia-2
Saludos,
Gastón
¡Qué bueno!
Este horario me cae mejor que el de la semana pasada, ¿es posible unirse una vez comenzado el contest?
La vez pasada ni probé porque podía solo la última hora/hora y media.
EDIT: Bueno, me inscribí por las dudas. Creo que no debería haber problema así.
Si, la inscripción esta abierta hasta el fin de contest
Y el tema del horario es mas cómodo, si, jaja. El curso de La Matanza termina a las 14 y era imposible que llegaran a tiempo (salvo que el sábado pasado no tuvimos clase asi que no hubo drama 
)
EN CONSTRUCCIÓN
El enunciado nos dice que originalmente había N pilas, y que todas las pilas tenían la misma cantidad de fardos de heno. La idea clave es que al moverse fardos de heno de una pila a la otra, la cantidad total de fardos de heno no varía y es un invariante (el fardo de heno que sale de una pila, se agrega en otra).
Como originalmente todas las pilas tenían la misma cantidad de fardos de heno, si llamamos c a esa cantidad, sabemos que en total habrá c \cdot N fardos de heno. Por otro lado, esta cantidad total de fardos de heno podemos obtenerla sumando la cantidad que hay en cada pila actualmente. Si llamamos T a la suma de las cantidades de las pilas que vienen en la entrada, entonces tenemos la siguiente relación:
Donde tanto T como N podemos calcularlos con las cantidades que vienen en el enunciado.
Finalmente, para cada pila podemos calcular cuántos fardos de heno le faltan o le sobran respecto de la cantidad que tenían originalmente. Si llamamos a_i a la cantidad de fardos de heno que tiene actualmente la pila i, entonces c-a_i será un número positivo si le faltan fardos de heno a la i-ésima pila, y será un número negativo si le sobran fardos de heno a dicha pila. Llamemos F y S a la cantidad total de fardos de heno que faltan y que sobran respectivamente.
Ejercicio: Ver que F = S, viendo cómo pueden variar ambas cantidades al mover un fardo de heno de una pila a otra y usando que originalmente F = S = 0
Para volver a cada pila a la cantidad original, lo óptimo es sacar un fardo de heno de alguna pila a la que le sobre, y moverlo a alguna que le falte, en total reducimos tanto F como S en uno haciendo esto. Por lo tanto en total realizaremos F movimientos (o S movimientos).
Ejercicio: Concluir que la cantidad total de movimientos que hay que realizar es:
#include <bits/stdc++.h>
#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long tint;
int main()
{
tint n;
while (cin >> n)
{
tint t = 0;
vector<tint> a (n);
// Leemos la entrada y obtenemos la cantidad total de fardos de heno
forn(i,n)
{
cin >> a[i];
t += a[i];
}
// Calculamos la respuesta
tint ans = 0;
forn(i,n)
ans += abs((t/n)-a[i]);
// Imprimimos la respuesta
cout << ans / 2 << "\n";
}
return 0;
}
Al leer el enunciado lo primero que debería llamarnos la atención es que en las cotas del problema sabemos que la cantidad total de vacas N \leq 20. Ahora, ¿cuántas formas de elegir un subconjunto de los N números dados hay?. Para formar un subconjunto, podemos pensar que recorremos las vacas una por una, y por cada una de ellas tenemos dos opciones: O bien la vaca en cuestión se encuentra en el subconjunto o no. Por lo tanto, como cada vaca puede estar o no estar, tenemos \underbrace{2 \cdot 2 \cdot 2 \dots \cdot 2}_{N} = 2^{N} \leq 2^{20} = 1.048.576 \sim 10^6 subconjuntos posibles.
Por lo tanto, una solución posible sería probar todos los subconjuntos posibles y por cada uno de ellos chequear si se realiza o no un acarreo al realizar la suma de los pesos de las vacas en el subconjunto. Como respuesta al problema queremos la máxima cantidad de vacas que puede tener un subconjunto con dicha propiedad (que no se genera acarreo al sumar los pesos).
Entonces, solo resta resolver una pregunta. ¿Cómo sabemos si al sumar los pesos de las vacas de un cierto subconjunto se realiza acarreo o no?
Si uno encolumna a los pesos (en la forma que uno suma los números en papel y lápiz), se puede ver que uno realiza acarreo si y solo si la suma de los pesos en alguna columna es mayor o igual a 10. Por lo tanto, para que no se genere acarreo, la suma de cada una de las columnas debe ser menor a 10.
Por ejemplo:
La implementación para ver el acarreo no debería generar demasiadas complicaciones, pero para ver cómo iterar en subconjuntos, recomiendo ver este post de la wiki que habla al respecto.
#include <bits/stdc++.h>
#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long tint;
const tint maxCifra = 16;
tint sumaCifra[maxCifra];
bool noTieneAcarreo(vector<tint> &peso, vector<tint> &indices)
{
forn(j,maxCifra)
sumaCifra[j] = 0;
for (auto i : indices)
{
tint n = peso[i];
tint j = 0;
while (n > 0)
{
sumaCifra[j++] += (n % 10);
n /= 10;
}
}
bool todosMenoresADiez = true;
forn(j,maxCifra)
todosMenoresADiez &= (sumaCifra[j] < 10);
return todosMenoresADiez;
}
int main()
{
tint n;
while (cin >> n)
{
vector<tint> peso (n);
forn(i,n)
cin >> peso[i];
tint ans = -1;
forn(b,(1LL << n)) // probamos todos los subconjuntos
{
vector<tint> indices;
forn(i,n)
if ((b & (1LL << i)) != 0) // si la i-esima vaca es elegida...
indices.push_back(i);
if (noTieneAcarreo(peso,indices))
ans = max(ans,tint(__builtin_popcountll(b))); // me fijo si ahora consigo un subconjunto con mas vacas.
}
cout << ans << "\n";
}
return 0;
}
Luego de leer el enunciado, se puede modelar el problema con un grafo de N nodos (uno por cada campo) y M aristas bidireccionales (una por cada tramo que conecta un par de campos). Al decir que “entre dos campos hay, como máximo, un tramo”, nos están diciendo que nuestro grafo no tiene multiejes. Al decir que “es posible moverse entre cualquier par de campos, siguiendo una secuencia de tramos determinados”, nos están diciendo que el grafo es conexo.
Con este modelo en mente, si llamamos d a la distancia que hay entre el nodo 1 y el nodo N en el grafo original, la tarea de las vacas consiste en encontrar una arista e tal que d_e-d se maximice, donde d_e es la distancia entre los nodos 1 y N en el grafo que es igual al original pero tiene a la arista e con el peso duplicado.
Una vez formulado de esta forma, podemos usar algún algoritmo de camino mínimo (Dijsktra, por ejemplo, dado que las aristas son positivas) para resolver el problema. Primeramente, lo utilizamos en el grafo original para calcular d. Luego, podemos iterar todas las aristas una por una, y para cada e \in E calcular d_e corriendo otra vez un algoritmo de camino mínimo.
Ejercicio: En caso de que el grafo original tenga muchas aristas, ¿qué implementación de Dijkstra conviene usar?¿ \mathcal{O}(N^2) u \mathcal{O}\left ((N+M)\log(N) \right )?
Ejercicio: Probar que la arista que hay que duplicar necesariamente pertenece a algún camino mínimo de 1 a N en el grafo original. ¿Qué ocurre si tomamos una arista que no pertenezca a ningún camino mínimo?
Ejercicio: ¿Es cierto que duplicando el peso de alguna de las aristas más pesadas que pertenecen a todo camino mínimo de 1 a N obtenemos la solución al problema?
#include <bits/stdc++.h>
#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long tint;
const tint maxN = 128;
const tint INFINITO = 1e15;
tint best[maxN];
struct Arista
{
tint salida,llegada,peso,indice;
Arista (tint ss, tint ll, tint pp, tint ii)
{
salida = ss;
llegada = ll;
peso = pp;
indice = ii;
}
};
void dijkstra (tint comienzo, vector<vector<Arista > > &ladj, tint duplicada)
{
priority_queue <pair<tint,tint> > q; // {-peso,indice}
tint n = ladj.size();
forn(i,n)
best[i] = (i != comienzo)*INFINITO;
vector<tint> procesado (n,0);
q.push({0,comienzo});
while (!q.empty())
{
tint actual = q.top().second;
q.pop();
if (!procesado[actual])
{
procesado[actual] = 1;
for (auto vecino : ladj[actual])
{
if (best[actual] + vecino.peso + vecino.peso*(duplicada == vecino.indice) < best[vecino.llegada])
{
best[vecino.llegada] = best[actual] + vecino.peso + vecino.peso*(duplicada == vecino.indice);
q.push({-best[vecino.llegada],vecino.llegada});
}
}
}
}
}
int main()
{
tint n,m;
while (cin >> n >> m)
{
// Leemos la entrada
vector<vector<Arista> > ladj(n);
forn(i,m)
{
tint ss,ll,pp;
cin >> ss >> ll >> pp;
ladj[ss-1].emplace_back(ss-1,ll-1,pp,i);
ladj[ll-1].emplace_back(ll-1,ss-1,pp,i);
}
// Vemos cuanto le lleva al gaucho su recorrido normal
dijkstra(0,ladj,-1);
tint ans = 0, d = best[n-1];
// Para cada arista duplicada, chequeamos cuanto empeora
forn(i,m)
{
dijkstra(0,ladj,i); // Dijkstra normal, solo que si usa la arista con indice i, le duplica el peso.
ans = max(ans,abs(best[n-1]-d));
}
cout << ans << "\n";
}
return 0;
}
Primero que nada, para ayudarnos a pensar, podemos pensar que las vacas están ubicadas en la recta numérica. Notemos que no importa en qué orden vienen las vacas en el enunciado, solo nos importa su lugar en la recta numérica (su coordenada x), por lo tanto podemos asumir un orden que nos sea conveniente. Vamos a asumir que están ordenadas en forma creciente, o sea x_1 \leq x_2 \leq \dots \leq x_N.
Como los paraguas pueden superponerse, si uno quiere cubrir un ancho de A, convendrá comprar el paraguas más barato que tenga ancho w \geq A. Luego, nos resultará conveniente tomar en vez del arreglo C que viene en el enunciado, uno ligeramente distinto, llamémoslo \hat{C} que cumple que \hat{C}[w] = \underset{\hat{w}\geq w}{ \min} C[\hat{w}]. En la implementacion, para calcular este nuevo arreglo, podemos tomar mínimo de sufijos yendo de derecha a izquierda (como la tablita aditiva, pero con mínimo y de derecha a izquierda en vez de izquierda a derecha). Además, implementativamente nos será conveniente pensar a los anchos indexados de cero y no de uno, pero esto es solo un detalle.
Finalmente, para resolver el problema vamos a utilizar programación dinámica de la siguiente forma:
f(i) = ``\text{el menor costo para cubrir las vacas situadas desde } x_1 \text{ hasta }x_i "
Para calcular f(i) Vamos a asumir que ya sabemos la respuesta de f(k) para todo k < i. Debemos cubrir a todas las vacas desde x_i hasta x_1. En particular, tenemos que cubrir a la vaca x_i. Para ello hay básicamente dos casos.
Por lo tanto, si vamos calculando estos valores en orden creciente de i, obtenemos la solución al problema en f(N).
#include <bits/stdc++.h>
#define forsn(i,s,n) for(tint i=(s);i<(tint)(n); i++)
#define forn(i,n) forsn(i,0,n)
#define dforn(i,n) for(tint i = tint(n)-1; i >= 0; i--)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
typedef long long tint;
const tint INFINITO = 1e16;
int main()
{
tint n,m;
while (cin >> n >> m)
{
// Leemos la entrada
vector<tint> x (n);
forn(i,n)
cin >> x[i];
vector<tint> c (m);
forn(i,m)
cin >> c[i];
// Calculamos para cada ancho, el menor precio de al menos ese ancho
dforn(i,m-1)
c[i] = min(c[i],c[i+1]);
// Ordenamos los puntos de la entrada
sort(x.begin(),x.end());
// Resolvemos el problema:
vector<tint> best(n,INFINITO);
forn(i,n)
{
best[i] = c[x[i]-x[0]]; // Caso base: Cubrir todos hasta el i con un paraguas.
forsn(k,1,i+1) // Si no cubro a todos, pruebo cubrir hasta todos los posibles anteriores.
best[i] = min(best[i],c[x[i]-x[k]] + best[k-1]); // De todas las opciones, nos quedamos con la mejor.
}
cout << best[n-1] << "\n";
}
return 0;
}
Gracias por la editorial, muy bien explicado!
Me quedé en el tercero por la mitad, trate de hacerlo con programación dinámica pero no me di cuenta de utilizar el arreglo auxiliar para guardar los mínimos.
Me gustaron mucho los problemas, simples y fáciles de implementar 
.