Mensajes

Mi primera propuesta antes de ser moderador , es dividir la criptografia.

Mi recomendacion seria:

1. Criptografia simetrica (AES, DES, algoritmos de permutaciones f_k(g_k(x)) = x, redes feistel, SBOXES, MD5,SHA1,TIGER etc..)
2. Criptografia asimetrica (Diffie-hellman, curvas elipticas, RSA , elgamal, Zero-Knowledge Proofs , XTR, MOV, DSA)
3. Criptografia teorica (Matematicas detras de AES, teoria de grupos , campos finitos, problema de logaritmo discreto , algoritmos para aritmetica sobre variedades jacobianas, teoria de nudos, toro complejo, curvas hiperelipticas, problema de logaritmo discreto, pollard-rho, number field sieve, karatsuba, ataques diferenciales, random number generators, factorizacion en primos,  etc...)

Si miras el número de mensajes que se van publicando puedes ver claramente que es un foro con muy poca actividad, no le veo necesidad de dividirlo, por mucho que haya diferentes ramas dentro de la criptografía, sin entrar ya en criptoanálisis.

Además, para tratar en detalle muchos de los temas de los que hablas se requiere una fuerte base matemática, más de la que se obtiene en cualquier ingeniería, es decir, la que correspondería a una licenciatura en matemáticas.

Un saludo de ghastlyX

Del tema ya se ha dicho todo lo que se tenía que decir, ambos administradores se han pronunciado. Me gustaría que que todos los que han escrito aquí o en el otro foro para criticar, insultar o difamar (porque la realidad es que en ambos sitios ha habido usuarios de ambos foros que lo han hecho) pararan de una vez y recapacitaran un poco, no van a ganar nada por insultar a otros.

Es tan fácil como respetarse los de un foro al otro y si alguien no es capaz, que nos/los ignore. No pienso cerrar el tema por el momento, espero que la gente sea lo suficientemente madura como para saber que seguir igual no sirve de nada.

Un saludo de ghastlyX

Esto suele resolverse con un BFS o DFS. Tu tienes en una matriz de enteros donde el valor de la posicion matriz[ i][j] corresponde al píxel que ocupa dicha posición. Llamas a la función indicando la posición del píxel inicio, la matriz y el nuevo color. Una vez en la función, la mecánica es guardarse el color antiguo del píxel, cambiarlo y luego comprobar los vecinos, ya sea recursivamente (DFS, tipo lo que has hecho) o iterativamente mediante una cola (BFS). Por ejemplo, este problema de la UVa se resuelve así:
http://icpcres.ecs.baylor.edu/onlinejudge/external/5/572.html

Un saludo de ghastlyX

Pues no te sé decir si por Floyd-Warshall funcionaría, pero si no me equivoco creo que mediante ese algoritmo tienes complejidad cúbica, tal y como he explicado sólo cuadrática. Olvida algoritmos de búsquedas de caminos en grafos para este problema. De hecho, olvida los grafos para este problema, se puede resolver sin haber visto un grafo en la vida.

Un saludo de ghastlyX

¿Matriz de adyacencia? No es de grafos el problema, es de DP y se resuelve como expliqué en el post anterior, supongo que pensarías en BFS o Dijkstra, pero va de dinámica.

Un saludo de ghastlyX

Pues ante la ausencia de respuestas, aclaro como se hace el de las minas. Recursivamente sería empezar en cada una de las casillas de la primera fila e ir probando cada camino desde ahí. Esto es terriblemente lento además de que probamos más de una vez el mismo camino. La solución es por DP.

Creamos una matriz de carácteres para guardar el mapa y otra del mismo tamaño para almacenar números. Entonces simplemente hay que recorrer dicha matriz: si en la posición hay una mina el número lo ponemos a un máximo declarado antes, de lo contrario será el mínimo entre el de arriba y las dos diagonales de arriba + 1. No hace falta decir que la primera fila ha de valer cero en todas las casillas excepto las que tengan minas. La solución final es el mínimo de todas las posiciones de la última fila.

No pondré más problemas, puesto que no tengo demasiado tiempo y casi nadie se pasa por aquí a resolverlos

Un saludo de ghastlyX

