Logramos que nuestra universidad fuera sede por primera vez! Muchas gracias a Exequiel Rivas por la organización.
Problemset
http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf
Scoreboard Final
http://torneoprogramacion.com.ar/2015/09/27/resultados-tap-2015/
Juez Online
A:
http://coj.uci.cu/24h/problem.xhtml?pid=3381
B:
http://coj.uci.cu/24h/problem.xhtml?pid=3382
C:
http://coj.uci.cu/24h/problem.xhtml?pid=3383
D:
http://coj.uci.cu/24h/problem.xhtml?pid=3384
E:
http://coj.uci.cu/24h/problem.xhtml?pid=3385
F:
http://coj.uci.cu/24h/problem.xhtml?pid=3386
G:
http://coj.uci.cu/24h/problem.xhtml?pid=3387
H:
http://coj.uci.cu/24h/problem.xhtml?pid=3388
I:
http://coj.uci.cu/24h/problem.xhtml?pid=3389
J:
http://coj.uci.cu/24h/problem.xhtml?pid=3390
K:
http://coj.uci.cu/24h/problem.xhtml?pid=3391
Soluciones
Problema A – AM/FM
Supongamos que tenemos el punto óptimo. El punto óptimo está en la intersección de áreas de algunas estaciones. Cualquier punto que tome que pertenezca a esa intersección va a ser igual de óptimo. Tenemos dos casos:
- Si la intersección es un círculo, entonces en el centro hay una estación por lo que puedo mover el punto en el centro de esa estación.
- Si la intersección no es un círculo, entonces está formada por la intersección de dos o más círculos no concéntricos. Puedo mover el punto al punto en donde algún par de circunferencias de esta intersección se cruzan.
Hemos demostrado que solo basta con probar los centros de las estaciones O(N) y las intersecciones entre las circunferencias O(N^2) como posibles candidatos. Solo resta buscar con fuerza bruta O(CANDIDATOS*N) cual es el candidato con más estaciones.
Problema B – Buen kilo de pan Flauta
Debemos hacer búsqueda binaria sobre la respuesta. Si fijamos una cantidad mínima de triángulos en cada división, podemos ir tomando de manera greedy en O(10^6) y ver si es posible o no lograr tal cantidad mínima.
Problema C – CompuTenis recargado
Solo tenemos que simular el partido.
Problema D – Directo a la felicidad
Para cada componente del grafo, o bien podemos poner estadios en todas las ciudades o bien agregar rutas y transformarlo en completo. Simplemente elegir la opción de menor coste y sumar el resultado de cada componente.
Problema E – Empaquetamiento perfecto
Próximamente! (en unos días, vayan pensando en estados y exponenciación de matrices)
Problema F – Favoritismo inducido
Planteamos una dinámica sobre el árbol. Dado un nodo v pintado de color c, cual es el índice de disturbios mínimo que se puede lograr mirando solo el subárbol de raíz en v? Esto es f(v, c). Para calcular f(v, c), simplemente para cada hijo de v, pruebo asignarle cada uno de los colores y obtengo el mínimo de su subárbol (acá uso f recursivamente) y me quedo con el mínimo.
Problema G – Genética alienígena II
El proceso de convertir la cadena sería ir matcheando un sufijo de la primer cadena y un sufijo de la segunda. El sufijo de la primer cadena se va a ir invirtiendo ocasionalmente. Una primera observación es que si sabemos cual es el sufijo de la primer cadena, podemos recuperar el sufijo de la segunda porque ambas tienen la misma cantidad de carácteres.
El truco está en notar que el sufijo de la primer cadena en cualquier estado es una substring de la cadena con la que empecé (que puede estar invertida). Por lo tanto para describir el estado solo basta con un (i, j, inv) donde inv es 1 o 0.
Con esto puedo recuperar el sufijo de la segunda haciendo j-i+1. Ya pudiendo describir el estado eficientemente podemos probar todo haciendo una dinámica, que tome un estado y diga cual es la mínima cantidad de movimientos necesarios.
Problema H – Haciendo la tarea
La cantidad de restas es pequeña. Podemos simular el proceso e imprimir cuantas restas hicimos.
Problema I – Invasión extraterrestre
Como N<=1000 podemos agregar todos los sufijos de ambas cadenas a una lista. Imaginemos primero que eso de que cambian de frecuencia no pasa, es decir sólo tenemos que matchear. Tenemos todos los sufijos y los ordenamos. Para cada sufijo i de una palabra, el siguiente sufijo (i+1) va a ser con el que más caracteres tenga en común al comienzo (no existe otro sufijo que tenga más carácteres al comienzo en común con i que i+1). Si el siguiente sufijo es de la otra palabra, los caracteres que tengan en común al comienzo determinan una subcadena en común entre ambas cadenas. Prestemos atención, para cada posición de la primer cadena (en realidad para cada sufijo) estamos encontrando la subcadena con más caracteres en común. Osea que mirando todas las posiciones (sufijos) y sacando un máximo ya tengo la respuesta.
Por último, para lidiar con los cambios de frecuencias hay que ‘normalizar’ los sufijos. Antes de agregar el sufijo a la lista lo transformo. Voy de izquierda a derecha. Si ese caracter no apareció antes la transformo la menor letra que no haya sido usada. Si el carácter ya apareció, la transformo a la letra que había usado antes.
Ej:
zzzybbx -> aaabccd
azmmd -> abccd
Luego aplico el algoritmo ya explicado. Se provee una implementación muy clara realizada por Emilio Lopéz
http://sprunge.us/SZIW?c++
Problema J – Jugando con Piedras II
Lo esencial es resolver el problema primero para 1, 2 y 3 pilas, luego la estrategia general se puede deducir viendo esos tres casos. Sea E la estrategia de jugar inverso a la última jugada de tu oponente. Es decir, sacar N piedras de la pila que tu rival saco 1, sacar N-1 de la que tu rival saco 2, etc. Si el segundo jugador puede ganar siguiendo la estrategia E - es decir luego de k turnos de sacar N+1 (entre ambos) el primero no puede jugar – usa esa estrategia. Si no puede, es decir el primero tiene una jugada ganadora JG que impide al 2do seguir con la estrategia E, hagamos que el primero empieze con JG y siga la estrategia E con las jugadas del segundo. Es claro que llegamos a la situación donde el 2do no podía jugar y en este caso el primer jugador tiene asegurada la victoria.
Problema K – Kimetto, Kipsang y Kipchoge
Tenemos que mantener un par de cosas. Primero, para cada posición i, cual es la siguiente posición j tal que S[i]=S[j], llamemosle next (next(i)=j). Podemos usar varios sets para hacer esto. Lo mismo para la posición anterior, ant(j)=i.
Ahora dada una query E k podemos reducir el problema a buscar en el rango [0, k] cual es el máximo ant. Si mantenemos los valores de ant en un arreglo, sacar el máximo en un rango se puede hacer eficientemente con un segment tree!
Sólo resta ver como actualizar los next y los ant en cada query.
Me pudieran ayudar a corregir el bug en mi solucion al problema D Directo a la felicidad porque hago eso mismo usando disjoint set, gracias de antemano
ResponderBorrar#include
#define MAX 1001
using namespace std;
int P[MAX], level[MAX], ady[MAX][MAX], nodos[MAX], rutas[MAX];
bool state[MAX];
void create_set(int x){
P[x] = x;
level[x] = 0;
}
int set_of(int x){
if(x != P[x]) P[x] = set_of(P[x]);//while(x != P[x]) x = P[x]; otra variante
return P[x];
}
void join(int x, int y){
int xx, yy;
xx = set_of(x);
yy = set_of(y);
if ( level[xx] > level[yy] )
{
P[yy] = xx ; nodos[xx]++;
}
else
{
P[xx] = yy;nodos[yy]++;
}
if( level[xx] == level[yy] ) level[yy]++;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M, R, E;
cin >> N>> M>> R>>E;
for( int i = 1; i <= N; i++ )
{
create_set(i);nodos[i] = 1;
}
for( int i = 1; i <= M; i++ )
{
int x, y; cin >> x >> y;
ady[x][y] = 1;
ady[y][x] = 1;
if( set_of(x) != set_of(y) )
{
join(x, y);
}
}
for( int i = 1; i < N; i++ )
{
for( int j = i+1; j <= N; j++ )
{
if( ady[i][j] == 0 && set_of(i)==set_of(j) ) rutas[set_of(i)]+=R;
}
}
long long sum = 0;
for( int i = 1; i <= N; i++ )
{
int tt = set_of(i);
if( state[tt] == 0 && nodos[tt] != 1 )
{
//cout << rutas[P[i]] << endl;
state[tt] = true;sum+=min(nodos[tt]*E,rutas[tt]);
}
}
cout << sum << "\n";
return 0;
}
Me parece que tu error está en que join une dos componentes, no dos nodos. Cuando hacés nodos[xx]++ deberías agregarle el tamaño de la otra componente, no sumarle uno. De todas maneras usar union-find es un overkill para el problema. Es más fácil hacer dfs teniendo en cuenta que la cantidad de aristas en un grafo completo K_n es (n*(n-1))/2
Borrarok gracias, probare con el dfs
ResponderBorrarPueden dar mas detalles sobre como resolver el problema A? Tengo varios intentando resolverlo, y no entiendo cual es la solucion propuesta. Pueden extender mas la solucion?
ResponderBorrarPara cada circulo:
BorrarAgrego su centro a candidatos
Para cada par de círculos:
Si se interesecan en los puntos p y q:
Agrego p y q a candidatos
Respuesta=0
Para cada punto p en candidatos:
Q=0
Para cada estación e:
Si p está dentro de e:
Q++
Respuesta =max( respuesta, Q)
imprimir respuesta
Hola me podrían decir como sacaron los puntos de intersección entre dos circunferencias en c++, por que se sacarlos analíticamente pero no pasarlo a código. gracias.
ResponderBorrarhttp://math.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect
Borrares sólo escribir la formula(s)
Este comentario ha sido eliminado por el autor.
ResponderBorrarBuenas, antes que nada gracias por compartir esta ayuda.
ResponderBorrarEstoy tratando de resolver todos los problemas utilizando el lenguaje Swift, pero no puedo conseguir más inputs/outputs de prueba para verificar mis soluciones.
Entré, por ejemplo, a http://coj.uci.cu/24h/problem.xhtml?pid=3381, luego de crear una cuenta en ese sitio, pero allí tampoco he encontrado datos de prueba. He revisado las FAQ de ese sitio, pero tampoco.
Si pudieran postearlos por aquí o pasarme un link a donde se encuentran o las instrucciones, me vendrían de maravillas.
¡Gracias!
Los casos de prueba no son públicos, por lo que no los vas a conseguir. Intenta buscar el error en el código y hacer más inputs/outputs propios para debuggear. Si después de varios días no encontrás el error en tu código, siempre podés pedir ayuda a alguien más. Por ejemplo está el grupo de ICPC Latinoamérica: https://groups.google.com/forum/#!forum/latinoamerica-icpc , donde te pueden dar una mano.
BorrarMartín, ¡gracias por la respuesta!
ResponderBorrarLo que estaba buscando no era solucionar un error en particular sino que revisar si lo que hice funciona con más casos Tendré que elaborar varios casos propios entonces.
¡Saludos!