tag:blogger.com,1999:blog-71376697187692026472024-03-18T22:47:35.512-06:00Algoritmos y DemasAnonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.comBlogger41125tag:blogger.com,1999:blog-7137669718769202647.post-86774425665786095842013-11-11T12:08:00.002-06:002013-11-11T12:40:05.604-06:00Problema E : Eleven (Regional Latinoamerica 2013)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<small>Escrito por Rodrigo Burgos Domínguez </small>
<br> <br>
<strong>Problema E : Eleven</strong> <br> <br>
La redacción del problema es muy simple, aun que el problema no lo es, lo que dice el problema que dado un número N hay que encontrar todos los anagramas de N (que no tengan dígitos ceros a la izquierda) , tal que sean divisibles por 11, la solución de programación dinamica se ve obvia, pero la forma de hacerla no lo es, un comentario de Ulises Méndez sobre la propiedad del 11 me ayudo a ver una solución no tan complicada, si buscan en internet encontraran que para que un numero sea divisible por 11 basta con sumar los dígitos que están en posiciones pares y resta le todos los dígitos que están en posiciones impares, si el resultado es divisible por 11 entonces el numero de divisible por 11.
<br> <br>
Por ejemplo: 4785 , sumamos las posiciones impares 4 + 8 = 12 y luego sumamos las posición pares 7 + 5 = 12, restamos el segundo al primero 12 - 12 = 0 , y como 0 % 11 = 0, por tanto es divisible por 11.
<br> <br>
Ya que tenemos este concepto solo nos tenemos que preocupar que la diferencia entre los pares eh impares sea divisible entre 11. Existe otro detalle, ya que nos piden que los anagramas sean numero sin ceros a la izquierda, esto es sencillo ( aun que no trivial de ver) , nosotros forzamos al numero que vamos a generar a que su primer dígito sea diferente de cero, es por eso que van a ver en el codigo esta parte ( countDigit es una arreglo donde guardamos el numero de 0, 1, 2 , 3, .. 9 que hay en el numero que leemos al inicio) <br>
<pre class="brush:perl">
for( digit = 1; digit <= 9; digit++)
if( countDigits[ digit ] > 0 ){
countDigits[ digit ]--;
memset( vis, 0, sizeof( vis ));
res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
countDigits[ digit ]++;
}
</pre>
<br>
Como ven descartamos un dígito el 1 o el 2, o el 3, ... al 9, dependiendo cual tratamos de forzar a que sea el primer digito de nuestro posible anagrama. Posteriormente resolvemos nuestra dinamica mandando ( digitoInicial ( siempre se empieza en cero para recorrer de cero a nueve), Numero de elementos pares que nos faltan, numero de elementos impares ( como ven se resta el primero que ya utilizamos) , modulo que llevamos hasta el momento (como ven es <strong>11 - digito</strong>, ya que los impares se restan ). <br> <br>
La dinamica es de la siguiente forma:<br>
<pre class="brush:perl">
solve( int posDigit, int pares, int impares, int mod)
</pre>
<br>
Nosotros nos vamos a estar moviendo de dígito en dígito, primero en el cero, luego en el uno,... , hasta el nueve, para eso es <strong>posDigit</strong> también llevamos el número de elementos <strong>pares</strong> que nos hace falta colocar en nuestro anagrama factible, así como los <strong>impares</strong> , el <strong>mod</strong> solo contendrá la suma de las diferencia de los dígitos pares e impares.<br><br>
Lo siguiente para resolver el problema es darse cuenta que si tenemos 5 dígitos de un tipo, solo los podemos colocar de la siguiente manera, { (0 pares , 5 impares), ( 1 par, 4 impares), ( 2 pares, 3 impares), ( 3 pares, 2 impares), ( 4 pares, 1 impar) , ( 5 pares, 0 , impares) }, no son muchas en el peor de los casos vamos a tener 100 dígitos iguales, en esta parte hago uso de un for con la variable <strong>slice</strong> esta variable va a cortar y determinar cuantos impares y pares: <br>
<pre class="brush:perl">
for( slice = 0; slice <= countDigits[ posDigit ]; slice++){
</pre>
<br>
Dependiendo del numero de elementos del dígito vamos a partilos como se los había mencionado , el numero de pares seria igual a <strong>slice</strong> y numero de impares seria igual a <strong> countDigits[ posDigit ] - slice </strong> , agregando estos dígitos tenemos que calcular nuestro nuevo modulo, ya que al agregar digitos pares e impares se modifica:
<pre class="brush:perl">
newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11
</pre>
<br>
Se suma el modulo que tenemos y se agregan los dígitos pares e impares, pueden notar que se restan los impares, también van a ver varios módulos 11, esto es por que la resta puede quedar un numero negativo y debemos asegurarnos que sea siempre positivo.
<br>
Ya que tenemos nuestro nuevo modulo podemos contar cuantos resultados tenemos si escogemos esa cantidad de pares eh impares con el digito en cuestión, lo que hacemos es invocar el solve para que calcula el siguiente dígito <strong> posDigit + 1 </strong> , también hay que restar nuestros pares usados en este momento, así como los impares y lo invocamos con nuestro nuevo modulo.
<br>
R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
<br>
Todavía no se acaba, ya colocamos el numero de dígtos pares, pero en el numero pueden estar distribuidos en cualquier posición disponible para dígitos pares, es por eso que se hacen las combinaciones de numeroParesDisponibles en paresAAgregar, lo mismo para los impares y estos dos resultados se multiplican el numero de soluciones factibles que obtuvimos del proximo digito. <br>
<pre class="brush:perl">
R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;
</pre>
<br>
( si es complejo de enterder pero espero les sirva el post, si tienen dudas o quieren que aclare algo mas, no duden en solicitarlo a rodrigo.burgos@gmail.com).
<br>
Aquí les dejo el código completo para que lo analicen: <br>
<br>
<pre class="brush:perl">
/* Rodrigo Burgos Dominguez */
# include "stdio.h"
# include "string.h"
# define MOD ((long long)1000000007)
char num[200];
int length, countDigits[10];
long long dinComb[102][102];
long long din[11][102][102][12];
int vis[11][102][102][12];
long long comb(int a, int b){
if( a == 0 && b == 0 ) return 1;
if( b > a ) return 0;
if( b == 0 ) return 1;
if( b < 0 ) return 0;
if( dinComb[a][b] != -1 ) return dinComb[a][b];
return dinComb[a][b] = (comb(a - 1, b - 1) + comb(a - 1, b)) % MOD;
}
long long solve( int posDigit, int pares, int impares, int mod){
long long res = 0, R;
int newmod, slice;
if( pares < 0 || impares < 0 ) return 0;
if( posDigit == 10 ) {
return (pares == 0 && impares == 0 && mod == 0) ? 1 : 0 ;
}
if( vis[posDigit][pares][impares][mod] == 1) return din[posDigit][pares][impares][mod];
vis[posDigit][pares][impares][mod] = 1;
for( slice = 0; slice <= countDigits[ posDigit ]; slice++){
newmod = ((mod + ( slice * posDigit ) - ( (countDigits[ posDigit ] - slice ) * posDigit )) % 11 + 11 ) % 11;
R = solve( posDigit + 1, pares - slice, impares - ( countDigits[ posDigit ] - slice ) , newmod ) % MOD;
R = ( R * ( ( comb(pares, slice) * comb( impares, ( countDigits[ posDigit ] - slice ) )) % MOD) ) % MOD;
res = (res + R) % MOD;
}
return din[posDigit][pares][impares][mod] = res % MOD;
}
main(){
int pares, impares, digit, x;
long long res;
memset( dinComb, -1, sizeof( dinComb ) );
while( scanf("%s", num) != EOF ){
length = strlen( num );
memset( countDigits, 0, sizeof( countDigits ));
for( x = 0 ; x < length ; x++) countDigits[ num[x] - '0']++;
pares = ( length / 2 );
impares = ( length / 2) + ( length % 2);
res = 0;
for( digit = 1; digit <= 9; digit++)
if( countDigits[ digit ] > 0 ){
countDigits[ digit ]--;
memset( vis, 0, sizeof( vis ));
res = ( res + solve( 0 , pares, impares - 1, 11 - digit)) % MOD;
countDigits[ digit ]++;
}
printf("%lld\n", res);
}
return 0;
}
</pre>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com1tag:blogger.com,1999:blog-7137669718769202647.post-69277615931934238132013-11-09T19:12:00.000-06:002013-11-09T19:17:10.216-06:00Problema A : Attacking rooks (Regional Latinoamerica)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<small>Escrito por Rodrigo Burgos Domínguez </small>
<br> <br>
<strong>Problema A : Attacking rooks ( Regional Latino America 2013)</strong>
Un problema un poco complejo de regional 2013 de Mexico, practicamente trata de dado una cuadricula de N x N , y unas celdas bloqueadas, es colocar el maximo numero de torres ( torre de ajedrez se mueve en toda su columna y toda su fila si no encuentra obstáculo), de tal manera que ninguna torre se ataque entre si. <br> <br>
Lo primero que uno debe observar que una torre puede bloquear una columna completa y una fila completa, entonces por cada posición del tablero si uno coloca una torre en esa posición bloquea la columna y fila de dicha posición, estas filas y columnas que nos referimos no es la fila completa del tablero si no una subparte de dicha fila ya que puede estar delimitada por puntos bloquedos ( o peones en el problema).
<br> <br>
Para formar todos las sub filas y utilizo estos fors: <br> <br>
<pre class="brush:perl">
newFil = 0;
for( r = 1; r <= n; r++){
for( c = 1; c <= n; c++){
if( map[r][c] != 'X'){
if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
fils[r][c] = fils[r][c - 1];
}
}
}
</pre>
<br> <br>
como se puede analizar lo que hace es marcar como una nueva fila, las subpartes cada que encuentra una posición bloqueada incrementa en esa posición un nueva fila y para todas las demás le asigna el numero de la fila de la posición bloqueada. ( en el caso de ser inicio de fila tambien se asigna una nueva fila).
<br> <br>
Ya con eso podemos hacer una relación de subFiles y subColumnas, y lo que hay que maximizar es el numero de conexiones que hay entre las filas y columnas, en pocas palabras utilizar maximo matching.
<br> <br>
Les comporta la solucion general del problema:
<br> <br>
<pre class="brush:perl">
/* Rodrigo Burgos */
# include <stdio.h>
# include <string.h>
# define MAX 100
char map[MAX + 3][MAX + 3];
int cols[MAX + 3][MAX + 3];
int fils[MAX + 3][MAX + 3];
int mark[MAX * MAX + 2], vis[ MAX * MAX + 2];
char graph[MAX*MAX/2+1][MAX*MAX/2+1];
int newFil, newCol;
int match(int nodo ){
int x;
if( vis[nodo] == 1 ) return 0;
vis[nodo] = 1;
for( x = 1; x <= newCol; x++)
if( graph[nodo][x] == 1 && ( mark[ x ] == -1 || match( mark[ x ])) ){
mark[x] = nodo;
return 1;
}
return 0;
}
main(){
int r, c, cont, x, n;
while( scanf("%d", &n) != EOF ) {
memset( cols, 0, sizeof( cols ) );
memset( fils, 0, sizeof( fils ) );
for( x = 1; x <= n; x++) scanf("%s", map[x] + 1);
newFil = newCol = 0;
for( r = 1; r <= n; r++){
for( c = 1; c <= n; c++){
if( map[r][c] != 'X'){
if( cols[r - 1][c] == 0 ) cols[r - 1][c] = ++newCol;
cols[r][c] = cols[r - 1][c];
}
}
}
for( r = 1; r <= n; r++){
for( c = 1; c <= n; c++){
if( map[r][c] != 'X'){
if( fils[r][c - 1] == 0 ) fils[r][c - 1] = ++newFil;
fils[r][c] = fils[r][c - 1];
}
}
}
memset( graph, 0, sizeof( graph ) );
for( r = 1; r <= n; r++){
for( c = 1; c <= n; c++)
if( map[r][c] != 'X'){
graph[fils[r][c]][cols[r][c]] = 1;
}
}
memset( mark, -1, sizeof( mark ) );
cont = 0;
for( x = 1; x <= newFil; x++){
memset( vis, 0, sizeof( vis ) );
if( match( x ) ) cont++;
}
printf("%d\n", cont);
}
return 0;
}
</pre>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-31186892718429326402013-11-09T13:09:00.003-06:002013-11-09T13:18:26.537-06:00Resultado online Regional 2013 America Latina, Mexico, Venezuela, Cuba .<br />
<br />
Les dejo la liga donde pueden ver el scoreboard:<br />
<br />
<a href="http://score.bombonera.org/" target="_blank">http://score.bombonera.org/</a><br /><br />problemas:<br /><br /><a href="http://uva.onlinejudge.org/contests/323-684d225e/12668.pdf" target="_blank">Problema A</a><br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12669.pdf" target="_blank">Problema B</a><br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12670.pdf" target="_blank">problema C</a><br /><br /><a href="http://uva.onlinejudge.org/contests/323-684d225e/12671.pdf" target="_blank">Problema D</a><br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12672.pdf" target="_blank">Problema E</a><br />
<br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12673.pdf" target="_blank">Problema F</a><br />
<br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12674.pdf" target="_blank">Problema G</a><br />
<br />
<br />
<a href="http://uva.onlinejudge.org/contests/323-684d225e/12675.pdf" target="_blank">Problema H</a><br /><br /><br /><a href="http://uva.onlinejudge.org/contests/323-684d225e/12676.pdf" target="_blank">Problema I</a><br /><br /><a href="http://uva.onlinejudge.org/contests/323-684d225e/12677.pdf" target="_blank">Problema J</a><br />
<br />Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-80683339173211525482013-11-05T21:17:00.000-06:002013-11-05T21:19:38.371-06:002533 - Connecting Cities (Kruskal)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<small>Escrito por Rodrigo Burgos Domínguez </small>
<br> <br>
<strong>
<a href="http://coj.uci.cu/24h/problem.xhtml?abb=2533" title="2533 - Connecting Cities (Kruskal)" target="_blank">2533 - Connecting Cities (Kruskal)</a>
</strong>
<br>
<br>
Este problema se presento en un concurso de preparación para el regional 2013, el problema nos decía que hay costos de conectar una ciudad a otra, y te dan todas las posible aristas y sus costos que puedes utilizar, tu tarea es encontrar el mínimo costo de conectar todas las ciudades, esto parecería directamente un <a href="http://algorithmmx.blogspot.mx/2013/11/algoritmo-de-kruskal.html" title="Kruskal" target="_blank">Kruskal</a>, pero ademas de eso puede colocar aeropuertos y el costo de colocar un aeropuerto en cualquiera de la ciudades es C.
<br>
<br>
Para el caso simple nosotros podemos utilizar kruskal, suponiendo que no colocamos ningún aeropuerto, pero que pasa cuando es necesario colocar lo, lo que debemos observar que colocar una unión de una ciudad a otra por medio de un aeropuerto nos cuesta 2C, ya que no existen entre ellas un aeropuerto , pero cuando colocamos la unión de otra, por ejemplo tenemos un aeropuerto del en el nodo A y B, y ahora queremos conecta Q con P, realmente no importa la conexión de Q con P, haciendo un aeropuerto en P, podemos conectar tanto A y B con P , con el único costo C, con esta hipótesis, lo que hacemos es agregar todas las aristas de todos los nodos contra todos los nodos con costo C, y aplicar kruskal, el resultado le sumamos el costo de la primera arista que generó dos aeropuertos C.
<br>
<br>
de ahi tenemos el siguiente codigo:
<br>
<br>
<pre class="brush:perl">
/*
Rodrigo Burgos Dominguez
*/
# include "stdio.h"
# include "string.h"
# define MAX_ARISTAS 5000000
# define MAX_NODES 2000
typedef struct { int a, b, cost; } ARISTA;
ARISTA A[MAX_ARISTAS + 1];
int set[MAX_NODES + 1];
int min( int a, int b){ return a < b ? a: b; }
int getSet( int nodo ){
return set[ nodo ] == nodo ? nodo : (set[nodo] = getSet( set[nodo] ) );
}
int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }
int kruskal(int N, int M){
int x, sol = 0, a, b, contAristaAgregadas = 0;
for( x = 0 ; x <= N; x++) set[x] = x;
qsort( A, M, sizeof( ARISTA ), compare );
for( x = 0; x < M; x++){
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
contAristaAgregadas ++;
set[a] = b;
sol += A[x].cost;
}
}
return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
}
main(){
int sol, ncases, cases, x, y;
int N, M, C;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
scanf("%d %d %d", &N, &M, &C);
for( x = 0; x < M; x++){
scanf("%d %d %d", &A[x].a, &A[x].b, &A[x].cost);
}
sol = kruskal(N, M);
for( x = 1; x <= N; x++)
for( y = x + 1; y <= N ; y++) {
A[ M ].a = x;
A[ M ].b = y;
A[ M ].cost = C;
M++;
}
sol = min( sol, kruskal(N, M) + C);
printf("%d\n", sol);
}
</pre>
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-15790927406059072092013-11-05T20:22:00.000-06:002014-02-25T16:28:40.939-06:00Algoritmo de Kruskal
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<small>Escrito por Rodrigo Burgos Domínguez </small>
<br> <br>
<strong>Algoritmo de Kruskal</strong>
Kruskal es una algoritmo muy utilizado en los concursos para la resolución de problemas que tiene que ver con el árbol de expansión mínima( MST) , la técnica de Kruskal, es ordenar todas las aristas ( dependiendo si uno quiere la expansión mínima o máxima) , al ordenar las aristas con el menor costo se va agregando la arista menor formando un árbol, en el momento que al agregar una arista se agregue un ciclo esta arista no es considerada parte de la solucion.
<br><br>
Vamos a elaborar el código paso por paso:
<br><br>
Creamos una estructura de datos llamada Arista:
<br><br>
<pre class="brush:perl">
typedef struct { int a, b, cost; } Arista;
</pre>
<br><br>
en esta estructura de datos vamos a guardar la información de cada arista, el nodo origen 'a', el nodo destino 'b' y obviamente el costo de la arista 'cost', posteriormente declaramos el arreglo donde vamos a guardar todas nuestras aristas:
<br><br>
<pre class="brush:perl">
# define MAX_ARISTA 100000 // dependiendo el numero de aristas:
Arista[MAX_ARISTA +1] A;
</pre>
<br><br>
Bueno eso es solo una parte del problema el como guardar la información ahora veamos el algoritmo:
<br><br>
Supongamos que N es el numero de nodos y M el numero de aristas, tenemos el siguiente seudocódigo ( como aparece en Wikipedia http://en.wikipedia.org/wiki/Kruskal's_algorithm
):
<br><br>
<pre class="brush:perl">
KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3 MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5 if FIND-SET(u) ≠ FIND-SET(v):
6 A = A ∪ {(u, v)}
7 UNION(u, v)
8 return A
</pre>
<br><br>
Vamos a seguir este algoritmo, la única diferencia que nosotros nada mas vamos a regresar el costo
<br><br>
<pre class="brush:perl">
int kruskal(int N, int M){
int x, sol = 0, a, b, contAristaAgregadas = 0;
for( x = 0 ; x <= N; x++) set[x] = x;
qsort( A, M, sizeof( ARISTA ), compare );
for( x = 0; x < M; x++){
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
contAristaAgregadas++;
set[a] = b;
sol += A[x].cost;
}
}
return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
}
</pre>
<br><br>
como puedes observar, creamos nuestro conjunto o mejor dicho lo inicializamos:
<br><br>
<pre class="brush:perl">
for( x = 0; x <= N; x++) set[x] = x;
</pre>
<br><br>
este arreglo lo que quiere decir es que el conjunto 0 pertenece al conjunto 0, el conjunto 1 al conjunto 1, en pocas palabras cada conjunto contiene solo un elemento, el mismo, al inicio todos los nodos perteneces a su correspondiente conjunto, nodo 0 al conjunto 0 , nodo 1 al conjunto 1, etc.
<br><br>
posteriormente se ordenan las aristas:
<br><br>
<pre class="brush:perl">
qsort( A, M, sizeof( ARISTA ), compare );
</pre>
<br><br>
Esta función es parte de ANSI C , y lo único que se tiene que agregar es la función comparar que seria de la siguiente manera:
<br><br>
<pre class="brush:perl">
int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }
</pre>
<br><br>
Esta función compara *a y *b, si *a es menor a *b debe regresar un numero negativo, si es mayor un positivo y si es igual debe regresar 0.
<br><br>
Para el caso de c++, también se puede ordenar con la función sort
<pre class="brush:perl">
# include "algorithm"
bool compare(ARISTA a, ARISTA b){ return a.cost < b.cost; }
// ordenacion
sort( A, A + M , compare);
</pre>
El siguiente paso es iterar todas las aristas, como ya están ordenadas van de menor a mayor:
<br><br>
<pre class="brush:perl">
for( x = 0; x < M; x++){
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
contAristaAgregadas++;
set[a] = b;
sol += A[x].cost;
}
}
</pre>
<br><br>
aquí hay algo curioso y esta parte amerita una explicación mas profunda ya que es lo que hace posible el la unión de conjunto el getSet , ¿que es esta función?
<br><br>
Esta función lo que hace es lo siguiente:
<br><br>
<pre class="brush:perl">
int getSet( int conjunto) {
if( set[conjunto] == conjunto) return nodo;
set[conjunto] = getSet( set[conjunto]);
return set[conjunto];
}
</pre>
<br><br>
Lo que valida es si el conjunto que esta preguntando pertenece al mismo conjunto del que empezó,esto quiere decir que nadie a movido a ese conjunto, en otro caso si lo han movido y ahora el conjunto pertenece a otro conjunto, en ese momento podemos regresar que pertenece al conjunto guardado pero puede ser que el conjunto al que apunta ahora pertenezca a otro conjunto, entonces recursivamente se mueve al siguiente conjunto getSet( set[conjunto]), y así aseguramos que regresemos realmente el conjunto que pertenece el nodo en cuestión.
<br><br>
Como se observa al regresar el siguiente conjunto actualizamos el valor
<pre class="brush:perl">
set[conjunto] = getSet( set[conjunto]);
</pre>
<br><br>
Esto es para que la búsqueda sea optima, si por ejemplo el conjunto 1 apunta al 2, el 2 al 3, el 3, al 4, … y el 9999 al 10000 , se procesaría cada consulta del nodo 1 diez mil veces, pero al agregar esta actualización la siguiente vez que se pregunte sobre el nodo 1, solo se consultaría el conjunto 1 y el 10000 y validaría si el 10000 no ha sido modificado.
<br><br>
Esta parte es crucial en el algoritmo y deben entender bien la función getSet.
<br><br>
siguiendo con el algoritmo de Kruskal:
<br><br>
<pre class="brush:perl">
// RECORDANDO
for( x = 0; x < M; x++){
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
contAristaAgregadas++;
set[a] = b;
sol += A[x].cost;
}
}
</pre>
<br><br>
lo que sigue es validar que el conjunto de la arista de ‘a’ sea diferente de la arista de ‘b’ , por tanto se realiza por medio de esto:
<pre class="brush:perl">
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
}
</pre>
<br><br>
si a ¡= b entonces no perteneces al mismo conjunto y se agrega la arista como parte de la solución:
<br><br>
<pre class="brush:perl">
contAristaAgregadas++;
set[a] = b;
sol += A[x].cost;
</pre>
<br><br>
en conAristasAgregadas, el nombre lo dice todo , contamos el numero de aristas agregadas, hacemos el conjunto ‘a’ que pertenesca al conjunto de 'b':
<br><br>
<pre class="brush:perl">
set[a] = b; // si, así de fácil.
</pre>
<br><br>
y sumamos la arista:
<br><br>
<pre class="brush:perl">
sol += A[x].cost;
</pre>
<br><br>
al final del algoritmo debemos garantizar que sea conexo, y para eso validamos el numeró de aristas agregadas sean igual al N – 1 :
<br><br>
<pre class="brush:perl">
return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
</pre>
<br><br>
si es igual a N – 1, regresamos la solución que llevamos, en otro caso regresamos infinito en este caso 2 a la 28 ( este valor puede no ser suficiente si el costo de las aristas es muy grade, hay que tener cuidado en esto).
<br><br>
al final nuestro algoritmo queda de la siguiente manera:
<br><br>
<pre class="brush:perl">
# include "stdio.h"
# include "string.h>
# define MAX_ARISTAS 5000000
# define MAX_NODES 2000
int set[MAX_NODES + 1];
int getSet( int conjunto ){
return set[ conjunto ] == conjunto ? conjunto : (set[conjunto] = getSet( set[conjunto] ) );
}
typedef struct { int a, b, cost; } ARISTA;
ARISTA A[MAX_ARISTAS + 1];
int compare(ARISTA *a, ARISTA *b){ return a->cost - b->cost; }
int kruskal(int N, int M){
int x, sol = 0, a, b, contAristaAgregadas = 0;
for( x = 0 ; x <= N; x++) set[x] = x;
qsort( A, M, sizeof( ARISTA ), compare );
for( x = 0; x < M; x++){
a = getSet( A[x].a);
b = getSet( A[x].b);
if( a != b){
contAristaAgregadas ++;
set[a] = b;
sol += A[x].cost;
}
}
return ( contAristaAgregadas == N - 1 ) ? sol : (1<<28);
}
</pre>
<br>
<br>
Un ejemplo de kruskal es este
<a href="http://algorithmmx.blogspot.mx/2013/11/2533-connecting-cities-kruskal.html" title="2533 - Connecting Cities" target="_blank">2533 - Connecting Cities</a>
<br>
<br>
<br>
<br>
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-27096676583407228542013-10-31T11:40:00.000-06:002013-10-31T11:40:01.091-06:002457 - Piece Creation (Programación Dinamica COJ)
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<strong><a href="http://coj.uci.cu/24h/problem.xhtml?abb=2457" title="2457 - Piece Creation" target="_blank">2457 - Piece Creation</a></strong>
<br><br>
Este problema nos dice que teniendo puntos en un tablero, nosotros podemos trazar líneas horizontales y verticales que conecten el punto con el extremo del tablero, con la restricción de que no toque otro punto o otra línea que conecte otro punto con la orilla del tablero ( Esto es un circuito electrónico que conecta un punto del circuito con la orilla ya que en la orilla esta la corriente). La tarea es encontrar el costo mínimo de hacer esto, ya que cada cm de línea que utilicemos tiene un costo.
<br><br>
Lo primero que se me ocurrió fue hacer un flujo máximo a costo mínimo, cada punto del tablero serian dos nodos un nodo incidente y otro adyacente, donde cada nodo incidente y adyacente que represente un nodo tendría una arista de costo 1 o de capacidad 1 , esto para evitar que pasara por el mas de un cable , si existiera un punto en esta coordenada simplemente esta arista no existiría, y de hecho resolvía el problema general, de conectar con el mínimo cable todos los puntos, pero el problema tiene una restricción, que solo pueden ser líneas rectas, esta solución encuentra un cableado donde se puede modificar la dirección del cable.
<br>
<br>
Después de pensar un rato mas encontré algo interesante, que es el tamaño del chip ( o del tablero) es menor a 30, y solo hay 50 puntos , si nosotros ordenamos de menor a mayor , por coordenadas Y y posteriormente por X, tenemos que cuando coloquemos un punto P[pos] después de P[pos - 1 ], este punto o esta arriba ( P[pos-1].y < P[pos - 1].Y ) o esta a la derecha ( P[pos-1].x < P[pos].x) , con esto podemos saber dos cosas, primero si puedo conectar el punto P[pos] a la derecha , ya que si P[pos-1].y == P[pos].y no es posible, y llevando el control del rango [A,B], donde A es el punto donde inicia el tablero visible de arriba y B es la posición del tablero donde termina el espacio visible, a que me refiero con campo visible, por ejemplo el campo visible al inicio es de 0 a 31, si un punto esta en la coordenada X = 5 y se conecta con otro a la izquierda tapa todos los nodos del 0 al 5 entonces el campo visible de tablero superior es de 6 al 31, si existiera otro que fuera a la derecha a partir de X = 9 , se tendría un campo visible de 6 al 8, entonces si nosotros llevamos esto en nuestra dinámica o mejor dicho en nuestra memorización , podríamos saber si puedo conectarme arriba y a la izquierda y como siempre se puede conectar a la derecha , casi se tiene resuelto el problema, para resolver el problema de si puede ir hacia abajo , simplemente llevamos otro rango [a,b], este rango es el rango permitido de colocar un punto, si nosotros colocamos un punto que va hacia abajo partiría en dos el tablero, y si un punto se quiere conectar al a izquierda solo podría hacerlo si el b = 31 , o si quiere ir a la derecha tendría que a ser igual a cero ( a=0) , si garantizamos que al partir el tablero ( conectarlo hacia abajo no hay un punto en ese trayecto) entonces solo restaría agregar los puntos siguiente dependiendo si están de lado de una partición o si están del otro lado.
Aquí les dejo el código:
<br>
<pre class="brush:perl">
/*Autor: Rodrigo Burgos Dominguez*/
# include "stdio.h"
#include "string.h"
typedef struct { int x, y; } POINT;
POINT p[100];
int AA, n;
int compare( POINT *a, POINT *b){
if( a->y != b->y)
return a->y - b->y;
return a->x - b->x;
}
int min( int a, int b){ return a < b ? a: b;}
int max( int a, int b){ return a > b ? a: b;}
int din[51][32][32][32][32];
int mapMax[100];
int mapMin[100];
int ladosMax[100];
int ladosMin[100];
int solve( int position, int A, int B, int a, int b){
int res = (1<<22), path = -1, tres, cst = 0;
if( position >= n ) return 0;
if( din[position][A][B][a][b] != -1) return din[position][A][B][a][b];
if( p[position].x <= a || p[position].x >= b )
return din[position][A][B][a][b] = solve( position + 1, A, B, a, b);
/* ARRIBA */
if( p[position].y <= mapMin[ p[ position ].x ] && p[ position ].x < B && p[ position ].x > A){
tres = solve( position + 1 , A, B, a, b ) + p[ position ].y ;
if( tres < res ){
res = tres;
path = 0;
cst = p[ position ].y;
}
}
/* IZQUIERDA */
if( p[position].x <= ladosMin[ p[ position ].y ] && a == 0 ){
tres = solve( position + 1 , max( A, p[ position].x), B, a, b ) + p[ position ].x ;
if( tres < res){
res = tres;
path = 1;
cst = p[ position ].x;
}
}
/* DERECHO */
if( p[position].x >= ladosMax[ p[ position ].y ] && b == 31 ){
tres = solve( position + 1 , A, min( B, p[position].x ), a, b ) + ( AA - p[ position ].x);
if(tres < res){
res = tres;
path = 2;
cst = ( AA - p[ position ].x);
}
}
/* ABAJO */
if( p[position].y >= mapMax[ p[ position ].x ]){
tres = solve( position + 1 , A, B, a, p[ position].x ) + solve( position + 1, A, B, p[ position ].x , b)+ ( AA - p[ position ].y );
if( tres < res){
res = tres;
path = 3;
cst = ( AA - p[ position ].y );
}
}
/* printf("(%d %d) %d %d %d %d %d -> %d -> path %d cost %d\n", p[position].x, p[ position].y, position, A, B, a, b, res, path, cst);*/
return din[position][A][B][a][b] = res;
}
main(){
int x, res;
while( scanf("%d %d", &AA, &n) != EOF ){
memset( din, -1, sizeof( din ));
for( x = 0; x <= AA; x++){
mapMax[ x ] = -(1<<22);
mapMin[ x ] = (1<<22);
ladosMax[x] = -(1<<22);
ladosMin[x] = (1<<22);
}
for( x = 0; x < n; x++){
scanf("%d %d", &p[x].x, &p[x].y);
mapMax[ p[x].x ] = max(mapMax[ p[x].x ], p[x].y);
mapMin[ p[x].x ] = min(mapMin[ p[x].x ], p[x].y);
ladosMax[ p[x].y ] = max(ladosMax[ p[x].y ] , p[x].x);
ladosMin[ p[x].y ] = min(ladosMin[ p[x].y ] , p[x].x);
}
qsort( p, n, sizeof( POINT ), compare );
res = solve( 0, 0, 31, 0, 31);
if(res >= (1<<22))
printf("No solution\n");
else
printf("The total length of wire used is %d\n", res);
}
return 0;
}
</pre>
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-41608687012558458752012-08-14T11:36:00.001-05:002012-08-15T10:27:48.052-05:00UVA 10407 Simple division<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>UVA 10407 Simple division </h3>
<br />
http://uva.onlinejudge.org/external/104/10407.html
<br />
Buenos dias a todos, les comparto este problema, practicamente se trata de encontrar un numero que al dividir a toda una lista de numeros regresen todos el mismo residuo, en el algoritmo que expongo abajo se puede ver que la solucion la pongo como un "Fuerza Bruta pero no tanto" ya que mi idea no se basa tanto en las propiedades de la division del numero y como no soy un matematico puro no se me ocurre directamente como sacar una solucion con estas propiedades.
<br />
Esta solucion radica en el hecho si tomo dos numeros distintos la cantidad de numeros que al dividirlo me resulte el mismo residuo no son muchos, por tal motivo lo primero que hago es quitar todos los numero repetidos:
<br />
<pre class="brush:perl">
// ESTO VA FUERA DEL MAIN
int compare( int *a, int *b){ return *a - *b; }
// FIN DE LO QUE VA FUERA DEL MAIN
qsort( list, n, sizeof( int ), compare );
nsize = 1;
for( x = 1; x < n; x++){
if( list[ x ] != list[ x - 1]){
list[ nsize++ ] = list[x];
}
}
</pre>
<br />
Primero ordeno, y luego si son distintos los guardo en la ultima posicion libre que tengo, primero n es el tamaño de mi lista y al final nsize sera mi nuevo tamaño de la lista.
<br />
Dejo reposar el algoritmo por unos segundos, y despues calculo todos los numeros que dividen a los numeros mas pequeños, ya que trato de procesar la menor cantidad de operaciones:
<br />
<pre class="brush:perl">
// ESTO VA FUERA DEL MAIN
int compare2( int *a, int *b){ return abs(*a) - abs(*b); }
// FIN DE LO QUE VA FUERA DEL MAIN
qsort( list, nsize, sizeof( int ), compare2 );
npa = 0;
for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
</pre>
Orderno la nueva lista sin elementos repetidos, pero en vez de ordenarlo de menor a mayor, los ordeno de menor a mayor, pero aplicando la funcion de valor absoluto a los numeros. Despues procedo a fuerza bruta ver todos los numero que su residuo sea igual del primer y el segundo elemento de la lista,
<br /><br/> <b> Por que hago (( A % div) + div) % div ? </b> <br /> <br />
Cuando era niño me preguntaba si los numero negativos al dividirlos sus residuos eran positivos, bueno asi es, pero cuando lo haces en C/C++ eso no es cierto, el residuo es negativo y lo tienes que volver positivo, por eso primero saco el residuo de A / div , despues le sumo div, esto asegura que se vuelva positivo, y por ultimo le vuelvo a sacar el residuo, ya que si era positivo el residuo al sumarle div se saldria del rango de [0, div - 1].
<br /> Ya despues de que cuajo la solucion, lo que resta es hacer un barrido con todos los numeros pero en vez de checar todos los divisores posibles, solo revisamos las pisibles soluciones ( en este caso las guarde en <b>posibleAnswer</b> ), y al momento de varificar si el nuevo numero tambien tiene como resuduo una posible solucion, se van eliminando los que no cumplen.
<br />
<pre class="brush:perl">
for( x = 2; x < nsize; x++){
nextsize = 0;
for( div = 0; div < npa; div++){
if( ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ]
== ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
}
}
npa = nextsize;
}
</pre>
<br /> Al final solo hay que imprimir el ultimo valor de nuestras posibles soluciones <b>posibleAnswer[ npa - 1] </b>
<br />
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problema: UVA 10407 Simple division
Solucion: Fuerza Bruta pero no tanto.
*/
# include "stdio.h"
# include "string.h"
int max( int a, int b ){ return a > b ? a : b; }
int abs( int a ){ return a < 0 ? -a : a; }
int compare( int *a, int *b){ return *a - *b; }
int compare2( int *a, int *b){ return abs(*a) - abs(*b); }
int list[ 1002 ], n;
int posibleAnswer[1000*1000], npa;
main(){
int a, b, x, y, nsize, nextsize, div;
while(1){
for( n = 0; scanf("%d", &list[ n ]) != EOF && list[ n ] != 0 ; n++);
if( n == 0 ) break;
qsort( list, n, sizeof( int ), compare );
nsize = 1;
for( x = 1; x < n; x++){
if( list[ x ] != list[ x - 1]){
list[ nsize++ ] = list[x];
}
}
qsort( list, nsize, sizeof( int ), compare2 );
npa = 0;
for( div = 1; div <= max( abs(list[0]) , abs(list[ 1 ]) ); div++)
if( ((list[ 0 ] % div) + div ) % div == ((list[ 1 ] % div) + div ) % div) posibleAnswer[ npa++ ] = div;
for( x = 2; x < nsize; x++){
nextsize = 0;
for( div = 0; div < npa; div++){
if( ((list[ 0 ] % posibleAnswer[ div ])+ posibleAnswer[ div ] ) % posibleAnswer[ div ]
== ( ( list[ x] % posibleAnswer[div]) + posibleAnswer[ div ] ) % posibleAnswer[ div ] ){
posibleAnswer[ nextsize++ ] = posibleAnswer[ div];
}
}
npa = nextsize;
}
printf("%d\n", posibleAnswer[ npa - 1]);
}
return 0;
}
</pre>
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
<br />
Manuel me copartio su solucion ya reducida matematicamente, vean como el algoritmo que el muestra es corto y elegante basandose en las propiedad de los numeros:
http://thnkndblv.blogspot.mx/2012/08/10407-simple-division.html
</body>
Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com2tag:blogger.com,1999:blog-7137669718769202647.post-9238158554825743392012-08-13T10:57:00.003-05:002012-08-13T10:57:50.368-05:00UVA 12444 Bits and Piecest (Greedy)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>UVA 12444 Bits and Piecest </h3>
<br />
http://uva.onlinejudge.org/external/124/12444.html
<br />
Este problema a simple vista parece difícil, pero al analizar un poco como se comporta los operadores binarios de AND y OR, nos damos cuenta que siempre debe
tener los dos números, tanto A como B, los mismo bits de C, si existiera un bit en C que no estuviera prendido en D entonces hay un error, para encontrar el número cuya diferencia de |B - A| sea mínima, solo hace falta notar que todos los bits que no están C pero si están en D, el bit con valor mas alto se asigna a el valor de B y todos los demás bits se suman a A.
<br />
<br />
<pre class="brush:perl">
/*
Problem: UVA 12444 Bits and Pieces
Autor: Rodrigo Burgos Dominguez
Problem: Let A and B be non-negative integers and let C = A&B and D = A|B. Given C and D,
can you find A and B such that the absolute difference (|A-B|) is minimal?
Solution: greedy
*/
# include "stdio.h"
# include "string.h"
int transform[2][32];
long long max( long long a, long long b){ return a > b ? a : b; }
long long min( long long a, long long b){ return a < b ? a : b; }
void trans(int indice, long long number){
int pos;
memset( transform[ indice ], 0, sizeof( transform[ indice ]));
for( pos = 0; number > 0 ; pos++){
transform[indice][pos] = (number % 2);
number /= 2;
}
}
main(){
int cases, ncases, notSolution, x;
long long C, D, A, B, pot, last;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
scanf("%lld %lld", &C, &D);
trans( 0, C );
trans( 1, D );
notSolution = A = B = last = 0;
for( x = 0, pot = 1; x < 32; x++, pot *= 2){
if( transform[ 0 ][ x ] > 0 && transform[1][x] == 0 ) notSolution = 1;
if( transform[ 0 ][ x ] > 0 ){
A += pot;
B += pot;
}else if( transform[ 1 ][ x ] > 0 ){
A += last;
last = pot;
}
}
B += last;
if( notSolution == 1 ) printf("-1\n");
else printf("%lld %lld\n", min(A,B), max(A,B));
}
return 0;
}
</pre>
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
</body>
Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-22022891124460642442012-07-25T13:21:00.001-05:002012-07-25T13:21:53.376-05:00Uva Online Judge 11691 - Allergy Test<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>Uva Online Judge 11691 - Allergy Test </h3>
<br />
http://uva.onlinejudge.org/external/116/11691.html
<br />
<br />
Al leer este problema, inmediatamente me di cuenta que se podía resolver con programación dinámica utilizando una mascara de bits, esta mascara de bits representaría las pruebas que ya eh utilizado, adicional a eso necesitaría llevar en mi programación dinámica, el espacio en días que la prueba anterior ocupa de tal manera que yo puedo hacer una prueba en cualquiera de esos días sin que impida saber si hay una reacción en la prueba anterior.
</br>
</br>
Al implementarlo fue un rotundo <b>tiempo de ejecución excedido</b>, paso bastante tiempo en que volviera a tratar de resolver el problema, después de meditar un rato, no era necesario saber si una prueba ya fue utilizada, si no podría diferenciarla por tamaño de días que dura su reacción y no individualmente, esto me dejaría que el numero de estados posibles no eran de 2^20 si no de las combinaciones de 20 en 7 que es muchísimo menor, para implementar la solución utilicé un map de c++ para llevar la información.
<br />
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problem: 11691 - Allergy Test
Algoritm: Programacion Dinamica
*/
# include "stdio.h"
# include "string.h"
# include "algorithm"
# include "map"
using namespace std;
typedef struct { int values[8]; } DATA;
bool operator < ( DATA A, DATA B ){
int x;
for( x = 0; x < 8; x++) if( A.values[x] != B.values[x]) return A.values[x] < B.values[x];
return 0;
}
map< DATA, int > din[8];
map< DATA, int > vis[8];
int solve( int sizePrevius, DATA currentState){
int res = (1<<30), x, cnt = 0, y;
DATA next;
if( vis[ sizePrevius][currentState] == 1)
return din[sizePrevius][currentState];
vis[ sizePrevius][currentState] = 1;
for( x = 0; x < 8; x++) if( currentState.values[x] > 0 ){
cnt++;
for( y = 0; y <= sizePrevius; y++) if( x - y > 0){
next = currentState;
next.values[x]--,
res = min( res, solve( (x - y) - 1 , next) + sizePrevius + 1);
}
}
if(cnt == 0 ) res = sizePrevius;
return din[sizePrevius][currentState] = res;
}
main(){
int ncases, cases, x, n, val;
DATA empty;
memset( empty.values, 0, sizeof( empty.values ));
for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++){
for( x = 0; x < 7; x++){
map< DATA, int > visEmpty;
vis[x] = visEmpty;
}
scanf("%d", &n);
DATA ini = empty;
for( x = 0; x < n; x++){
scanf("%d", &val);
ini.values[ val ]++;
}
printf("%d\n", solve( 0 , ini ));
}
return 0;
}
</pre>
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-10769535312103314932012-07-19T13:04:00.000-05:002012-07-19T13:04:09.575-05:00UVA Online Judge 12125 - March of the Penguin<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>UVA Online Judge 12125 - March of the Penguins </h3>
<br />
http://uva.onlinejudge.org/external/121/12125.html
<br />
Es un problema clasico de Flujos, en este problema para cada pedazo de hielo es representado por dos nodos, el primero nodo seria el nodo en el que pueden llegar los pinguinos, todas las aristas que llegan a estos nodos, son de capacidad infinita, el segundo nodo son todas las pinguinos que pueden salir, aqui la capacidad tambien es infinita, el truco para evitar que mas de los pinguinos especificados puedan salir del pedazo de hielo es crear una arista entre estos dos nodos que lo representan, con capacidad igual a la que se proporciona en la entrada, al final solo hay que gener un nodo inicial y crear aristas con la capacidad que se especifica en la entrada (esta capacidad es la cantidad de pinguinos que se encuentran en cada pedazo de hielo al inicio ), se ejecuta el algoritmo de flujo maximo poniendo como nodo final cada uno de los nodos incidentes ( Nodos que solo reciben las aristas), y de esta manera si el flujo maximo es igual al total de pinguinos entonces ese nodo es un posible nodo final de reunion de todos los pinguinos.
<br />
Para este problema especifico en vez de utilizar una busqueda en amplitud para el flujo utilzo una busqueda en profundidad.
<br />
Les dejo el código:
<br />
<br />
<pre class="brush:perl">
# include "stdio.h"
# include "string.h"
typedef struct { double x, y; int numPenguins, mtime; } PENGUINS;
PENGUINS peng[102];
int graph[204][204], fnet[204][204], vis[204];
double distPenguins( PENGUINS A, PENGUINS B ){
return (A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y);
}
int min( int a, int b ){ return a < b ? a : b; }
int busquedaEnProfundidad(int currentNode, int destiny, int n, int flow ){
int r, x;
if( currentNode == destiny ) return flow;
if( vis[currentNode] == 1 ) return 0;
vis[currentNode] = 1;
for( x = 0; x < n; x++)
if( graph[currentNode][x] - fnet[currentNode][x] > 0 ){
r = busquedaEnProfundidad( x, destiny, n, min(flow, graph[currentNode][x] - fnet[currentNode][x]) );
if( r > 0 ){
fnet[currentNode][x] += r;
fnet[x][currentNode] -= r;
return r;
}
}
return 0;
}
int fordFulkerson(int inicio, int destino, int n) {
memset( fnet, 0, sizeof( fnet ));
int currentFlow, flow = 0;
do{
memset( vis, 0, sizeof( vis ));
currentFlow = busquedaEnProfundidad( inicio, destino, n, (1<<22));
flow += currentFlow;
}while( currentFlow > 0 );
return flow;
}
main(){
int cases, ncases, x, y, ini, sumAllPenguins, n, r, cont;
double dist;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
scanf("%d %lf", &n, &dist);
sumAllPenguins = 0;
for( x = 0; x < n; x++){
scanf("%lf %lf %d %d", &peng[ x ].x, &peng[ x ].y, &peng[ x ].numPenguins, &peng[x].mtime );
sumAllPenguins += peng[x].numPenguins;
}
memset( graph, 0, sizeof( graph ));
for( x = 0; x < n; x++)
for( y = 0; y < n; y++)
if( x != y && distPenguins( peng[x], peng[y]) <= dist*dist ){
graph[x*2+1][y*2] = (1<<22);
}
for( x = 0; x < n; x++){
graph[x*2][x*2 + 1] = peng[x].mtime;
}
ini = n*2;
for( x = 0; x < n; x++)
graph[ini][ x*2 ] = peng[x].numPenguins;
cont = 0;
for( x = 0; x < n; x++){
r = fordFulkerson( ini, x*2, n * 2 + 3);
if( r == sumAllPenguins){
if(cont > 0 ) printf(" ");
printf("%d", x);
cont++;
}
}
if( cont == 0 ) printf("-1");
printf("\n");
}
return 0;
}
</pre>
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-12237156101463000022012-05-22T16:42:00.000-05:002012-05-22T16:42:26.023-05:00Problema B: Adding New Machine (ACM Dalian Regional 2011)<br />
<h2>
Problema B: Adding New Machine<o:p></o:p></h2>
<div class="MsoNormal">
Les comparto un problema con su explicación del concurso de Dalian en China.</div>
<h3>
Descripción<o:p></o:p></h3>
<div class="MsoNormal">
Increíble loca
Compañía progresista ( ICPC por sus siglas en ingles), sufre demasiado por su
lenta producción. Después de una investigación, ellos encontraron que el
embotellamiento estaba en el Absulutely Crowded Manufactory (ACM). Para acelerar
el procedimiento, ellos compraron otra maquina para el ACM. Pero un nuevo
problema apareció, ¿como poner esta nueva maquina en el ACM?.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
ACM es un complejo
rectangular, que esta dividido en W*H celdas. Existen N viejas maquinas
rectangulares, y la nueva maquina no
puede ocupar ninguna celda donde existan maquinas viejas. La nueva maquina
necesita M celdas consecutivas. Celdas consecutivas significan una línea de
celdas adyacentes. Tu tarea es calcular el numero de formas diferentes en las
que se pueden colocar la nueva maquina.<o:p></o:p></div>
<h3>
Entrada<o:p></o:p></h3>
<div class="MsoNormal">
Hay múltiples casos
de prueba ( no mas de 50). La primera línea de cada caso de prueba contiene 4
enteros W, H, N , M ( 1 <= W, H <=
10^7 , 0 <= N <= 50000, 1 <= M <= 1000), indicando el ancho y el
largo de el ACM , el numero de maquinas viejas
y el tamaño de la nueva maquina. Las siguientes N líneas, cada una
contiene 4 enteros Xi1, Yi1 , Xi2 y Yi2 ( 1 <= Xi1 <= Xi2 <= W, 1
<= Yi1 <= Yi2 <= H), indicando las coordenadas de la i-e sima maquina
vieja. Se garantiza que no hay celdas ocupadas por dos maquinas viejas.<o:p></o:p></div>
<h3>
Salida<o:p></o:p></h3>
<div class="MsoNormal">
Imprimir el numero de formas de colocar la nueva maquina en
el ACM.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<table border="1" cellpadding="0" cellspacing="0" class="MsoTableLightShadingAccent1" style="border-collapse: collapse; border: none; mso-border-bottom-alt: solid #4F81BD 1.0pt; mso-border-bottom-themecolor: accent1; mso-border-top-alt: solid #4F81BD 1.0pt; mso-border-top-themecolor: accent1; mso-padding-alt: 0cm 5.4pt 0cm 5.4pt; mso-yfti-tbllook: 1184;">
<tbody>
<tr>
<td style="border-bottom: solid #4F81BD 1.0pt; border-left: none; border-right: none; border-top: solid #4F81BD 1.0pt; mso-border-bottom-themecolor: accent1; mso-border-top-themecolor: accent1; padding: 0cm 5.4pt 0cm 5.4pt; width: 224.45pt;" valign="top" width="224"><div class="MsoNormal">
<b><span style="color: #365f91;">Entrada Ejemplo<o:p></o:p></span></b></div>
</td>
<td style="border-bottom: solid #4F81BD 1.0pt; border-left: none; border-right: none; border-top: solid #4F81BD 1.0pt; mso-border-bottom-themecolor: accent1; mso-border-top-themecolor: accent1; padding: 0cm 5.4pt 0cm 5.4pt; width: 224.45pt;" valign="top" width="224"><div class="MsoNormal">
<b><span style="color: #365f91;">Salida Ejemplo<o:p></o:p></span></b></div>
</td>
</tr>
<tr>
<td style="background: #D3DFEE; border-bottom: solid #4F81BD 1.0pt; border: none; mso-background-themecolor: accent1; mso-background-themetint: 63; mso-border-bottom-themecolor: accent1; padding: 0cm 5.4pt 0cm 5.4pt; width: 224.45pt;" valign="top" width="224"><div class="MsoNormal">
<b><span style="color: #365f91;">3 3 1 2<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">2 2 2 2<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">3 3 1 3<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">2 2 2 2<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">2 3 2 2<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">1 1 1 1<o:p></o:p></span></b></div>
<div class="MsoNormal">
<b><span style="color: #365f91;">2 3 2 3<o:p></o:p></span></b></div>
</td>
<td style="background: #D3DFEE; border-bottom: solid #4F81BD 1.0pt; border: none; mso-background-themecolor: accent1; mso-background-themetint: 63; mso-border-bottom-themecolor: accent1; padding: 0cm 5.4pt 0cm 5.4pt; width: 224.45pt;" valign="top" width="224"><div class="MsoNormal">
<span style="color: #365f91;">8<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="color: #365f91;">4<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="color: #365f91;">3<o:p></o:p></span></div>
</td>
</tr>
</tbody></table>
<div style="border-bottom: solid windowtext 1.0pt; border: none; mso-border-bottom-alt: solid windowtext .75pt; mso-element: para-border-div; padding: 0cm 0cm 1.0pt 0cm;">
<div class="MsoNormal" style="border: none; mso-border-bottom-alt: solid windowtext .75pt; mso-padding-alt: 0cm 0cm 1.0pt 0cm; padding: 0cm;">
<br /></div>
<div class="MsoNormal" style="border: none; mso-border-bottom-alt: solid windowtext .75pt; mso-padding-alt: 0cm 0cm 1.0pt 0cm; padding: 0cm;">
<br /></div>
<div class="MsoNormal" style="border: none; mso-border-bottom-alt: solid windowtext .75pt; mso-padding-alt: 0cm 0cm 1.0pt 0cm; padding: 0cm;">
<br /></div>
</div>
<div class="MsoNormal">
<br /></div>
<h2>
Solución:<o:p></o:p></h2>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
La primera solución
que se nos presenta a simple vista es colocar en todas las posiciones vacías la
nueva maquina, y contar cuantas veces se puede colocar esta maquina, el único
problema es que W y H son muy grandes, y el costo de hacer esto es W*H*M (
10^17 ), por lo tanto no es una solución viable, pero de esta solución podemos sacar algunos
conclusiones que nos pueden ser útiles, por ejemplo cuando exploramos todas las
posibilidades <u>solo existen dos maneras de colocar una maquina iniciando en
una posiciones (fila, columna), una es colocándola horizontalmente y la otra es
verticalmente.</u><o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Para resolver un problema complicado primero hay que irnos a
lo particular, y de ahí movernos a lo general y es por eso que vamos a
resolverlo parte por parte de este problema.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Primero supongamos que solo es una línea sin obstáculos, si
la línea es de tamaño H y la longitud de la maquina es M, el numero de formas
que podemos colocar M es H – M + 1 , siempre y cuando M sea menor a H. <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Si todas las celdas de la matriz estuvieran libres de
obstáculos entonces podríamos contar con
facilidad de cuantas maneras podemos colocar esta nueva maquina en toda la
matriz. Suponiendo que la colocamos de
manera vertical, podemos calcular cada columna en 10^7 operaciones ( bueno pero
como todos es lo mismo podría ser con tan solo una multiplicación para todas las
columnas), para en este caso nos conviene realizar columna por columna, en el
caso de las filas cuando la maquina se coloca horizontalmente también se puede
contar fila por fila, en a lo mas 10^7 operaciones.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Esto es para el caso en que toda están vacías, con una sola
resta funciona, pero ¿que pasa cuando existen maquina ya colocadas y cuando son
50000 de ellas?. Para ese caso debemos primero observar un ejemplo, vean la
imagen siguiente:<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="margin-left: 106.2pt;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR2tL7qYgKW85kMzycRrOKQYwSqO6QWfpgaSGTWBqVbrGhyphenhyphenXWZ9N5Dw-Ecuhlw0bDenn6PgAQIc7TmDEE5ApTXkpVFMABFLRb_-w-JjhgzjrXjK-zvyDhpY6nMUpzSK8IY81dG094GGJg/s1600/grid1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="248" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR2tL7qYgKW85kMzycRrOKQYwSqO6QWfpgaSGTWBqVbrGhyphenhyphenXWZ9N5Dw-Ecuhlw0bDenn6PgAQIc7TmDEE5ApTXkpVFMABFLRb_-w-JjhgzjrXjK-zvyDhpY6nMUpzSK8IY81dG094GGJg/s320/grid1.jpg" width="320" /></a></div>
<span lang="ES"></span><o:p></o:p><br />
<span lang="ES"><br /></span><br />
<span lang="ES"><br /></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Como pueden ver, ningún rectángulo se empalma, si nosotros vamos
de izquierda a derecha, por cada columna vemos que en el a primera columna no
hay nada que nos limite, nosotros calculamos cuantas maquinas nuevas podemos
colocar en esta columna con una simple resta, pero en la segunda existe dos
rectángulos, cuando inician los rectángulos nosotros debemos calcular
exactamente los intervalos vacíos para calcular el numero de maquinas a
colocar, existen dos intervalos de 1 y 2, como nuestras maquina es de tamaño 2
, entonces podemos colocar 0 y 1
maquinas nuevas, si nosotros nos movemos a la tercera columna el numero de
maquina que vamos a colocar es la misma que en la segunda, ya que no hay ningún
rectángulo que termine o inicie, pero en la cuarta columna nos encontramos que
uno de los rectángulos se termina, y hay que calcular de nuevo la cantidad de
maquinas a colocar. En este caso quedaría un intervalo de 5, la cantidad de
maquinas que debemos colocar en esta columna es de 4.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
¿Que es lo que
podemos rescatar de esta parte?<o:p></o:p></div>
<div class="MsoNormal">
Nosotros podemos ver
que solamente hay que calcular las posiciones donde exista un cambio, donde se
agregue un nuevo rectángulo o donde se termine uno, en total el máximo numero
de posiciones donde pudiera ocurrir es esto son 100,000 ( ya que hay 50,000
rectángulos por dos ya que es donde
inicia un rectángulo y donde termina).<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
¿Pero como podemos calcular cada columna el numero de nuevas
maquina que debemos colocar? La respuesta es utilizar una estructura de datos
para contarlas.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
¿Qué estructura de datos utilizaríamos para contar los
segmentos unidos y restara M a cada uno de ellos?<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Un<b> Árbol de
Intervalos</b> nos serviría para nuestros propósitos,(Véase el capítulo de
estructura de datos avanzadas), el <b>Árbol
de Intervalos</b> nos puede ayudar al conteo de estos segmentos, ya que para
cada nodo podemos guardar:<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
1 – numero de maquinas que podemos contar sin contar la de
los extremos.<o:p></o:p></div>
<div class="MsoNormal">
2 – numero de posiciones no marcadas pegadas a la izquierda .<o:p></o:p></div>
<div class="MsoNormal">
3 – numero de posiciones no marcadas a la derecha.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Supongamos que tenemos una maquina de tamaño 1x2, este es el
tamaño de la maquina que queremos insertar, la siguiente figura muestra una
fila vacía, sin ningún rectángulo en ella.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgqrlYLj6Aow5wMpTpUpCl9oCBsDNCg1t08vUngJMAhyj4m-Zuy1HdQJD9-OwPIoxZj9odN_E4pBCIUjYTIh6asxniHjzzY-jiXw49p2V0Zu_xdses3Ts7EZBlc-XhNMPyNXm8omUdfnI/s1600/acm1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="40" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgqrlYLj6Aow5wMpTpUpCl9oCBsDNCg1t08vUngJMAhyj4m-Zuy1HdQJD9-OwPIoxZj9odN_E4pBCIUjYTIh6asxniHjzzY-jiXw49p2V0Zu_xdses3Ts7EZBlc-XhNMPyNXm8omUdfnI/s320/acm1.jpg" width="320" /></a></div>
<span lang="ES"></span><o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Si nosotros queremos insertar una maquina que va de la
columna 2 a la columna 6 y otra maquina de la 8 a la 10 quedaría de esta manera.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7MW3bmOYQ-daRE4OECxOhaAwCuPwK_DGHLw_vCMPysHtxL8rZfiQb6H_0sIvCArusw8Pv4d9YObRnVix-67ZTReHknffB3KQRS-7q77wc6W5KL9ewYOLtBNGOhloJNjMqNMacuiKbM8A/s1600/acm2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="30" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg7MW3bmOYQ-daRE4OECxOhaAwCuPwK_DGHLw_vCMPysHtxL8rZfiQb6H_0sIvCArusw8Pv4d9YObRnVix-67ZTReHknffB3KQRS-7q77wc6W5KL9ewYOLtBNGOhloJNjMqNMacuiKbM8A/s320/acm2.jpg" width="320" /></a></div>
</div>
<div class="MsoNormal">
En nuestro árbol de intervalos, quedaría de la siguiente
manera: <o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="margin-left: 35.4pt;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglDXIglVBlTsqvUw1m9W0pV_4SRe52E0aw8sztJTaL6xEqXS7eDlPXam-cnUc-1dYKu1fmO8o9ZRc5jT4bvBeZeLrmEzrOP6aWl_seGu7NBg8dDs0PslM1pCAoGedLs9fTv-zaQkJ7DKw/s1600/arbol1.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="433" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglDXIglVBlTsqvUw1m9W0pV_4SRe52E0aw8sztJTaL6xEqXS7eDlPXam-cnUc-1dYKu1fmO8o9ZRc5jT4bvBeZeLrmEzrOP6aWl_seGu7NBg8dDs0PslM1pCAoGedLs9fTv-zaQkJ7DKw/s640/arbol1.jpg" width="640" /></a></div>
<span lang="ES"></span><o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Cado nodo padre puede sacar la información de sus hijos, por
ejemplo en el nodo que tiene la información del segmento [1, 8] , puede calcularlo
con sus dos hijos, el [1,4] y el [5,8], para calcular la información se sigue
los siguientes pasos.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoListParagraphCxSpFirst" style="mso-list: l0 level1 lfo1; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Cuadros izquierdos : Son los cuadros izquierdos
del hijo izquierdo.<o:p></o:p></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l0 level1 lfo1; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Cuadros derechos: Son los cuadros derechos del
hijo derecho.<o:p></o:p></div>
<div class="MsoListParagraphCxSpLast" style="mso-list: l0 level1 lfo1; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Numero de maquinas: La suma del numero de maquinas de los dos
hijos mas la suma de los cuadros
derechos del hijo izquierdo y los cuadros izquierdo del hijo derecho menos M (
M es el tamaño de la nueva maquina), si el resultado es negativo entonces
colocar 0.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
¿Que pasa cuando uno de los dos hijos nodos esta
completamente lleno?<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
En ese caso el calculo es distinto, el hijo que tiene todos
los cuadros llenos, no tiene un lado izquierdo o derecho con cuadros , si no
todo el segmento esta completo y tanto el lado izquierdo como derecho son los
mismos cuadros.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Para el caso especifico del nodo que representa el segmento
[1,4] del ejemplo anterior, que se muestra en la siguiente figura:<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal" style="margin-left: 106.2pt;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhB5dJhNm8FRSigRS-HoNRhN3mMmwPWY-nQL13CiFe4AK6xOZCh4iZZurrDYAczVOikyGGSgfVYvjw8RNdH4KnXRAJnt06gR9hacljPBT71_om50Qf0osdq5VrXjD3GUoeO4x3MFT6U494/s1600/arbol2.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="270" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhB5dJhNm8FRSigRS-HoNRhN3mMmwPWY-nQL13CiFe4AK6xOZCh4iZZurrDYAczVOikyGGSgfVYvjw8RNdH4KnXRAJnt06gR9hacljPBT71_om50Qf0osdq5VrXjD3GUoeO4x3MFT6U494/s400/arbol2.jpg" width="400" /></a></div>
</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Se calcula de la siguiente manera<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoListParagraphCxSpFirst" style="mso-list: l2 level1 lfo2; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Cuadros izquierdos: cuadros izquierdos del hijo izquierdo.<o:p></o:p></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l2 level1 lfo2; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Cuadros derechos: la suma de los cuadros del
hijo derecho mas los cuados derecho del hijo izquierdo.<o:p></o:p></div>
<div class="MsoListParagraphCxSpLast" style="mso-list: l2 level1 lfo2; text-indent: -18.0pt;">
<span style="font-family: Symbol;">·<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span></span>Numero de maquinas: El numero de maquinas del
lado izquierdo.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Como pueden ver se tiene que validar si esta completo alguno
de sus hijos o si los dos están llenos, en el caso de que alguno este vacío
aplica los mismo que en el primer escenario.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
¿Pero por que es tan rápido un árbol de intervalos en este
problema?<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Cuando agregamos un nuevo cuadrado al árbol, iniciamos de la
raíz el nodo que representa a todo el intervalo [1,N], y nos movemos por sus hijos, ya en los hijos
nos vamos recursivamente por todos las ramas del árbol hasta el final. Con las
siguiente condiciones:<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoListParagraphCxSpFirst" style="mso-list: l1 level1 lfo3; text-indent: -18.0pt;">
1.<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span>Si el nodo donde estamos su intervalo ya no esta
dentro del que queremos hacer una modificación , no seguimos exploras.<o:p></o:p></div>
<div class="MsoListParagraphCxSpMiddle" style="mso-list: l1 level1 lfo3; text-indent: -18.0pt;">
2.<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span>Si el nodo donde estamos su intervalo queda
absorbido por el intervalo donde vamos a modificar entonces solo modificamos
ese nodo, y dejamos una bandera ahí, diciendo que todos los cuadros de este
segmento o están usados o están libres, y ya no seguimos con los demás.<o:p></o:p></div>
<div class="MsoListParagraphCxSpLast" style="mso-list: l1 level1 lfo3; text-indent: -18.0pt;">
3.<span style="font-family: 'Times New Roman'; font-size: 7pt;">
</span>Si no pasa ninguna de las anteriores, entramos a
los hijos del nodo actual y realizamos el paso 1 y 2.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Y como pueden ver no se explora todo el árbol en cada
modificación si no solo una parte de el, que seria dos veces el largo de las
ramas y dependiendo del la longitud del segmento seria la longitud de la rama
igual a log( longitud del segmento ).<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Para saber después de nuestras inserciones y eliminaciones
cuantas maquinas caben en la fila o columna procesando, seria de la siguiente
manera:<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
El numero de maquinas es igual a el numero de maquinas de la
raíz mas max( 0, los cuadros del lado
izquierdo – M) + max( 0, los cuadros del lado derecho – M ) , donde M es el
tamaño de la maquina.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Nuestra bandera seria un nuevo elemento del árbol.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<img align="left" alt="Cuadro de texto: La complejidad de este algoritmo es la siguiente O( N x log max( W, H) ).
" height="29" hspace="9" src="file://localhost/Users/rodrigoburgosdominguez/Library/Caches/TemporaryItems/msoclip/0/clip_image011.png" v:shapes="Cuadro_x0020_de_x0020_texto_x0020_7" width="382" /><o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<b>Nota</b>: Uno debe
notar que cuando M es 1 solo hay que explorándolo vertical o horizontalmente,
ya que su rotación vertical u horizontal es la misma, y solo contaríamos el
doble.<o:p></o:p></div>
<h3>
Código<o:p></o:p></h3>
<div class="MsoNormal">
<span style="font-family: Century;">#
include <stdio.h><o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">#
include <string.h><o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">#define
MAXRECTANGLES 50002<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">int
W, H, N, M, nbreakp, memtree;<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">typedef
struct { int X[2], Y[2];} RECTANGLE;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">typedef
struct { int izq, der, countL, countR, count, delete, fill; } INTERVALTREE;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">typedef
struct { int coorden, position, accion; } BREAKPOINT;<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">INTERVALTREE
MEM[ MAXRECTANGLES * 30 ];<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">RECTANGLE
R[MAXRECTANGLES + 1];<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">BREAKPOINT
BP[ (MAXRECTANGLES + 1) * 2];<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">int
comparebp( BREAKPOINT *A, BREAKPOINT *B ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if(A->coorden != B->coorden ) return
A->coorden - B->coorden;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> return B->accion - A->accion; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">int
min(int a, int b ){ return a < b ? a : b; }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">int
max(int a, int b ){ return a > b ? a : b; }<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">INTERVALTREE
getNode(int punter, int A, int B){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> INTERVALTREE tmp;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.countL = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.countR = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.count = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.fill = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.delete = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( punter != -1 &&
MEM[punter].delete == 0 ) return MEM[ punter ];<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( punter == -1 || MEM[punter].delete == 2
){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.countL = B - A + 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> tmp.fill = 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> return tmp;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">void
insert( int *punter, int A, int B, int a, int b, int type){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> int med = (A + B ) / 2;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> INTERVALTREE left, rigth;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( B < a || b < A ) return;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if(*punter == -1 ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> *punter = memtree++;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].izq = -1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].der = -1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].count = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countR = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].fill = 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countL = ( B - A + 1);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter ].delete = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }else<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[*punter ].delete >= 1){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[*punter].izq != -1)
MEM[MEM[*punter].izq].delete = MEM[*punter ].delete;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[*punter].der != -1)
MEM[MEM[*punter].der].delete = MEM[*punter ].delete;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter ].delete = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( a <= A && B <= b ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countL = ( type == 0 ? 0 : B - A + 1); <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].fill = type; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countR = 0; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].count = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[*punter].izq != -1)
MEM[MEM[*punter].izq].delete = 1 + type;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[*punter].der != -1)
MEM[MEM[*punter].der].delete = 1 + type;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">
return;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> insert(&MEM[*punter].izq, A, med, a, b,
type);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> insert(&MEM[*punter].der, med+1, B, a, b,
type);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> /* Calcular */<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> left = getNode(MEM[*punter].izq , A, med);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> rigth = getNode(MEM[*punter].der, med +1 , B
);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( left.fill == 1 && rigth.fill == 1
){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].fill = 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countL = B - A + 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countR = 0; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].count = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }else if( left.fill == 1 ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[ *punter].fill = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countL = left.countL +
rigth.countL;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countR = rigth.countR;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].count= rigth.count;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }else if( rigth.fill == 1 ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[ *punter].fill = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countR = left.countR +
rigth.countL;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].countL = left.countL;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].count= left.count;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }else{<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> MEM[*punter].fill = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">
MEM[*punter].countL = left.countL;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">
MEM[*punter].countR = rigth.countR;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">
MEM[*punter].count = left.count+ rigth.count+<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> max( 0, left.countR
+ rigth.countL - M + 1) ;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">int
count( int punter, int A, int B){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( punter == -1 ) return ( B - A + 1 ) - M +
1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[punter].delete == 2 ) return ( B - A
+ 1 ) - M + 1;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( MEM[punter].delete == 1 ) return 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> return MEM[punter].count + max( 0 , MEM[punter].countL
- M + 1) + max( 0, MEM[punter].countR - M + 1); <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">long
long process( int axis , int width, int length){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> int lastpos = 1, cpos, indice = -1, A, B,
pos;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> long long currentCont, response = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> memtree = 0;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for( pos = 0; pos < nbreakp; pos++){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( lastpos != BP[pos].coorden ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> currentCont = (long long)count( indice,
1, length);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> response += currentCont * (long long)(
BP[ pos ].coorden - lastpos);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> cpos = BP[ pos ].coorden;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> A = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[
0 ] : R[ BP[ pos ].position ].X[ 0 ];<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> B = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[
1 ] : R[ BP[ pos ].position ].X[ 1 ];<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> insert( &indice , 1, length, A, B, BP[ pos
].accion );<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> lastpos = cpos;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> currentCont = (long long)count( indice, 1,
length);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> response += currentCont * (long long)( width
- lastpos + 1);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> return response;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<span style="font-family: Century;">main(){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> int rec, nc;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> long long cont;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> while( scanf("%d %d %d %d", &W,
&H, &N, &M) != EOF ){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for( rec = 0; rec < N; rec++) <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> scanf("%d %d %d %d", &R[
rec ].X[0], &R[ rec ].Y[0], &R[ rec ].X[1], &R[ rec ].Y[1]);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for( nbreakp = rec = 0; rec < N; rec++){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for(nc = 0; nc < 2; nc++){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp ].position = rec;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp ].accion = nc;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp++].coorden = R[rec].X[ nc
] + nc; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> qsort(BP, nbreakp, sizeof( BREAKPOINT ),
comparebp );<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> cont = process( 0, W , H);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for( nbreakp = rec = 0; rec < N; rec++){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> for(nc = 0; nc < 2; nc++){<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp ].position = rec;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp ].accion = nc;<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> BP[ nbreakp++].coorden = R[rec].Y[ nc
] + nc; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> qsort(BP, nbreakp, sizeof( BREAKPOINT ),
comparebp );<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> if( M > 1 )<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> cont
+= process( 1, H, W);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> printf("%lld\n", cont);<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> }<o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;"> return 0; <o:p></o:p></span></div>
<div class="MsoNormal">
<span style="font-family: Century;">}<o:p></o:p></span></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Cualquier duda o sugerencia escribirme a rodrigo.burgos@gmail.com</div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
<br /></div>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-45697918951462385092012-05-22T14:05:00.001-05:002012-05-22T14:05:21.215-05:00Factors in Bin-packing instances<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>ACM Mexico Centro America y el Caribe 2004, Factors in Bin-packing instances </h3>
<br />
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1100
<br />
Estaba recordando el regional cuando pasamos en primer lugar en una competencia donde al final del concurso teníamos 3 problemas y en el que estábamos peleándonos por tres mas pos-concurso, al final acabamos con 5 problema y pasamos al mundial.
<br />
Ese concurso fue inolvidable, como la BUAP gano con 5 problemas y también otro equipo de la BUAP intento con éxito hackear el PCS^2, al final los descubrieron pero fue épico, ya que en la lista del regional aparecía la BUAP en primer lugar con los alfalfas y en ultimo lugar con los BUAPandrosos.
<br />
Y es por ello que volví a ver los problemas del concurso y hay uno que no leí y que tampoco resolvimos por un solo caso de prueba, nos comentaron después los jueces, prácticamente el problema es dada un numero div = [n*f + .99999 ] que se calcula de multiplicar dos variables que te dan en el problema, hacer que una lista dada tenga exactamente el numero div de elementos que sean divisores de una variable C (dada en la entrada) .
<br />
Entonces para resolver el problema es ver cuantos números ya dividen a C, y ver si necesitamos mas divisores o menos, también nos pide el problema que sea el menor numero de unidades que se tengan que restar o sumar a los números.
<br />
Ya que sabemos si el numero de divisores es menor o mayor al valor esperado ( div ), entonces para cada numero en la lista calculamos el costo de transformarlo a un divisor o bien a un no divisor si queremos incrementar o decrementar los divisores.
<br />
Ordenamos por costo, y al final con un for vamos marcando el numero de divisores que nos sobran o nos hacen falta para que se impriman con el cambio, siempre de menor a mayor, si el costo es 0, entonces no podemos usar esos números por que ya son o divisores o no divisores.
<br />
Les dejo el código:
<br />
<br />
<pre class="brush:perl">
# include "stdio.h"
# include "string.h"
typedef struct { int value, nextValue, cost, position, changed; } TYPE;
TYPE types[1000000];
int solution[100000];
int min( int a, int b ){ return a < b ? a : b; }
int compare( TYPE *a, TYPE *b){
if( a->cost != b->cost) return a->cost - b->cost;
return a->position - b->position;
}
main(){
int n, c, contDivisors;
int expectedValue, x, c1, c2, r;
double value;
while( scanf("%lf", &value ) != EOF ){
scanf(" %d , %d", &n, &c);
expectedValue = (int)(value * (double)n + (double)0.9999999999999);
contDivisors = 0;
for(x = 0; x < n; x++){
scanf("%d", &types[ x ].value);
contDivisors += (types[x].value != 0 && (c % types[x].value) == 0) ? 1 : 0;
}
for(x = 0; x < n; x++){
types[x].position = x;
if( contDivisors <= expectedValue ){
/* UP */
c1 = c2 = 0;
for( r = types[x].value ; r <= c; r++ ){
if( r != 0 && (c % r) == 0 ) break;
c1++;
}
/* DOWN */
for( r = types[x].value ; ; r-- ){
if( r != 0 && (c % r) == 0 ) break;
c2--;
}
types[x].cost = min( c1, -c2);
if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
else types[x].nextValue = types[x].value + c1;
types[x].changed = 0;
}else{
/* UP */
c1 = c2 = 0;
for( r = types[x].value ; r <= c; r++ ){
if( r == 0 && (c % r) != 0 ) break;
c1++;
}
if( r > c ) c1 = (1<<28);
/* DOWN */
for( r = types[x].value ; ; r-- ){
if(r == 0 && (c % r) != 0 ) break;
c2--;
}
types[x].cost = min( c1, -c2);
if( -c2 < c1 ) types[x].nextValue = types[x].value + c2;
else types[x].nextValue = types[x].value + c1;
types[x].changed = 0;
}
}
qsort( types, n, sizeof( TYPE ), compare );
for( x = 0; x < n && contDivisors != expectedValue ; x++){
if( types[x].cost == 0 ) continue;
contDivisors += ( contDivisors > expectedValue ) ? -1 : 1;
types[x].changed = 1;
}
for( x = 0; x < n; x++){
solution[types[x].position ] = ( types[x].changed ) ? types[x].nextValue : types[x].value;
}
printf("%d, %d\n", n, c);
for( x = 0; x < n; x++){
printf("%d\n", solution[ x ]);
}
}
return 0;
}
</pre>
Cualquier duda o sugerencia contactarme a rodrigo.burgos@gmail.com
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com7tag:blogger.com,1999:blog-7137669718769202647.post-16573187047320371992012-03-24T20:41:00.000-06:002012-03-24T21:00:22.755-06:0010358 Matrix ( MINIMAX )<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
http://uva.onlinejudge.org/external/103/10358.html
Estaba revisando este problema y recordando cuando intente resolverlo hace ya mas de 8 años no tenia ni idea de como resolver un problema de este tipo, cuando aprendi a resolverlos con la tecnica de minimax, me tope con que como podia hacer un minimax sobre este problema si puede haber ciclos, ya que el minimax se resuelve con una dinamica y una dinamica para poder resolver el problema no debe tener ciclos, ahora que lo vuelvo a leer, es obvio que cuando se hacen mas de 32 movimientos entonces ya no lo pueden atrapar y por tanto se envia el mensaje "You are trapped in the Matrix.", y para evitar los ciclos enviamos en la dinamica el nivel, este nivel es el numero de pasos, si es par entonces se mueve neo en otro caso se mueven los agentes, los agentes tratan de minimizar y neo trata de maximizar. Al final si el valor que regresa la dinamica es 0 , indica que no lo pueden atrapar pero tampoco pudo escapar, si es -1 entonces lo atraparon, y si es 1 puede escapar. aqui les dejo el codigo.
<pre class="brush:perl">
/* Autor: Rodrigo Burgos Dominguez */
# include <stdio.h>
# include <string.h>
char map[10][10];
int dx[5]={0, 1, -1, 0, 0};
int dy[5]={0, 0, 0, 1, -1};
int din[40][8][8][8][8][8][8];
int vis[40][8][8][8][8][8][8], cases;
int max(int a, int b ){ return a > b ? a : b; }
int min(int a, int b ){ return a < b ? a : b; }
void find( int a, int b, int *A,int *B, char ch ){
int cont = 0;
for( ; a < 8; a++, cont++)
for(b = ( cont == 0 ) ? b : 0 ; b < 8 ; b++, cont++)
if( map[a][b] == ch ){
*A = a;
*B = b;
return;
}
}
int canWalk(int ax, int ay, int aX, int aY, int nx, int ny){
if( ax < 0 || ay < 0 || nx < 0 || ny < 0 || aX < 0 || aY < 0 ) return 0;
if( ax >= 8 || ay >= 8 || nx >= 8 || ny >= 8 || aX >= 8 || aY >= 8 ) return 0;
if( map[ax][ay] == '#' || map[aX][aY] == '#' || map[nx][ny] == '#') return 0;
return 1;
}
int solve( int level, int ax, int ay, int aX, int aY, int nx, int ny){
int res, d1, d2;
if( level >= 40 ) return 0;
if( ax == nx && ay == ny ) return -1;
if( aX == nx && aY == ny ) return -1;
if( map[nx][ny] == 'P' ) return 1;
if( vis[level][ax][ay][aX][aY][nx][ny] == cases) return din[level][ax][ay][aX][aY][nx][ny];
vis[level][ax][ay][aX][aY][nx][ny] = cases;
if( level % 2 == 0 ){ /* Move neo */
res = -1;
for(d1 = 0; d1 < 5; d1++)
if( canWalk( ax, ay, aX, aY, nx + dx[ d1 ], ny + dy[ d1 ])){
res = max( res, solve(level + 1, ax, ay, aX, aY, nx + dx[ d1 ] , ny + dy[ d1 ]) );
}
}else{ /* move agents */
res = 1;
for( d1 = 0; d1 < 5; d1++)
for( d2 = 0; d2 < 5; d2++)
if( canWalk( ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny ) ){
res = min( res, solve( level + 1, ax + dx[d1], ay + dy[d1 ], aX + dx[d2], aY + dy[d2], nx, ny) ) ;
}
}
return din[level][ax][ay][aX][aY][nx][ny] = res;
}
main(){
int ncases, ax,ay,aX,aY,nx,ny, x, r;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
for( x = 0; x < 8; x++) scanf("%s", map[ x ]);
find( 0, 0 , &ax, &ay, 'A');
find( ax, ay+1 , &aX, &aY, 'A');
find( 0, 0 , &nx, &ny, 'M');
r = solve(0, ax, ay, aX, aY, nx, ny);
if( r == 0 ) printf("You are trapped in the Matrix.\n");
else if( r < 0 ) printf("You are eliminated.\n");
else printf("You can escape.\n");
}
return 0;
}
//</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-34078426527549901062012-03-24T17:56:00.001-06:002012-03-24T17:59:16.315-06:00108 Maximum Sum ( DP + Inclusion exclusion)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
Un claro ejemplo de programacion dinamica e inclusion exclusion.
http://uva.onlinejudge.org/external/1/108.html
<pre class="brush:perl">
/* Autor: Rodrigo Burgos Dominguez */
# include <stdio.h>
# include <string.h>
int max(int a,int b){ return a > b ? a : b; }
int sum[200][200], data[200][200], n;
main(){
int x, y, a, b, sol;
scanf("%d", &n);
for( x = 0; x < n ; x++)
for( y = 0; y < n ; y++) scanf("%d", &data[ x ][ y ]);
memset( sum, 0, sizeof( sum ));
for( x = n - 1; x >= 0; x--){
for( y = n - 1; y >= 0 ; y-- ) sum[x][y] = sum[x][y + 1] + data[x][ y ];
for( y = n - 1; y >= 0 ; y-- ) sum[x][y] += sum[x+1][y];
}
sol = -(1<<28);
for( x = 0; x < n; x++)
for( y = 0; y < n; y++)
for( a = x; a < n; a++)
for( b = y; b < n; b++)
sol = max( sol, sum[x][y] - sum[x][b + 1] - sum[a + 1][y] + sum[a+1][b+1]);
printf("%d\n", sol);
return 0;
}
//</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-29180859712368610842012-03-21T17:08:00.000-06:002012-03-21T17:08:28.397-06:00Hedge Mazes ACM Latinamerica 2011<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<pre class="brush:perl">
# include "stdio.h"
# include "string.h"
# define MAXNODOS 10000
int R, C, Q;
int *graph[ MAXNODOS + 1], ngraph[ MAXNODOS + 1];
int mem[(MAXNODOS + 1)*40], arista[ MAXNODOS * 40 + 1][ 2 ];
int vis[MAXNODOS + 1] , mark[ MAXNODOS + 1], SET[MAXNODOS + 1], posNode[MAXNODOS + 1];
int getSet( int node ){ return node == SET[node] ? node : (SET[ node ] = getSet( SET[node])); }
int max( int a, int b ){ return a > b ? a : b; }
int min( int a, int b ){ return a < b ? a : b; }
int componentConection( int node, int level , int father){
int response = level, x;
if( vis[ node ] == 1 ) return mark[ node ];
if( vis[node] == 2) return response;
mark[ node ] = level;
posNode[level] = node;
vis[ node ] = 1;
for( x = 0; x < ngraph[ node ]; x++) if( graph[node][x] != father ){
response = min( response, componentConection( graph[node][x], level + 1, node ) );
SET[ getSet( node )] = getSet( posNode[response] );
}
vis[node] = 2;
return response;
}
void markSameLine( int node , int value, int father){
int x;
if( mark[ node ] > 0 ) return;
mark[ node ] = value;
for( x = 0; x < ngraph[ node ] ; x++ ) if( graph[node][x] != father ){
if( getSet( graph[node][x] ) != getSet( node ) ){
markSameLine( graph[ node ][ x ], value, node );
}
}
}
main(){
int a, b, x, y, nmem;
while( scanf("%d %d %d", &R, &C, &Q) != EOF && ( R || C || Q)){
memset( ngraph, 0, sizeof( ngraph ));
for( x = 0; x < C; x++){
scanf("%d %d", &a, &b);
arista[ x ][ 0 ] = a;
arista[ x ][ 1 ] = b;
ngraph[ a ]++;
ngraph[ b ]++;
}
nmem = 0;
for( x = 0; x <= R; x++){
graph[ x ] = mem + nmem;
nmem += ngraph[ x ];
}
memset( ngraph, 0, sizeof( ngraph ));
for( x = 0; x < C; x++){
a = arista[ x ][ 0 ];
b = arista[ x ][ 1 ];
graph[a][ngraph[a]++] = b;
graph[b][ngraph[b]++] = a;
}
memset( vis, 0, sizeof( vis ));
memset( mark, 0, sizeof( mark ));
for( x = 0; x <= R; x++) SET[ x ] = x;
for( x = 1; x <= R; x++)
if( vis[ x ] == 0 )
componentConection( x , 0, x );
memset( mark, 0, sizeof( mark ));
for( x = 1; x <= R; x++) if( mark[ x ] == 0 ){
markSameLine( x, x, x);
}
for( x = 1; x <= Q; x++){
scanf("%d %d", &a, &b);
if( ( mark[ a ] == 0 || mark[b] == 0 ) || mark[ a ] != mark[ b ]) printf("N\n");
else printf("Y\n");
}
printf("-\n");
}
return 0;
}
}//</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-53660501843564244292012-01-24T01:12:00.000-06:002012-01-24T01:12:00.629-06:00Hacker Cup 2012 Qualification Round<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h2>
Hacker Cup 2012 Qualification Round </h2>
<br />
<a href="https://www.facebook.com/hackercup/problems.php?pid=215823855164332&round=146094915502528"> <h3> Billboards</h3> </a> <br />
<br />
Este problema practicamente es de simulacion, uno va incrementando el tamaño de las letras y al final valida que no se salgan del tamaño maximo de filas y columnas.
<br />
<pre class="brush:perl">
# include <stdio.h>
# include <string.h>
char words[1001][1001], line[1001];
int nwords;
main(){
int ncases, cases, sol, row, col, W, H, x;
char *buf;
for( scanf("%d", &ncases), cases = 1; cases <= ncases; cases++ ){
scanf("%d %d", &W, &H);
gets( line );
nwords = 0;
for( buf = strtok( line, " \n" ) ; buf != NULL ; buf = strtok( NULL, " \n") ){
strcpy( words[ nwords++ ], buf );
}
row = 0;
for( sol = 1; ; sol++){
col = 0;
row = sol;
for( x = 0 ; x < nwords ; x++ ){
if( sol * strlen( words[ x ] ) + col + ( col > 0 ? sol : 0 ) <= W ){
col = sol * strlen( words[ x ] ) + col + ( col > 0 ? sol : 0 );
}else {
if( col == 0 ) break;
col = 0;
row += sol;
x--;
}
}
if( x < nwords ) break;
if( row > H ) break;
}
printf("Case #%d: %d\n", cases, sol - 1 );
}
return 0;
}//</pre>
<br />
<a href="https://www.facebook.com/hackercup/problems.php?pid=268598303201105&round=146094915502528"> <h3>Auction</h3> </a> <br />
<br />
Un problema realmente dificil, la fuerza bruta no funciona, lo que mas me pude acercar fue a una solucion 10^14 que no correria en tiempo, como estan los modulos tanto para W como para P a lo mas de 10^7, siempre se puede encontrar un ciclo menor o igual a eso, y con eso podemos ver que el LCM ( largo de W, largo de P ) es el maximo ciclo que tenemos que recorrer, el unico problema con eso es que este LCM puede ser mas grande incluso que N. ( alguien tiene alguna idea para resolverlo??? ).
<br />
<pre class="brush:perl">
Not solved.
</pre>
<br />
<a href="https://www.facebook.com/hackercup/problems.php?pid=341666075863455&round=146094915502528"> <h3>Alphabet Soup</h3> </a> <br />
<br />
Este problema se puede resolver con una tecnica de hash, en un arreglo una cuenta cuantas veces esta una letra ( en <b> H </b> guardo el numero de letras que hay en HACKERCUP ), teniendo las letras de <b>HACKERCUP</b> contadas, contamos las de cada uno de los casos de prueba ( en <b> hash </b> ) , y para obtener la solucion solo dividimos cada letra de hackercup encontrada en el caso de prueba con las que tenemos en nuestra palabra base, el minimo de ellas es la respuesta.
<br />
<pre class="brush:perl">
# include <string.h>
# include <stdio.h>
int min( int a, int b ){ return a < b ? a : b; }
int H[256];
int hash[256];
char line[1002];
char hackercup[ 12 ] ="HACKERCUP";
main(){
int x, cases, ncases, length, sol;
memset( H, 0, sizeof( H ));
for( x = 0; x < strlen( hackercup ) ; x++) H[ hackercup[ x ] ]++;
for( gets( line ) , sscanf(line, "%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
gets( line );
memset( hash, 0, sizeof( hash ));
length = strlen( line );
for( x = 0; x < length ; x++ ){
hash[ line[ x ] ]++;
}
sol = (1<<22);
for( x = 0; x < strlen( hackercup ) ; x++) sol = min( sol, hash[ hackercup[ x ] ] / H[ hackercup[ x ] ] ) ;
printf("Case #%d: %d\n", cases, sol);
}
return 0;
}//</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-32732543899829918292012-01-20T00:19:00.003-06:002012-01-20T00:26:42.167-06:00TOPCODER SRM 530 DIV 1<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h2>
TOPCODER SRM 530 DIV 1 </h2>
<br />
Ayer 19 de febrero se realizo el SRM 530, donde solo Vasyl[alphacom] pudo resolver todos los problemas.
<a href="http://community.topcoder.com/stat?c=problem_statement&pm=11274 "> <h3> Problema 250: GogoXCake </h3> </a> <br />
Para solucionar este problema habria uno que notar que como no se puede rotar el cortador entonces la unica forma que podemos comer el primero pedazo de pastel (En otras palabras el pedazo de pastel que tenga la fila mas pegada hacia arriba y si hay varias que tenga la columan mas pegada a la izquierda) y cumplir con lo que dice el problema, es colocar el cortador de igual manera en celda de uso que este en la fila 0 y columna mas a la izquierda ( en el problema indica que siempre en la primera fila va a existir por lo menos una celda que se debe usar), ya teniendo esto lo que hacemos es ver que las demas celdas del cortador qeu se tengan que usar tengan pastel, que ademas que el cortador no se salga del pastel, y cuando la celda se coma en el vector cake esa fila y columna tambien este vacia.
Si realizamos ese procedimiento cada vez que encontremos un pedazo de pastel que no hemos comido y que deberiamos habernoslo comido ( y no encontramos ninguna inconsistencia antes mencionadas ) regresamos "YES", en otro caso regresamos "NO".
<br />
<pre class="brush:perl">
class GogoXCake {
public:
string solve(vector <string>, vector <string>);
};
char O[100][100];
string GogoXCake::solve(vector <string> cake, vector <string> cutter) {
int n = cake.size() , m = cake[ 0 ].size(), posy ;
for( int x = 0; x < n; x++)
for( int y = 0; y < m; y++)
O[x][y] = 'X';
for( int a = 0; a < n; a++){
for(int b = 0; b < m; b++){
if( cake[ a ][ b ] == '.' && O[a][b] != '.' ){
int x, y;
for( x = 0; x < cutter[ 0 ].size() ; x++) if( cutter[ 0 ][ x ] == '.' ) break;
posy = ( b - x );
if( posy < 0 ) return "NO";
for( x = 0; x < cutter.size(); x++)
for( y = 0; y < cutter[ 0 ].size() ; y++){
if( cutter[ x ][ y ] == '.' ){
if( a + x >= n || posy + y >= m ) return "NO";
if( O[ a + x ][ posy + y ] == '.' || cake[a + x ][ posy + y ] == 'X' ) return "NO";
O[ a + x ][ posy + y ] = '.';
}
}
}
}
}
return "YES";
}
//</pre>
<br />
<a href="http://community.topcoder.com/stat?c=problem_statement&pm=11267"> <h3>Problema 500: GogoXMarisaKirisima</h3> </a> <br />
<br />
Este problema es un Greedy, primero hay que observar que para el primer paso que hay que dar es encontrar una solucion ( un camion del nodo 0 al nodo N - 1) si no existe por lo menos un camino entonces la respuesta es 0, en otro caso nosotros borramos de la matriz de adyacencia ( o marcamos como usados ) , las aristas de nuestro camino ( en el algoritmo marcamos en la matriz <b> mat </b> los usados ), tambien marcamos los nodos que ya estan en algun camino del nodo 0 al nodo N - 1. ( en el algoritmo marcamos los nodos usados en el arreglo <b> mark </b> ) <br />
El siguiente paso es darnos cuenta que si ya tenemos un camino de nodo 0 al nodo N - 1 entonces toda arista que salga de un nodo marcado a otro nodo marcado , indicaria que esta arista une una parte del camino de 0 a N - 1 con otra parte de ese mismo camino, o bien que conecta dos caminos distintos, en cualquiera de esos casos, podriamos encontrar una nueva forma de llegar de 0 a N - 1 con esa arista nueva, si eso pasa incrementamos el numero de formas ( <b> cont++ </b> ). </br >
¿Que pasa cuando ya no encontramos aristas para agregar ? , bueno si no encontramos mas aristas que cumplan con eso, lo que tenemos que hacer es buscar otro camino del nodo 0 al nodo N - 1, sin usar las aristas ya utilizadas. <br /> <br />
<b> Nota: </b> cuando busquemos un camino nuevo no necesariamente sale de 0 , si no de cualquiera de los nodos marcados ( aquellos que pertenecen a un camino ) y el destino no es N - 1, si no cualquier nodo que tambien pertenesca a un camino. ( la funcion F realiza esa funcion y verifica que por lo menos se agregue una arista nueva en la busqueda ).
<br />
<pre class="brush:perl">
class GogoXMarisaKirisima {
public:
int solve(vector <string>);
};
int mat[100][100];
vector <string> C;
int vis[100];
int mark[100];
int n;
int find( int nodo, int fin ){
if( vis[ nodo ] == 1 ) {return 0 ; }
vis[ nodo ] = 1;
if( nodo == fin ){ mark[ nodo ] = 1; return 1;}
for( int x = 0; x < n; x++)
if( C[ nodo ][ x ] == 'Y' ){
if( find( x , fin ) ) {
mat[nodo][x] = 1;
mark[ nodo ] = 1;
return 1;
}
}
return 0;
}
int F( int a, int level ){
if( vis[a] == 1) return 0;
if( level > 0 )vis[ a ] = 1;
if( level > 0 && mark[ a ] == 1 ) { mark[ a ] = 1; return 1; }
for( int x = 0; x < n; x++ ){
if(C[a][x] == 'Y' && mat[a][x] == 0 ){
int r = F( x, level + 1);
if( r > 0 ){
mark[ a ] = 1;
mat[a][x] = 1;
return r + 1;
}
}
}
return 0;
}
int GogoXMarisaKirisima::solve(vector <string> choices) {
int cont = 0;
C = choices;
n = choices.size();
memset( mat, 0, sizeof( mat ));
memset( vis, 0, sizeof( vis ));
memset( mark, 0,sizeof( mark ));
if( find( 0 , n - 1 ) == 0 ) return 0;
cont++;
int ban = 1;
for( ; ban == 1; ){
ban = 0;
for( int x = 0; x < n; x++)
for( int y = 0; y < n; y++){
if( C[x][y] == 'Y' && mat[x][y] == 0 ){
if( mark[ x ] == 1 && mark[ y ] == 1 ){
mat[x][y] = 1;
cont++;
ban = 1;
}
}
}
if( ban == 0 ){
for( int x = 0; x < n; x++){
if( mark[ x ] == 1 ) {
memset( vis, 0, sizeof( vis ));
if( F( x, 0 ) > 0 ){
ban = 1;
cont++;
break;
}
}
}
}
}
return cont;
}
//</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-22998213626592485062012-01-16T11:12:00.002-06:002012-01-16T11:12:19.358-06:00USACO 2012 January Contest, Bronze Division, Problem 3. Grazing Patterns<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3>
USACO 2012 January Contest, Bronze Division, Problem 3. Grazing Patterns </h3>
<br />
Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=105<br />
Despues de un rato de pensar como reducir el problema, ya que con programacion dinamica no se me ocurria como ( por que eran 2^25 estados en el peor de los casos ) , me di cuenta que no deberia haber muchas formas de que Bessie y Mildred pudieran comer todo el pasto, por tanto decidi hacer un bactracking.
<br />
Para este backtracking necesito leer el mapa que lo guardo en <b> mapa </b> , ya teniendo el mapa, en mi funcion para el backtraking llevo la posicion de Bessie y de Mildre su fila <b>row</b> y su columna <b>col</b> y el numero de pasto que aun no eh consumido, cada vez que entro a la funcion valido que no se allan salido del mapa , para esos son los if de la linea 17 y 18, despues valido que no que esas posiciones del mapa no allan sido visitadas antes por ninguna de las dos vacas, en la linea 19 se compara si la posicion de Bessie es la misma que la de Mildred y solo falta una celda de pasto <b>count = 1</b> entonces regreso que encontre una forma, en otro caso si llegaron a la misma posicion pero les falto alguna zona por comer, en la line 50 y 51 se asigna la direcion a Bessie y a Mildred respectivamente, y en la linea 52 se manda a llamar de nuevo la funcion <b>solve</b> pero con las nuevas posiciones de Bessie y de Mildred, se incrementan dependiendo de su dirección , con los arreglos <b> dx </b> y <b> dy </b> estos arreglos nos ayudan a reducir el codigo ya que tienen asignadas 1, 0 o -1 para indicar que se incrementa la posicion en 1 o se decrementa por 1, en la lina 47 y 48 se marca el mapa como visitado y en la linea 53 y 54 se desmarca ( como todo backtracking).
<br />
Aqui el codigo:
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problema: Grazing Patterns
*/
# include "stdio.h"
# include "string.h"
# define MAX 5
int mapa[ MAX + 1 ][ MAX + 1];
int dx[ 4 ] = { 0, 0, 1,-1};
int dy[ 4 ] = { 1,-1, 0, 0};
int solve( int BessieRow , int BessieCol, int MildredRow , int MildredCol , int count ){
int BessieDir , MildredDir;
int cont = 0;
if( BessieRow < 0 || BessieRow >= MAX || BessieCol < 0 || BessieCol >= MAX ) return 0;
if( MildredRow < 0 || MildredRow >= MAX || MildredCol < 0 || MildredCol >= MAX ) return 0;
if( mapa[ BessieRow ][ BessieCol ] == 1 || mapa[ MildredRow ][ MildredCol ] == 1) return 0;
if( BessieRow == MildredRow && BessieCol == MildredCol ) return count == 1 ? 1 : 0;
mapa[ BessieRow ][ BessieCol ] = 1;
mapa[ MildredRow ][ MildredCol ] = 1;
count -= 2;
for( BessieDir = 0; BessieDir < 4; BessieDir++ )
for( MildredDir = 0; MildredDir < 4; MildredDir++ )
cont += solve( BessieRow + dx[ BessieDir ], BessieCol + dy[ BessieDir ], MildredRow + dx[ MildredDir ], MildredCol + dy[ MildredDir ] , count );
mapa[ BessieRow ][ BessieCol ] = 0;
mapa[ MildredRow ][ MildredCol ] = 0;
return cont;
}
main(){
int m, x, count = MAX * MAX , a, b;
freopen("grazing.in", "r", stdin);
freopen("grazing.out", "w", stdout);
scanf("%d", &m);
for( x = 0; x < m; x++ ){
scanf("%d %d", &a, &b);
if( mapa[a - 1][b - 1] == 0 ) count--;
mapa[a - 1][b - 1] = 1;
}
printf("%d\n", solve( 0, 0, MAX - 1, MAX - 1, count ));
return 0;
}
</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-86850866290032325962012-01-16T10:52:00.002-06:002012-01-16T10:52:30.666-06:00USACO 2012 January Contest, Bronze Division, Problem 2. Haybale Stacking<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3> USACO 2012 January Contest, Bronze Division, Problem 2. Haybale Stacking </h3>
<br />
Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=104 <br />
Este problema no se puede resolver con fuerza bruta ya que N es de 1,000,000 de elementos, y K es de 25,000, entonces como puedo resolver este problema ? <br />
El problema pide que se de el tamaño de la pila de enmedio ( ya ordenadas todas ) , entonces hay que generar de alguna manera todas las pilas de forma lineal, y despues ordenarlas para sacar la de enmedio.
<br />
Si yo marco en un erreglo <b>insert</b> todas las posiciones en donde inicia un intervalo <br />
y en otro arreglo <b>delete</b> marco todas las posicones en donde termina un intervalo <br />
si hay mas de dos posiciones repetidas lo que se guardan en ambos arreglos es el numero de intervalos que se insertan y el numero de intervalos que terminan en esa posicion <br />
Con solo recorrer el arreglo de izquierda a derecha ( de 1 a N (en mi algoritmo de 0 a N - 1, ya que decremento a y b por 1) ) puedo asignarle a cada pila el numero de fardos de heno que deberia tener despues de asignar todas los fardos correspondientes, este valor lo guardamos en <b>count</b>, ya teniendo esta informacion solo se ordena y se imprime la posicion <b> n / 2 </b> </br> </br>
Aqui el codigo: <br />
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problema: Stacking
*/
# include "string.h"
# include "stdio.h"
int insert[1000001];
int delete[1000001];
int count[1000001];
int compare( int *a, int *b){ return *a - *b; }
main(){
int x, n, k, a, b, cont;
freopen("stacking.in", "r", stdin);
freopen("stacking.out", "w", stdout);
scanf("%d %d", &n, &k);
memset( insert, 0, sizeof( insert ));
memset( delete, 0, sizeof( delete ));
memset( count , 0, sizeof( count ));
for( x = 0; x < k ; x++){
scanf("%d %d", &a, &b);
insert[ a - 1 ]++;
delete[ b - 1 ]++;
}
cont = 0;
for( x = 0; x < n; x++){
cont += insert[ x ];
count[ x ] = cont;
cont -= delete[ x ];
}
qsort( count, x, sizeof( int ) , compare );
printf("%d\n", count[ n / 2 ]);
return 0;
}
</pre>
<br />
Cualquier duda o sugerencia pueden escribirme a rodrigo.burgos@gmail.com
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-61801926769810051902012-01-16T10:34:00.002-06:002012-01-16T10:35:59.917-06:00USACO 2012 January Contest, Bronze Division, Problem 1. Gifts<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3> USACO Computiong Olympiad , January 2012 Contest , Problem 1. Gifts </h3>
<br />
Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=103
<br />
Para resolverlo utilize una estructura COST ( P = price y S = shipping cost ) , como solo puedo reducir el precio de un solo elemento, lo que se me ocurrio fue hacer una fuerza bruta, por cada uno de los regalos dividirlo entre dos y luego ordenarlo , utilizo el arreglo copy para mi modificacion y ordenacion asi no pierdo mi configuracion orignal sin reduccion que lo tengo en el arreglo gifts. <br />
Para que ordeno? <br />
Si mis datos estan ordenamos la mejor forma de dar regalos es siempre comprando los de menor precio ( P + S ), y asi queda el algoritmo ( la complejidad el algoritmo es de N ^ 2 * log N ( ordenacion ( N log N ) por N iteraciones ) ):
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problema: Gift
*/
# include "stdio.h"
# include "string.h"
typedef struct { int P, S; } COST;
COST gifts[1002], copy[ 1002 ];
int max( int a, int b ){ return a > b ? a : b; }
int compare( COST *a, COST *b){
int ca = a->P + a->S, cb = b->P + b->S;
if( ca < cb) return -1;
if( ca > cb) return +1;
return 0;
}
main(){
int n, B, x, y, sol = 0, budget;
freopen("gifts.in","r", stdin);
freopen("gifts.out","w", stdout);
scanf("%d %d", &n, &B);
for( x = 0; x < n; x++) scanf("%d %d", &gifts[x].P, &gifts[x].S);
for( x = -1; x < n; x++){
for( y = 0; y < n; y++) copy[ y ] = gifts[ y ];
if( x >= 0 ){
copy[ x ].P /= 2;
qsort( copy , n, sizeof( COST ), compare);
budget = B;
for(y = 0; y < n; y++){
budget -= ( copy[y].P + copy[y].S);
if( budget < 0 ) break;
}
sol = max( sol, y );
}
}
printf("%d\n", sol);
return 0;
}
</pre>
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com2tag:blogger.com,1999:blog-7137669718769202647.post-54526646653415823832011-12-20T17:48:00.001-06:002011-12-21T22:27:54.563-06:00OMI 2011 Problema 3 ( La guardia negra)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="texp/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<h3> OMI 2011 Problema 3 ( La guardia negra) </h3>
<br />
Problema:
<br />
La guardia negra<br />Según la canción del fuego y el hielo, la guardia de los centinelas negros ha defendido al reino de Westeros de las amenazas del norte durante los últimos 8,000 años. A últimas fechas un gran número de huestes enemigas se ha venido concentrando en la frontera norte de Westeros. El comandante de la guardia, Lord Snow, ha mandado llamar por ti para que le ayudes a planear la defensa.<br />La guardia tiene representado el campamento enemigo como una cuadrícula de M filas por N columnas, en cada casilla de la cuadrícula hay un número si,j que representa la cantidad de soldados enemigos en esa casilla.<br />La guardia cuenta con una catapulta capaz de lanzar un proyectil explosivo a cualquier lugar de esta cuadrícula. Al explotar, el proyectil eliminará a todos los soldados enemigos que se encuentren a una distancia menor o igual a un número di que depende del proyectil en cuestión. La distancia entre dos casillas se define como la suma del valor absoluto de la diferencia de sus columnas mas el valor absoluto de la diferencia de sus filas.<br />El comandante de la guardia quiere que desarrolles un programa para calcular la cantidad de soldados que eliminaría un proyectil específico si fuera lanzado en una cierta casilla.<br />Problema<br />Escribe un programa que dada la cuadrícula del campamento, el número de soldados en cada casilla, el número de proyectiles, la distancia de alcance de cada uno y el lugar donde quieres lanzarlo, calcule el número de enemigos que serán eliminados con cada proyectil.<br />
Restricciones<br />1 <= M, N <= 1,000<br />1 <= P <= 100,000<br />0 <= si,j <= 1,000,000,000 0 <= di <= 500<br />Entrada<br />Filas y de columnas del campamento respectivamente. Número de proyectiles con los que cuenta la guardia. Número de soldados en la casilla (i,j).<br />Alcance del proyectil i.<br />Tu programa debe leer del teclado la siguiente información:<br />
En la primer línea los números M y N que representan el número de filas y columnas.<br />
En cada una de las siguientes M líneas hay N números enteros separados por un<br />espacio que representan los soldados en cada casilla del campamento.<br />
En la siguiente línea el número P de proyectiles que tiene la guardia.<br />
En las últimas P líneas hay 3 enteros separados por espacios en cada una que<br />representan la fila y columna donde se lanzará un proyectil y la distancia de alcance del mismo.<br />Tanto las filas como las columnas inician nuieradas a partir del 0 y hasta M-1 y N-1 respectivamente. La fila 0 es la fila superior y la columna 0 es la columna hasta la izquierda.<br />Puedes estar seguro de que los proyectiles serán lanzados de tal forma que su alcance no exceda el campamento, es decir, ninguna explosión llegará a una casilla que este fuera de la cuadrícula.<br />Salida<br />Tu programa deberá escribir a la pantalla P líneas con un número cada una. La i-eȁsima línea debe contener la cantidad de enemigos que serían eliminados al lanzar el proyectil i.
<br />
<h3> Solucion: </h3>
El problema de la guardia negra es un problema que parece complicado, pero habría que tomarnos un tiempo para analizarlo, realmente uno debe responder a los querys que se solicitan, en la posición pos_fila, pos_columna, con diámetro T contar cuantos soldados son eliminados, bueno podemos tratar de encontrar una solución dinámica que cuente todo pero es muy costoso, mejor vamos a hacerlo a fuerza bruta. Si escucharon bien a fuerza bruta, pero bueno no lo hagamos tan bruta, solo respondamos a lo que nos preguntan, primero tenemos que observar que para una posición fil, col, con un diámetro T, siempre vamos a contar los rangos de para cada columna de la celda [fila – t, col ] hasta [fila + t, col], sacamos toda la suma, y luego para la coluina de atrás [fila – t + 1, col - 1] hasta [ fila + t – 1 , col – 1] y asi sucesivamente, mi propuesta de solución es precacular estas sumas, si en un arreglo de suma, tenemos la suma desde la base de la matriz que es [ fila = n – 1, col = ? ] , hasta la fila 0 [ fila = 0 , col = ?] , entonces para calcular toda la suma del rango que necesitamos cacular nos tomara una operación por ejemplo si quiero la suma de la celda[ 10, 4] a la celda[ 1000, 4 ] ( observen que la columna siempre es la misma) basta con sacar del arreglo suma[ 10, 4] – suma[ 1000 + 1 , 4] , ya que suma[10, 4], tiene la suma de todos los suma[ 10 , 4] , suma[ 10 , 5] + suma[10, 6] …. , y le restamos las suma que son suma[ 1001, 4] + suma[ 1002, 4] + suma[ 1003, 4] …..
<br />
Ya tenemos la suma ahora solo hay que sacar las T*2 + 1 columnas, como solo son 100,000 preguntas y a lo mas T es 1000, tenemos que en el peor de los casos se harán 100,000,000 operaciones que corre en menos de 1 segundo.
<br />
Veamos la implementación:
<br />
<pre class="brush:perl">
/*
Autor: Rodrigo Burgos Dominguez
Problema: La guardia negra
*/
# include "stdio.h"
# include "string.h"
int cnt[1001][1001];
long long sum[1002][1002];
int n, m;
long long get( int x, int y ){
if( x < 0 || x >= n || y < 0 || y >= m ) return 0;
return sum[x][y];
}
long long suma( int px, int py, int t){
long long sum = 0;
int x, y, d;
for( x = py, d = 0; x >= 0 && x >= py - t ; x--, d++){
sum += get( px - ( t - d ), x ) - get( px + ( t - d ) + 1, x);
}
for( x = py + 1, d = 1 ; x < m && x <= py + t ; x++, d++){
sum += get( px - ( t - d ), x ) - get( px + ( t - d ) + 1, x);
}
return sum;
}
main(){
int x, y, q, nq, px, py, t;
scanf("%d %d", &n, &m);
for( x = 0; x < n; x++)
for( y = 0; y < m; y++) scanf("%d", &cnt[x][y]);
for( x = n - 1; x >= 0; x--){
for( y = 0; y < m; y++)
sum[ x ][ y ] = sum[x + 1][ y ] + cnt[x][y];
}
scanf("%d", &nq);
for( q = 0; q < nq; q++){
scanf("%d %d %d", &px, &py, &t);
printf("%lld\n", suma( px, py, t));
}
return 0;
}
</pre>
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-29976151963394626192011-12-20T17:25:00.000-06:002011-12-20T17:25:02.157-06:00OMI 2011 Problema 1 ( Dementores a la puarte )<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<b> Problema: </b>
<br />
<b>Dementores a la puerta</b><br />¡Los temidos dementores están a las puertas de Hogwarts! Como de costumbre, será tarea de los amigos Harry Potter y Ron Weasley alejarlos de ahí. Para alejarlos ambos saben invocar el hechizo patronus. Cuando un mago invoca un patronus los dementores se alejan en dirección contraria al mago lo más posible. Por ejemplo, si el mago está del lado oeste, los dementores se alejarán hacia el este hasta chocar con algún obstáculo o pared. Si está del lado norte, los dementores se alejarán hacia el sur.<br />El patio de Hogwarts se representa como un cuadrado de lado N, Harry y Ron están en el lado oeste y norte del patio. El patio tiene O obstáculos internos. Inicialmente toda la fila norte (la fila superior) y la columna oeste (la columna hasta la izquierda) están<br />llenas de dementores.<br />La primer figura muestra el patio de Hogwarts, Harry está del lado oeste y Ron del lado norte. Los puntos negros son las casillas en donde hay dementores (en una casilla pueden haber múltiples dementores). Los cuadros grises son obstáculos y los dementores no pueden pasar a través de ellos, sin embargo, los patronus si atraviesan los obstáculos.<br />Aquí se muestra cómo quedan los dementores si Harry o Ron invocan su patronus. La izquierda muestra el resultado de Harry y derecha el resultado de Ron.<br />El objetivo de Harry y de Ron es llevar a todos los<br />dementores a la esquina inferior derecha del patio.<br />Como no son buenos para calcular, te pidieron que les digas cuál es el número mínimo de patronus que deben invocar entre los dos (cada uno de ellos puede invocar varios) para lograrlo.<br />Problema<br />Escribe un programa que dados los obstáculos del patio determine el número mínimo de patronus que se requieren para llevar a los dementores a la esquina inferior derecha.<br />Restricciones<br />1 < N <= 1,000 Dimensiones del patio<br />0 <= O <= 1,000,000 Número de obstáculos en el patio<br />Entrada<br />Tu programa debe leer del teclado los siguientes datos:<br /> En la primera línea los números N y O, dimensiones del patio y número de obstáculos.<br /> En las siguientes O líneas habrá 2 números enteros separados por un espacio en cada<br />una que indican la columna y la fila de cada uno de los obstáculos respectivamente. La esquina superior izquierda se representa como la posición (0, 0).<br />Salida<br />Tu programa debe escribir a la pantalla un único número entero que indique la cantidad mínima de patronus necesarios para llevar a todos los dementores a la esquina inferior derecha.<br />Te aseguramos que para todos los casos de prueba es posible lograr el objetivo.<br />
<b> OMI 2011 Problema 1 ( Dementores a la puarte ) </b> <br /><br />
Para encontrar la solución a este problema hay que ir de lo generar a lo particuluar, como podemos ver
en el problema tenemos realmente n * 2 - 1 numero de dementores todos en la primera fila y primera columna
¿Por que digo que hay que ir de lo generar a lo particular?, bueno pues podemos pensar en resolver el problema
moviendo todos los dementores al mismo tiempo o bien mejor moverlos uno por uno, primero pensemos cual es la <br />
mejor manera de llevar a un dementor de su posición a la esquina inferior derecha, bueno si Harry lanza su patronus
todos se mueven a la derecha, si Harry volviera a lanzar su patronus entonces no se movería ningún dementor, por lo tanto
el siguiente movimiento siempre debe hacerlo Ron, y podemos ver pasa exactamente lo mismo si Ron lanza su patronus
Harry debe ser el siguiente, entonces solo hay dos posibles solución que Ron lance su patronus primero o que Harry lo lance primero
Ya con este primer paso podemos ver que solo hay que calcular el máximo tiempo que tarda cada dementor en llegar a su destino iniciando
Harry primero y ver si es mejor que empezando con Ron <br /> <br />
Ahora para cada dementor que este en la primera fila o primera columna, el mínimo para llegar a su destino, es saber si se moverá hacia abajo
o hacia la derecha, si sabemos eso, entonces el siguiente paso será el movimiento diferente. <br />
Para resolver esto utilizaremos programación dinámica en din[ direccion ][ posicionfila ][ posicioncol ], pero para hacer el movimiento mas rápido
ya que si nos movemos hacia abajo tendríamos que movernos hasta llegar a un obstaculo o llegar al borde, primero pre calculamos la siguiente
posición que nos corresponde si vamos hacia abajo, y para usamos el arreglo next[ direccion ][ posicionfila ][ posicioncol ] , que nos indica
que si vamos hacia abajo en la posición fila , col next[ abajo = 0 ][ posicionfila ][ posicioncol ], nos indica la fila en la que acabaríamos
y si pones next[ derecha = 1 ][ posicionfila ][ posicioncol ] nos indicaría la columna. <br /> < br />
Veamos el código:
<pre class="brush:perl">
/* Autor : Rodrigo Burgos
Problema: Dementores a la puerta */
# include "string.h"
# include "stdio.h"
int mapa[1002][1002], n;
int next[2][1000][1001];
int din[2][1002][1002];
int min( int a, int b ){ return a < b ? a : b; }
int max( int a, int b ){ return a > b ? a : b; }
/* calculamos el minimo numero de movimientos para llegar a la esquina
inferior derecha, desde la posicion a, b con direccion dir (0 : abajo, 1 : derecha) */
int solve(int dir, int a, int b ){
int res;
if( a == n - 1 && b == n - 1) return 0; /* Ya llege a mi destino */
if( din[dir][a][b] != - 1) return din[dir][a][b];
if( dir == 0 ){
res = solve( (dir + 1) % 2 , next[dir][a][b], b ) + 1;
}else{
res = solve( (dir + 1) % 2 , a, next[dir][a][b]) + 1;
}
return din[dir][a][b] = res;
}
main(){
int obs, a, b, x, y, dir;
int sol, res;
scanf("%d %d", &n, &obs);
for( x = 0; x < obs; x++){
scanf("%d %d", &a, &b);
mapa[ b ][ a ] = 1;
}
/* Todas las posiciones siguientes les asignamos como vacias*/
memset( next, -1, sizeof( next ));
/* Calculamos las posiciones siguientes de cada una de las
cordenadas, si van hacia abajo hasta donde llegan , si van a la
derecha hasta donde llegan, dir = 0 ( abajo ) , dir = 1 ( derecha) */
for( dir = 0; dir < 2; dir++){
for( x = n - 1; x >= 0 ; x-- )
for( y = n - 1; y >= 0 ; y-- ){
if( dir == 0 ){ /* hacia abajo */
if( mapa[x][y] == 0 ){ /* si no hay obstaculo */
next[ dir ][ x ][ y ] = ( next[ dir ][ x + 1][ y ] == -1 ? x : next[ dir ][ x + 1 ][ y ] );
}
}else{ /* hacha la derecha */
if( mapa[x][y] == 0 ){ /* si no hay obstaculo */
next[ dir ][ x ][ y ] = ( next[ dir ][ x ][ y + 1 ] == -1 ? y : next[ dir ][ x ][ y + 1 ] );
}
}
}
}
sol = (1<<29);
memset( din , -1, sizeof( din ));
for( dir = 0; dir < 2; dir++){
res = 0;
for( x = 0; x < n; x++){
res = max( res, solve(dir, 0, x ));
res = max( res, solve(dir, x, 0 ));
}
sol = min( sol, res );
}
printf("%d\n", sol);
return 0;
}
</pre>
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-33229751755974881712011-12-16T10:54:00.000-06:002011-12-16T16:53:08.056-06:00Ball Stacking ( Latino America 2011 ACM)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
<br />
<h2><a href="http://uva.onlinejudge.org/external/123/12357.html" target="_blank">Ball Stacking</a><br /> </h2>
<br />
<br />
<h3> Introduccion </h3>
<br />
Este problema solo lo pudo resolver un equipo en la region de mexico.
<br />
El problema practicamente consiste en dado una piramide de numeros , uno puede escojer cualquiera de los numeros, pero cuando uno escoje alguno simpre debe escojer los dos que se encuentran arriba de el , para el caso de los elementos que se encuentran en las orillas, por ejemplo todos los que estan en la columna 0 solo tienen un numero superior y no dos.
<br />
Tu tarea es de que manera escojerias los numeros ( con la restriccion antes mencionada de que debes tomar los dos numero arriba de el, y si tomas estos numero los dos de arriba y asi sucesivamente) de tal forma que maximises la suma de los numero repetidos.
<br />
<h3> Solucion Lenta </h3>
<br />
Lo primero que se nos viene a la cabeza es que es Programacion Dinamica, pero como logro que se pueda hacer esta programacion dinamica, bueno para todo problema lo primero hay que hacer es dibujarlo y ver su forma, lo primero que ami se me ocurrio ( que si hubiera estado en el concurso eso me hubiera hecho perder como una hora del cocurso), es que note que que se forman triangulos, y para evitar recontar los triangulos de abajo, yo manejo la fila y el rango que puedo formar hacia abajo, (ROW, A, B) donde A B, es la base del triangulo que que esta libre, si empiezo de arriba hacia abajo, cuando uno selecciona una posicion C de este rango, nuevamente puedo formar dos triangos que no han sido selecionados (ROW, A, C - 1) y (ROW, C + 1, A ) , entonces si recorro esta C y guardo el mejor resultado para todas las C aue esten en el rango [ A, B], entonces puedo obtener la mejor forma de selecionar numeros culla base es la fila ROW en el rango A, B
<br />
La complejidad de este algoritmo es O( N x N x N x N ) que es aproximadamnte 10^12, lo cual no sale a tiempo, lo implemente y perdi mas de una hora por suponer que ya implementado veria alguna manera de reducirlo, a aqui el codigo:
<pre class="brush:perl">
/*Autor: Rodrigo Burgos Dominguez */
# include <stdio.h>
# include <string.h>
long long balls[1002][2002];
long long din[2][1002][2002];
long long scanning[1002][2002];
int n;
long long max(long long a, long long b ){ return a > b ? a : b; }
long long procesa( int row, int a, int b, int c ){
long long res = scanning[ row ][ c ];
int lrow, lcol, rrow, rcol, irow, icol;
lrow = row - ( c - a + 1) ;
lcol = a - 1;
rrow = row - ( b - c + 1);
rcol = c;
irow = row - (b - a) - 2;
icol = a - 1;
if( lrow >= 0 && lcol >= 0 ) res -= scanning[ lrow ][ lcol ];
if( rrow >= 0 && rcol >= 0 ) res -= scanning[ rrow ][ rcol ];
if( irow >= 0 && icol >= 0 ) res += scanning[ irow ][ icol ];
return res;
}
main(){
int currentRow, column, row, a, b, c;
while( scanf("%d", &n) != EOF && n ){
for( row = 0; row < n; row++)
for( column = 0; column <= row; column++) scanf("%lld", &balls[ row ][ column ]);
memset( din, 0, sizeof( din ));
memset( scanning, 0, sizeof( scanning ) );
for( row = 0; row < n; row++)
for( column = 0; column <= row; column++ ){
scanning[ row ][ column ] = balls[ row ][ column ];
if( row > 0 ){
scanning[ row ][ column ] += scanning[ row - 1 ][ column ];
if(column > 0 )
scanning[ row ][ column ] += scanning[ row - 1 ][ column - 1];
if( row > 1 && column > 0 ){
scanning[ row ][ column ] -= scanning[ row - 2 ][ column - 1];
}
}
}
din[ 0 ][ 0 ][ 0 ] = max( (long long)0 , (long long)balls[ 0 ][ 0 ] );
for( row = 1; row < n; row++){
currentRow = ( row % 2 );
memset( din[ currentRow ], 0, sizeof( din[ currentRow ] ) );
for( a = row; a >= 0 ; a--){
for( b = a; b <= row; b++){
if( b > 0 ) din[currentRow][a][b] = max( 0 , din[ (currentRow + 1) % 2][ a ][ b - 1] ) ;
for( c = a; c <= b; c++){
din[currentRow][a][ b ] = max( din[currentRow][a][ b ] ,
( ( c > 0 ) ? din[ currentRow ][a][ c - 1 ] : 0 ) + din[currentRow % 2][c + 1][ b ] + procesa( row, a, b, c ));
}
}
}
}
printf("%lld\n",din[(n - 1) % 2 ][ 0 ][ ( n - 1 ) ]);
}
return 0;
}
</pre>
<br />
<h3> Solucion Correcta ( no necesariamente unica ni la mejor) </h3>
<br />
<br />
Si me hubiera puesto a analizar que otros patrones encontraba, hubiera notado algo que me podria haber ayudado muchisimo para resolver el problema, si nosotro no dibujamos el triangulo si no que vamos haciendo los ejemplos con la entrada tal y como nos las dan, cada triangulo que formamos , se puede ver como una linea vertical que va desde el pico de la piramide ( ROW , COL ) y baja por toda esa columna hasta ROW = 0, para la columna anterior siempre es (ROW - 1 , COL - 1), bueno asi se va formando, de ahi viene la idea, que para que yo pueda forma una piramide cuyo pico es (ROW , COL ), entonces en la columna anterior por lo menos debo tener una piramide que tenga como pico ( ROW - 1, COL - 1), si yo tuviera una piramida en la columna anterior con pico mayor a ROW - 1, entonces quiere decir que esa piramide es mayor a la que estoy colocando en este momento, la idea es que la mejor forma de construir una piramide en con pico ( ROW , COL ) es igual a la suma de toda la columna desde ROW hasta 0 mas (+) el pico de mayor suma que se pudo generar en la columan anteriro que sea mayor a ( ROW - 1, COL - 1), si eso lo hacemos para todas las filas y columnas obtendremos el resolutado.
<br />
<br />
La complejidad del algoritmo hasta este punto es de O( N x N x N ) que ya es mucho menor 10^9, pero aun asi es costoso, si nosotros implementamos un interval tree o una tecnica para poder obtener el mejor valor de la columna anterior mayor a ( ROW - 1, COL - 1) en un tiempo log2 N, entonces la complejidad seria de O( N x N x LOG2 N ) , que seria aproximadamento 10^7 en el caso mas grande.
<br />
<br />
Eh aqui una implementacion
<br />
<br /><br />
<pre class="brush:perl">
/* Autor: Rodrigo Burgos Dominguez */
#include "stdio.h"
#include "string.h"
#define INFINITY (((long long)1)<<50)
typedef struct { int izq, der; long long maximo; } INTERVAL;
INTERVAL MEM[ 1000000 ];
int nmem;
long long best[ 1002 ], tmpbest[ 1002];
long long balls[ 1002 ][ 1002 ];
long long max( long long a , long long b ){ return a > b ? a : b; }
/*Crea un interval tree basado en lo que hay en el arreglo best*/
long long makeInterval( int *pt, int a, int b){
int med;
if( a > b ) return -INFINITY;
if( *pt == -1 ){
*pt = nmem++;
MEM[*pt].izq = -1;
MEM[*pt].der = -1;
MEM[*pt].maximo = 0;
}
if( a == b ){
return MEM[*pt].maximo = best[ a ];
}
med = (a + b) / 2;
MEM[*pt].maximo = max( makeInterval( &MEM[*pt].izq, a, med ) , makeInterval( &MEM[*pt].der, med + 1, b ));
return MEM[*pt].maximo;
}
/* del intreval tree creado se consulta el rango A, B, y se obtiene el elemento mas grande*/
long long getMax(int pt, int a, int b, int A, int B){
int med = ( a + b ) / 2;
if( pt == -1 || B < a || A > b ) return -INFINITY;
if( A <= a && B >= b ) return MEM[pt].maximo;
return max( getMax( MEM[pt].izq, a, med, A, B) , getMax(MEM[pt].der, med + 1, b, A, B ) );
}
main(){
int row, col, n, indice;
long long sum, sol;
while( scanf("%d", &n) != EOF && n ){
for( row = 0; row < n; row++){
for( col = 0; col <= row; col++){
scanf("%lld", &balls[ row ][ col ]);
}
}
/* best contiene la mejor mander de ralizar la operacion en la correspondiente columna,
y la posicion de best[ row ]*/
best[ 0 ] = 0;
sol = 0;
for( row = 0; row < n; row++){
best[ row + 1 ] = balls[ row ][ 0 ] + best[ row ];
sol = max( sol, best[ row + 1]);
}
for( col = 1; col < n; col++){
sum =0;
nmem = 0;
indice = -1,
makeInterval( &indice, col - 1, n);
for( row = col; row <= n ;row++){
tmpbest[ row ] = sum + getMax(indice, col - 1, n , row - 1 , n );
sol = max( sol, tmpbest[ row ]);
sum += balls[ row ][ col ];
}
for( row = col; row <= n ; row++) best[ row ] = tmpbest[ row ];
}
printf("%lld\n", sol);
}
return 0;
}
</pre>
<br />
<h3> Una mejor solucion </h3>
<br />
Esta solucion es practicamente la misma que la de arriba, pero de igual manera por programar rapido y resolver que la mejor manera de sacar el mejor valor de un arreglo es con un interval tree, no considere que es estatico este arreglo y con un simple barrido del arreglo puedo saber cual es el mayor eh aqui el codigo, con complejidad O( N x N )
<pre class="brush:perl">
#include <stdio.h>
#include <string.h>
#define INFINITY (((long long)1)<<50)
typedef struct { int izq, der; long long maximo; } INTERVAL;
INTERVAL MEM[ 1000000 ];
int nmem;
long long best[ 1002 ], tmpbest[ 1002];
long long balls[ 1002 ][ 1002 ];
long long max( long long a , long long b ){ return a > b ? a : b; }
main(){
int row, col, n;
long long sum, sol;
while( scanf("%d", &n) != EOF && n ){
for( row = 0; row < n; row++){
for( col = 0; col <= row; col++){
scanf("%lld", &balls[ row ][ col ]);
}
}
/* best contiene la mejor mander de ralizar la operacion en la correspondiente columna,
y la posicion de best[ row ]*/
best[ 0 ] = 0;
sol = 0;
for( row = 0; row < n; row++){
best[ row + 1 ] = balls[ row ][ 0 ] + best[ row ];
sol = max( sol, best[ row + 1]);
}
for( col = 1; col < n; col++){
sum =0;
nmem = 0;
for( row = n - 1; row >= 0 ; row--){
best[ row ] = max(best[ row ], best[ row + 1]);
}
for( row = col; row <= n ;row++){
tmpbest[ row ] = sum + best[ row - 1 ];
sol = max( sol, tmpbest[ row ]);
sum += balls[ row ][ col ];
}
for( row = col; row <= n ; row++) best[ row ] = tmpbest[ row ];
}
printf("%lld\n", sol);
}
return 0;
}
</pre>
<h3> Conclusion </h3>
<br />
Para los concursos de programacion uno debe analizar, la mayoria de los problemas se puede resolver sencillamente, el truco es buscar la idea correcta, tomense su tiempo para encontrar la idea correcta y no implemntar cosas que puedan harcerlos perder el tiempo.
<br />
<br />
<br />
Saludos
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-46946741023433982472011-12-14T23:58:00.002-06:002011-12-15T00:41:15.651-06:00Interesting Sequences ( Programacion Dinamica y Barrido)<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css" rel="stylesheet" type="text/css"></link>
<link href="http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDafault.css" rel="stylesheet" type="text/css"></link>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js" type="text/javascript">
</script>
<script src="http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js" type="text/javascript">
</script>
<script language="javascript">
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<br />
<a href="http://uva.onlinejudge.org/external/123/12385.html" target="_blank">http://uva.onlinejudge.org/external/123/12385.html</a><br />
<br />
<br />
Este problema se trata de dada una secuencia, encontrar una subsecuencia interesante, una subsecuencia interesante es una subsecuencia donde el primer elemento es igual al ultimo, y tu tarea es encontrar el maximo numero de subsecuencias de este tipo de tal manera que no se intersecten una con otra.
<br />
<br /><br />
<pre class="brush:perl">
/* Autor: Rodrigo Burgos Dominguez */
#include "stdio.h"
#include "string.h"
#define MAXELEMENT 100000
int list[MAXELEMENT + 1];
int next[MAXELEMENT + 1];
int scanning[MAXELEMENT + 1];
int dp[ MAXELEMENT + 1];
int max( int a, int b){ return a > b ? a : b; }
main(){
int cases, ncases, n, x;
for( scanf("%d", &ncases), cases = 1; cases <= ncases ; cases++ ){
scanf("%d", &n);
for( x = 0; x < n; x++) scanf("%d", &list[ x ]);
/* se inicializa el barrido, para indicar que ningun elemento del mismo tipo a sido encontrado */
memset( scanning, -1, sizeof( scanning ));
for( x = n - 1; x >= 0 ; x--){
/* Se calcula el siguiente elemento igual a list[x] que encontro en el barrido ( scanning) */
next[ x ] = scanning[ list[ x ] ];
/* Se incerta al barrido que el elemento list[x] se encontro en la posicion x */
scanning[ list[x] ] = x;
}
memset( dp, 0, sizeof( dp ));
for( x = 0; x < n; x++){
/* Si en la posicion x existe algun elemento igual a el pero despues de el, se puede incrementar
el numero de subsecuencias */
if( next[x] != -1) dp[ next[x] ] = max( dp[ next[ x ]] , dp[ x ] + 1 );
/* En dado caso de no encontrar ningua se asigna a la siguiente posicion el mejor valor obtenido*/
dp[ x + 1] = max( dp[ x + 1], dp[ x ] );
}
printf("%d\n", dp[ n ]);
}
return 0;
}
</pre>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0tag:blogger.com,1999:blog-7137669718769202647.post-81607288226057230862011-12-14T23:14:00.001-06:002011-12-15T00:43:01.592-06:00Distributing Ballot Box ( Busqueda binaria)<link href='http://alexgorbatchev.com/pub/sh/2.1.364/styles/shCore.css' rel='stylesheet' type='text/css'/>
<link href='http://alexgorbatchev.com/pub/sh/2.1.364/styles/shThemeDefault.css' rel='stylesheet' type='text/css'/>
<script src='http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shCore.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushPerl.js' type='text/javascript'></script>
<script src='http://alexgorbatchev.com/pub/sh/2.1.364/scripts/shBrushXml.js' type='text/javascript'></script>
<script language='javascript'>
SyntaxHighlighter.config.bloggerMode = true;
SyntaxHighlighter.config.clipboardSwf = 'http://alexgorbatchev.com/pub/sh/2.1.364/scripts/clipboard.swf'
SyntaxHighlighter.all();
</script>
<body>
Este problema lo pueden encontrar en este liga: <a href="http://uva.onlinejudge.org/external/123/12390.html">http://uva.onlinejudge.org/external/123/12390.html</a><br />
Al leerlo practicamente podemos suponer que se puede hacer con un interval tree, sacando glotonamente el mayor eh incrementarla el numero de cajas asignadas a esta ciuda`, pero cuando nos sentamos a analizar un poco mas, descubrimos que es mas sencillo utilizar una tecnica de busqueda binaria: <a href="http://algorithmmx.blogspot.com/2011/11/algoritmo-de-busqueda-binaria.html" target="_blank">Busqueda Binaria</a><br />
<br />
Pero como podemos saber que se puede resolver un problema con esta tecnica? bueno el objetivo del problema es Dado un numero de ciudades y el numero de votantes que se encuentra en ella , distribuir las casillas de vopacion de tal manera que si se distribullen los votantes de la mejor manera, el maximo numero de votantes en cualquier casilla sea el minimo posible ( minimizar el maximo de votantes por casilla).<br />
<br />
Para verlo como un problema de busqueda binaria y como se plantea en el post de busqueda binaria debe ser creciente o decreciente, aqui en este caso , si nosotros ponemos un limite de votantes ( en otras palabras , ninguna casilla debe tener mas de este numero de votantes) y distribuimos las casillas de tal manera que forcemos a que se cumpla este limite , si el limite se puede conseguir , podemos buscar un limite inferior, pero si no, tendremos que encontrar un limite mas grande.
<br />
Usando la busqueda binaria se puede hacer en log2 de 2000000 que son aproximadamenste como 22 operaciones, lo costoso es validar que el liminte se pueda alcansar o no , para esto solo hay que asignar las casillas, veamos como queda el codigo:<br />
<br />
<br />
<pre class=”brush:perl”>
/* Autor: Rodrigo Burgos Dominguez */
#include "stdio.h"
#include "string.h"
#define MAXCITIES 500000
#define MAXPOPULATION 2000000
int numcities, numboxes;
int population[MAXCITIES + 1];
/* Este metodo solo regresa uno (1) si se puede obtener vopos menores o iguales al limite establesido (limit)
cero (0) en otro caso */
int isPossible( int limit, int remainboxes ){
int x, denominador;
for( x = 0; x < numcities; x++){
/* ya que desde al inicio se eliminaron el numero de cajas necesarias
( el numero de ciudades) solo nos queda el remanente este remanente debemos
distribuirlo, de tal manera que logremos bajar la cantidad de votantes sobre
una misma casilla, iniciamos con un denominador en 1 ( ya que ya tenemos un caja apartada
para cada ciudad, solo vamos incrementando las cajas para
reducir el numero de votantes , hasta que sea menor o igual a nuestro limite */
for( denominador = 1 ;
population[x] / denominador + ( (population[x] % denominador) > 0 ? 1 : 0 ) > limit;
denominador++);
remainboxes -= ( denominador - 1 );
if( remainboxes < 0) return 0;
}
return 1;
}
main(){
int x, remainboxes, izq, der, sol, med;
while( scanf("%d %d", &numcities, &numboxes) != EOF && ( numcitias != -1 || numboxes != -1 ) ){
for( x = 0; x < numcities ; x++) scanf("%d", &population[ x ]);
remainboxes = numboxes - numcities;
sol = 500000;
/*Busqueda Binaria */
for( izq = 0, der = MAXPOPULATION + 1; izq <= der ; ){
med = (izq + der) / 2;
if( isPossible( med, remainboxes ) ){
sol = med;
der = med - 1;
}else izq = med + 1;
}
printf("%d\n", sol);
}
return 0;
}
</pre>
<br />
<br />
<br />
<br />
<br />
<br />
<br />
</body>Anonymoushttp://www.blogger.com/profile/07423937812554531489noreply@blogger.com0