9/14/2008
11489 - Integer Game
Este fue el otro problema que solucione de ACM ICPC::Regional Warmup 1 (Easy version), este me pareció mas vacancito, puesto que era simplemente pura observación matemática, la idea era muy sencilla, decían que los jugadores siempre al quitar un dígito del numero deberían dejar un numero multiplo de 3, y ahora bien sabemos que un numero solo es multiplo de 3 si la suma de sus digitos es divisible por 3, ahora bien los jugadores solo podrían quitar dígitos múltiplos de 3 es decir 3,6,9 y nos garantizaban que el numero no contenia 0's, ahora vale la pena decir que la única jugada que en la que no aplicaba este procedimiento era en la primera jugada, puesto que si el numero modulo 3 no era igual a cero, entonces la primera jugada deberia ser quitar un digito que fuera congruente modulo 3 con el numero inicial, y listo. Simplemente era validar la paridad de la suma de todas las jugadas posibles y listo.
11483 - Code Creator
Este fue el problema mas fácil ACM ICPC::Regional Warmup 1 (Easy version) era simplemente hacer lo que decía el problema y quedaba listo
LINK
LINK
9/11/2008
3986 - The Bridges of Kölsberg
Enunciado
Programación dinámica, dynamic programming, DP.
dp[i][j] = Máximo puntaje que puedo alcanzar habiendo creado puentes válidos entre las primeras i ciudades del norte y las primeras j ciudades del sur.
b[i][j] = Mínima cantidad de puentes que necesito para obtener un puntaje de dp[i][j].
Notar que dp[i][j] es el máximo entre tres posibles opciones:
Código fuente
Programación dinámica, dynamic programming, DP.
dp[i][j] = Máximo puntaje que puedo alcanzar habiendo creado puentes válidos entre las primeras i ciudades del norte y las primeras j ciudades del sur.
b[i][j] = Mínima cantidad de puentes que necesito para obtener un puntaje de dp[i][j].
Notar que dp[i][j] es el máximo entre tres posibles opciones:
- dp[i-1][j-1] + valor_norte[i] + valor_sur[j], siempre y cuando la ciudad norte-i y la ciudad sur-j tengan el mismo sistema operativo. Representa la opción de conectar los dos puentes.
- dp[i][j-1]. Representa la opción de lograr un mejor puntaje ignorando la ciudad actual del sur.
- dp[i-1][j]. Representa la opción de lograr un mejor puntaje ignorando la ciudad actual del norte.
Código fuente
3340 - Hour glass
Lo resolví usando BFS, con el estado [m, n, t] donde
m = Cantidad de arena que queda en el reloj pequeño
n = Cantidad de arena que queda en el reloj grande
t = Tiempo transcurrido desde el inicio
Lo que no he podido entender, es que mi código da Accepted en el Live Archive y TJU, pero Wrong Answer en PKU.
m = Cantidad de arena que queda en el reloj pequeño
n = Cantidad de arena que queda en el reloj grande
t = Tiempo transcurrido desde el inicio
Lo que no he podido entender, es que mi código da Accepted en el Live Archive y TJU, pero Wrong Answer en PKU.
3978 - Obfuscation
Axy y yo lo hicimos recursivo. Es un backtracking pero con memoria para no repetir cálculos.
int f(int i) = Retorna la cantidad de maneras diferentes en que podemos decodificar la string dada si inicialmente nos paramos en la letra en la posición i. Si logra recurrir hasta el final, guarda la respuesta que encontró en un vector para imprimirla en caso de no ser ambigua.
Si f(0) == 0 -> Imposible
Si f(0) == 1 -> Imprimir respuesta
Si f(0) >= 2 -> Ambiguo
int f(int i) = Retorna la cantidad de maneras diferentes en que podemos decodificar la string dada si inicialmente nos paramos en la letra en la posición i. Si logra recurrir hasta el final, guarda la respuesta que encontró en un vector para imprimirla en caso de no ser ambigua.
Si f(0) == 0 -> Imposible
Si f(0) == 1 -> Imprimir respuesta
Si f(0) >= 2 -> Ambiguo
9/09/2008
Palindrom Numbers
Este problema lo encontré en dos jueces y difieren en una letra de la salida, pero en teoría son el mismo.
ZJU - Live Archive
Tuve varios problemas para poder solucionar, porque cuando lo mande a la primera me dio WA, y me dio demasiada rabia, entonces mire en el foro del live archive y ahí decían que había que agregarles unos espacios en blanco y una letra a una salida ahí, entonces cuando le agregue eso,volví a mandarlo como dos veces mas, y nada.
Entonces lo único que se me acourrio es que si tenia un sistema superior al decimal cuando lo leyera de atras hacia adelante no tubiera que voltiar los "dígitos" de dos numeros es decir por ejemplo el "13" voltearlo como "31" es un dígito en sistema 14,15 y 16. Le cambie eso y obuve el AC.
ZJU - Live Archive
Tuve varios problemas para poder solucionar, porque cuando lo mande a la primera me dio WA, y me dio demasiada rabia, entonces mire en el foro del live archive y ahí decían que había que agregarles unos espacios en blanco y una letra a una salida ahí, entonces cuando le agregue eso,volví a mandarlo como dos veces mas, y nada.
Entonces lo único que se me acourrio es que si tenia un sistema superior al decimal cuando lo leyera de atras hacia adelante no tubiera que voltiar los "dígitos" de dos numeros es decir por ejemplo el "13" voltearlo como "31" es un dígito en sistema 14,15 y 16. Le cambie eso y obuve el AC.
9/08/2008
3979 - Tower Parking
El enunciado
Después de hablar con Daniel y adivinar un rato varios detalles del problema, llegamos a la conclusión que el orden en el que salían los carros era el orden ascendente de los números parqueados, y que el ascensor apuntaba en cada piso a una posición en particular, es decir que si en el piso uno estaba apuntando el carro en la posición 1, no necesaraimente lo deberia hacer en los otros pisos. Después de esto la simulación era muy fácil.
Después de hablar con Daniel y adivinar un rato varios detalles del problema, llegamos a la conclusión que el orden en el que salían los carros era el orden ascendente de los números parqueados, y que el ascensor apuntaba en cada piso a una posición en particular, es decir que si en el piso uno estaba apuntando el carro en la posición 1, no necesaraimente lo deberia hacer en los otros pisos. Después de esto la simulación era muy fácil.
3057 - Permutation Code
El enunciado
La mayor dificultad de este problema era despejar el XOR, pero después de esto el problema era casi hacer una simulación inversa
La mayor dificultad de este problema era despejar el XOR, pero después de esto el problema era casi hacer una simulación inversa
3056 - Flow Layout
El enunciado
Era una simple simulación del enunciado, teniendo un buen manejo de las alturas relativas.
Era una simple simulación del enunciado, teniendo un buen manejo de las alturas relativas.
3055 - Symmetric Order
El enunciado
Este es de los problemas más fáciles que he hecho.
Simplemente era reorganizar el orden creciente total en uno parcial, era como hacer "uno para ti uno para mi" en donde el para ti quedaba al principio del nuevo orden y el para mi al final del nuevo orden, solo vale la pena decir que cuando el tamaño de la lista era impar, era necesario colocar el ultimo de la lista original en la mitad.
Este es de los problemas más fáciles que he hecho.
Simplemente era reorganizar el orden creciente total en uno parcial, era como hacer "uno para ti uno para mi" en donde el para ti quedaba al principio del nuevo orden y el para mi al final del nuevo orden, solo vale la pena decir que cuando el tamaño de la lista era impar, era necesario colocar el ultimo de la lista original en la mitad.
3054 - Triangle Cuts
El enunciado
Este problema era más asustador que cualquier otra cosa, y largo de implementar.
La idea era probar todas las rotaciones con todas las permutaciones de los triángulos.
Podíamos asumir que el orden de los ángulos que nos daban era estricto ("Assume that none of the triangles is flipped over so the green side of the paper is up, and the vertex angles are listed in clockwise order around each individual triangle. ").
Ahora podíamos decir que tenemos los triangulo a,b,c,d internos al grande.
Ahora bien lo que había que intentar hacer era coger el triangulo a y unir con el b en todos sus rotaciones posibles, luego de tener a-b unir el triangulo c en todas sus rotaciones posibles, luego lo mismo con d. Ahora lo que teniamos que hacer era probar si algunas de las rotaciones del triangulo grande encajaba con alguno de los triangulos que se crearon de la union de los otros triangulos pequeños, además de validar la suma de los angulos.
Ahora bien hasta aqui el programa da wrong answer, para obtener el AC tube que evaluar todas las permutaciones de los 4 triangulos, es decir repetir el procediento anterior, pero intercambiar el orden en el que juntaba los triangulos.
A otra cosa importante es que solo era necesario validar la suma de los ángulos a uno nunca le importa la relación de longitudes de los triangulos.
Este problema era más asustador que cualquier otra cosa, y largo de implementar.
La idea era probar todas las rotaciones con todas las permutaciones de los triángulos.
Podíamos asumir que el orden de los ángulos que nos daban era estricto ("Assume that none of the triangles is flipped over so the green side of the paper is up, and the vertex angles are listed in clockwise order around each individual triangle. ").
Ahora podíamos decir que tenemos los triangulo a,b,c,d internos al grande.
Ahora bien lo que había que intentar hacer era coger el triangulo a y unir con el b en todos sus rotaciones posibles, luego de tener a-b unir el triangulo c en todas sus rotaciones posibles, luego lo mismo con d. Ahora lo que teniamos que hacer era probar si algunas de las rotaciones del triangulo grande encajaba con alguno de los triangulos que se crearon de la union de los otros triangulos pequeños, además de validar la suma de los angulos.
Ahora bien hasta aqui el programa da wrong answer, para obtener el AC tube que evaluar todas las permutaciones de los 4 triangulos, es decir repetir el procediento anterior, pero intercambiar el orden en el que juntaba los triangulos.
A otra cosa importante es que solo era necesario validar la suma de los ángulos a uno nunca le importa la relación de longitudes de los triangulos.
3053 - Primary X-Subfactor Series
El enunciado.
Este problema me pareció muy vacancito, porque mezclaba un poco de todo, porque utilice bitwise para hacer unas validaciones, como mirar si el subfactor era valido, encontrar cada uno de los dígitos.
Pero la idea general del problema era empezar a generar todas las series de longitud l, es decir empezar con las de tamaño uno, luego con las de tamaño dos y así sucesivamente, vale la pena decir que habían dos formas de detener la recursividad, cuando se me acabaran los dígitos, o simplemente cuando la longitud fuera igual a la longitud del numero.
La función de bactraking que utilice, practicamente consistia en:
void gen(int n, int l), donde n es el numero al que se le calcula el subfactor y l es la longitud de la secuencia, y la llamada recursiva la hacia gen(k,l+1), donde k era el nuevo n y l+1 la siguiente longitud.
Además para evitar es pasando valores de arreglos como parametros utilice un arreglo global en donde tenia la mejor serie y otro donde tenia una serie temporal que era la que se hiba calculando.
Este problema me pareció muy vacancito, porque mezclaba un poco de todo, porque utilice bitwise para hacer unas validaciones, como mirar si el subfactor era valido, encontrar cada uno de los dígitos.
Pero la idea general del problema era empezar a generar todas las series de longitud l, es decir empezar con las de tamaño uno, luego con las de tamaño dos y así sucesivamente, vale la pena decir que habían dos formas de detener la recursividad, cuando se me acabaran los dígitos, o simplemente cuando la longitud fuera igual a la longitud del numero.
La función de bactraking que utilice, practicamente consistia en:
void gen(int n, int l), donde n es el numero al que se le calcula el subfactor y l es la longitud de la secuencia, y la llamada recursiva la hacia gen(k,l+1), donde k era el nuevo n y l+1 la siguiente longitud.
Además para evitar es pasando valores de arreglos como parametros utilice un arreglo global en donde tenia la mejor serie y otro donde tenia una serie temporal que era la que se hiba calculando.
9/07/2008
3975 - Escape from Enemy Territory
Enunciado.
Sí! Después de suficientes Time Limit Exceeded logré violar al juez con una solución que le entró en 9.4 segundos (y seguro que le tuvo que arder).
El problema se divide en tres partes:
1. Encontrar el camino más corto entre una base enemiga y cualquier casilla. Esto se hace con una sola pasada de BFS.
2. Encontrar cuál es el camino entre el inicio y el final que tenga máximo elemento mínimo. Esto es muy parecido al problema 10099 - Tourist guide de la UVa. Yo lo hice con una modificación del algoritmo de Dijkstra, pero en una de las soluciones oficiales de los jueces lo hacen con una modificación lasciva de BFS, difícil de comprender (Es más rápido). Tarea: Imprimir este código y entender por qué carajos funciona.
3. Finalmente, encontrar el camino más corto entre el inicio y el final donde ningún elemento de él sea menor que el número encontrado en el paso 2. Esto se hace con una sola pasada de BFS.
El que quiera ver el código, está en mi repositorio de Github.
Sí! Después de suficientes Time Limit Exceeded logré violar al juez con una solución que le entró en 9.4 segundos (y seguro que le tuvo que arder).
El problema se divide en tres partes:
1. Encontrar el camino más corto entre una base enemiga y cualquier casilla. Esto se hace con una sola pasada de BFS.
2. Encontrar cuál es el camino entre el inicio y el final que tenga máximo elemento mínimo. Esto es muy parecido al problema 10099 - Tourist guide de la UVa. Yo lo hice con una modificación del algoritmo de Dijkstra, pero en una de las soluciones oficiales de los jueces lo hacen con una modificación lasciva de BFS, difícil de comprender (Es más rápido). Tarea: Imprimir este código y entender por qué carajos funciona.
3. Finalmente, encontrar el camino más corto entre el inicio y el final donde ningún elemento de él sea menor que el número encontrado en el paso 2. Esto se hace con una sola pasada de BFS.
El que quiera ver el código, está en mi repositorio de Github.
3971 - Assemble
Bueno uno de los puntos a tocar en este problema es que no importa optimizar el dinero. Simplemente importa con la plata que se tiene armar el computador con la mayor calidad posible.
Algoritmo:
1. Creamos una matriz en la cual almacenamos los componenetes que nos dicen.
grid[i][j] = elemento j , del tipo i.
2. Escogemos todos los componenetes que solo tienen un elemento y los compramos (Si solo se tiene un elemento no hay como escoger otro).
3. Se ordena cada vector de componentes de tal modo que en la primera posicion quede el elemento con mayor calidad y en caso de tener la misma calidad que otro entonces el de mayor precio.
4. Intentamo hacer la compra si no nos alcanza la plata buscamos el siguiente elemento de los componentes que disminuya lo mas poco posible la calidad del computador a armar hasta que podamos comprar.
Algoritmo:
1. Creamos una matriz en la cual almacenamos los componenetes que nos dicen.
grid[i][j] = elemento j , del tipo i.
2. Escogemos todos los componenetes que solo tienen un elemento y los compramos (Si solo se tiene un elemento no hay como escoger otro).
3. Se ordena cada vector de componentes de tal modo que en la primera posicion quede el elemento con mayor calidad y en caso de tener la misma calidad que otro entonces el de mayor precio.
4. Intentamo hacer la compra si no nos alcanza la plata buscamos el siguiente elemento de los componentes que disminuya lo mas poco posible la calidad del computador a armar hasta que podamos comprar.
9/06/2008
10069 - Distinct Subsequences
Bueno casi que no hago este problema les cuento la historia.
1. Lo hago en c++. (Wrong Answer)
2. Revizo el algoritmo y corrijo un bug. (Wrong Answer)
3. Caigo en cuenta que el resultado es demasiado grande por lo cual lo intento en Java con BigInteger. (Compile Error).
4. Revizo el porque salio este error y me dice que que la clase no puede declararse publica. Lo envio sin esto (Run Time Error).
5. De la rabia que me dio al no saber porque saco Run Time Error en java. Declare todas las variables en c++ como long long y lo intento de nuevo (Wrong Answer).
6. Despues de tanto desespero me ilumino y me acuerdo que la clase debe de llamarse "Main". Lo cambio y lo envio. (Time Limit Exceeded).
Por mi salud mental dejo este problema así.
Dia siguiente.
7. Me propongo a mejorar el algoritmo para que corra más rapido en la lenteja de Java. (Time Limit Exceeded).
8. Me quedo un rato pensando en como optimizarlo al maximo y le hago más mejoras al algoritmo (Wrong Answer).
9. Bueno me dio felicidad al saber que almenos ejecuto en java pero fallo. Caigo en cuenta del caso trivial y lo mando (Accepted).
Bueno el que persevera alcanza y este ejercicio me enseño bastante de como mandar problemas en Java y mucha experiencia, jeje.
Ahora si como lo resolvi.
dp[i][j] = Número de veces en que la subcadena Z0...Zi está en la subcadena X0...Xj.
1. Lo hago en c++. (Wrong Answer)
2. Revizo el algoritmo y corrijo un bug. (Wrong Answer)
3. Caigo en cuenta que el resultado es demasiado grande por lo cual lo intento en Java con BigInteger. (Compile Error).
4. Revizo el porque salio este error y me dice que que la clase no puede declararse publica. Lo envio sin esto (Run Time Error).
5. De la rabia que me dio al no saber porque saco Run Time Error en java. Declare todas las variables en c++ como long long y lo intento de nuevo (Wrong Answer).
6. Despues de tanto desespero me ilumino y me acuerdo que la clase debe de llamarse "Main". Lo cambio y lo envio. (Time Limit Exceeded).
Por mi salud mental dejo este problema así.
Dia siguiente.
7. Me propongo a mejorar el algoritmo para que corra más rapido en la lenteja de Java. (Time Limit Exceeded).
8. Me quedo un rato pensando en como optimizarlo al maximo y le hago más mejoras al algoritmo (Wrong Answer).
9. Bueno me dio felicidad al saber que almenos ejecuto en java pero fallo. Caigo en cuenta del caso trivial y lo mando (Accepted).
Bueno el que persevera alcanza y este ejercicio me enseño bastante de como mandar problemas en Java y mucha experiencia, jeje.
Ahora si como lo resolvi.
dp[i][j] = Número de veces en que la subcadena Z0...Zi está en la subcadena X0...Xj.
9/04/2008
2825 - Decorations
DP, programación dinámica, dynamic programming. Disponible en el Live Archive y en ZJU.
Estado:
dp[i][j] = cantidad de cadenas válidas que tienen exactamente longitud i y terminan en la combinación j-ésima que le gusta al Sultán. (Declarada unsigned int dp[101][600]).
Estado:
dp[i][j] = cantidad de cadenas válidas que tienen exactamente longitud i y terminan en la combinación j-ésima que le gusta al Sultán. (Declarada unsigned int dp[101][600]).
9/02/2008
10131 - Is Bigger Smarter?
Bueno que dilema con este problemita que alfin resolvi.
2 wrong answer por el puto caso donde el peso de los elefantes era igual.
1 wrong answer por que de la emoción de que sabia que ya estaba bueno se me olvido comentar los 'cout' de prueba, jajajaja.
dp[i] = Maximo tamaño de la subsecuencia (cumpliendo las especificaciones requeridas) donde i es el ultimo elemento de ésta subsecuencia.
sol_dp[i] = Elemento anterior a 'i' de la subsecuencia.
Clic aqui para ver el enunciado del problema.
2 wrong answer por el puto caso donde el peso de los elefantes era igual.
1 wrong answer por que de la emoción de que sabia que ya estaba bueno se me olvido comentar los 'cout' de prueba, jajajaja.
dp[i] = Maximo tamaño de la subsecuencia (cumpliendo las especificaciones requeridas) donde i es el ultimo elemento de ésta subsecuencia.
sol_dp[i] = Elemento anterior a 'i' de la subsecuencia.
Clic aqui para ver el enunciado del problema.
9/01/2008
2017 - Hey, you are not Marion Jones!
Simplemente simulé todo lo que decía el enunciado. Había quedado pendiente de un mini-entrenamiento que hicimos Arcila y yo.
BadNeighbors (250) - 2004 TCCC Online Round 4
Bueno despues de mucho pensarle a este problema pude resolverlo.
dp[i] = Máxima donación posible hasta i (incluyendolo).
Nota: Que gallo poner a funcionar este dp con una subsecuencia circular, pero ahí vamos aprendiendo :D.
dp[i] = Máxima donación posible hasta i (incluyendolo).
Nota: Que gallo poner a funcionar este dp con una subsecuencia circular, pero ahí vamos aprendiendo :D.
10819 - Trouble of 13-Dots
DP, programación dinámica, dynamic programming.
Es parecido al problema de la mochila (Knapsack 0/1 problem).
El estado que utilice:
Es parecido al problema de la mochila (Knapsack 0/1 problem).
El estado que utilice:
dp[i][j] = Utilizando un subconjunto de los elementos [0..i],
el máximo valor que puedo comprar gastando exactamente j pesos.
dp[i][j] == INT_MIN si no puedo escoger un subconjunto de los
elementos [0..i] que valga exactamente j pesos.
8/31/2008
11152 - Colourful Flowers
El primer problema que voy a colocar es este de geometría, que Andrés me mostró esta mañana,utilice dos principios simples sr= Área triangulo, donde s: es el semi perímetro y r: el inradio, y la ley del extendida del seno (a /sen a =2R) donde R: es el circunradio.
Suscribirse a:
Entradas (Atom)