Supongo que estará bien, Pascal no sé, por los comentarios que pones parece que está bien, pero no te lo puedo asegurar. He hecho en cinco minutillos una solución en C++ con comentarios en cada línea, así podrás ver si es lo mismo:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

//Definimos los colores como constantes
const int VERDE = 0;
const int AMARILLO = 1;

bool dfs(vector<vector<int> >& grafo, int nodo, int color, vector<int>& color_nodo)
{
     bool flag = true;  //Declaramos el flag como true
     for(int i = 0; i < grafo[nodo].size(); i++)  //Mientras nuestro nodo tenga conexiones...
     {
             if(color_nodo[grafo[nodo][i]] == - 1) //Si el nodo al que está conectado no está pintado...
             {
                color_nodo[grafo[nodo][i]] = not color;  //Le ponemos el color contrario
                flag = dfs(grafo, grafo[nodo][i], not color, color_nodo);  //flag recibe el valor del DFS en dicho nodo
             }
             else if(color_nodo[grafo[nodo][i]] == color) return false;  //Si tiene el mismo color, es imposible el bicolouring, devolvemos false
     }
     return flag;  //Si no se ha salido antes, devuelve flag.
}             
     
int main()
{
    int q; //Número de casos
    cin >> q; //Recogemos los casos
    while(q--) //Mientras siga habiendo casos...
    {
            int n, p; //Nodos y conexiones respectivamente
            cin >> n >> p; //Recogemos ambos valores
            vector<int> color_nodo(n, -1); //Declaramos un arreglo de tamaño n para guardar el color de cada nodo
            vector<vector<int> > grafo(n); //Declaramos una matriz especificando solamente una dimensión
            while(p--) //Mientras haya conexiones por recoger...
            {
                 int origen, destino;   
                 cin >> origen >> destino;  //Recogemos los nodos de origen y destino
//Ambos nodos están conectados, por lo que hay que poner la conexión hacia ambos lados
//La matriz grafo indicará las conexiones: grafo[i].size() será la el número de conexiones donde cada j de grafo[i][j] es el nodo al que se conecta
                 grafo[origen].push_back(destino);  //Añadimos el nodo al que se conecta, en ambos sentidos
                 grafo[destino].push_back(origen);
            }
            color_nodo[0] = VERDE;  //Al primer nodo le asignamos color verde (puede ser al revés, es un simple número)
            if(dfs(grafo, 0, VERDE, color_nodo)) cout << "Miguel, a pintar" << endl;  //Hacemos DFS y según qué devuelva mostramos una salida u otra
            else cout << "No pierdas el tiempo" << endl;
    }
}

Venga, que seguro que más gente aparte de GroK sabe programar. Quiero una solución para el de las minas

Un saludo de ghastlyX

OK, me esperaré un poco más y mientras si eso quizá ponga alguno nuevo más. Por ahora hay tres: uno directo, otro DP y otro de grafos.

Un saludo de ghastlyX

PD: Hay que ver, que a muchos los sacan de APIs, hooks y ese tipo de programación y se pierden xDD

Bueno, voy a poner uno nuevo, esta vez de grafos, lo dejo adjunto. A ver si alguien da ya una solución para el de las minas, para el que no se haya dado cuenta con las pistas o no conozca ese tipo de problemas, es de programación dinámica. Si nadie publica nada tendré que dar yo la solución

Un saludo de ghastlyX

Son correctas ambas, me ha gustado la segunda, es una forma original de resolverlo, más de tipo matemática que no directa. Eso sí, como ya he dicho, no hay que pedir la entrada con lo de "Introduce los metros de la pared", simplemente recoged los datos, al estilo de UVa, USACO, OIE, IOI, ACM, Topcoder, etc. Poniendo eso en los concursos os daría error, puesto que la salida que produce tiene que ser idéntica a los ejemplos, y en ellos no aparecen peticiones de entrada de datos. Bueno, ya que el de los triángulos está resuelto, intentad el de las minas, que es algo más complejo.

Se podría hacer recursivamente, mirando TODOS los caminos desde cada parcela, pero es brutalmente lento, una solución recursiva no será considerada correcta. En mi primer post di una gran pista de cómo resolverlo, la repetiré: buscad una solución más dinámica!

Un saludo de ghastlyX