Mensajes

Si bien puedes utilizar estrategias tipo Trie, para el problema que planteas la manera más sencilla es la que te han comentado, leer primero todo el diccionario de palabras en el que buscas, ordenarlo y por cada palabra que busques hacer una búsqueda binaria. A la hora de implementarlo, lo más sencillo es que metas dichas palabras en un set de C++ y utilices la función count o find para saber si están o no.

Si optaras por utilizar estructuras tipo Trie, lo más eficiente sería utilizar o bien una estrategia de preprocesado del texto vía Suffix Tree (muy difícil de implementar siendo eficiente) o bien preprocesar los patrones a buscar vía Aho-Corasick (algo menos difícil que un Suffix Tree a mi opinión, pero también muy difícil). Sinceramente el tiempo de ejecución que vas a ganar con estas opciones para un diccionario de 70000 palabras es bastante despreciable, así que yo optaría por la binaria, que con un set son 5 líneas.

Sí que puedes. Simplemente tendrías que poner un sólo valor por dirección, que sería el incremento inicial. Entonces desde el código, habría que mantener la suma acumulada en lugar de sumar directamente el valor como hago yo. Las dos maneras son igual de buenas y en un concurso yo haría esta opción, ya que no depende de la longitud de la string y el array es menos engorroso de crear. Hice la otra en aquel momento porque pensé que se entendería mejor el código.

La verdad, no entiendo tu pregunta. No sé a qué te refieres con poner números del -1 al 1 en las celdas.

Primero de todo, lo siento. Todo este tema ha sido porque mi código (precioso, por cierto xDD) no se ha entendido.

A ver, no es que el problema se tenga que hacer con matrices de direcciones, si lo haces BIEN con ifos te entrará, el problema es que el código a base de ifos es generalmente horrible, largo y casi siempre sale un bug.

El código mío en sí es muy simple, sólo que si nunca has visto la idea se hace rara. Hay 8 direcciones posibles para que una palabra aparezca, así que para cada dirección, me creo dos arrays de tamaño 3 con los incrementos de fila y de columna asociados a cada posición en dicha dirección. Para simplificar el código, estos arrays los meto en dos arrays, uno para la fila o y otro para las columnas. De esta manera puedo iterar de manera genérica sobre todas las direcciones con un simple for.

Sé que en el foro los concursos de programación algorítmica y los jueces online son en general bastante odiados, pero he de romper una lanza en su favor xDD. Primero decir que aunque un programa que enviéis de Wrong Answer y a vosotros os vaya bien con los ejemplos que probáis, el error va a ser vuestro, no del juez. Aparte de los casos públicos que se dan en los problemas, los jueces utilizan múltiples casos de prueba privados, buscados especialmente para cazar los errores que el código pueda tener.

Y además de ser divertidos, en estos concursos y jueces se aprende mucho: primero algoritmia y segundo a pensar de manera totalmente abstracta, cosa muy útil para resolver otros tipos de problemas. Además, si se os da bien y se obtienen buenos resultados en concursos, las empresas grandes suelen envíar ofertas de trabajo y cuando digo grandes me refiero a tales como Google o Facebook.

Bueno, con la entrada 110, el programa sin la variable auxiliar no es que pete, simplemente no cambia el valor del primer elemento del vector.

Yo tampoco tengo ni la menor idea de por qué pasa esto, más cuando un amigo me comentó que con Dev-C++ los dos códigos dan el mismo valor.

[110]

Hola a todos,

El otro día estaba programando un cierto código con árboles y cuando compilaba el programa se comportaba de forma que no conseguía entender. Para no poner el código original, he simplificado el código lo máximo posible para que se vea el comportamiento con el código tan corto y simple como sea posible.

Ante todo, para no ir repitiéndome, comento que la entrada (vía stdin) que utilizo en los códigos que voy a poner es la string 110.

El primer código es el siguiente, que se comporta como yo esperaría:

Código (cpp) [Seleccionar] Expandir

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

typedef long long ll;
typedef vector<int> VI;

VI fe;

int llegeix() {
  char c;
  cin >> c;
  if (c == '0') return -1;
 
  int u = fe.size();
  fe.push_back(42);
 
  int aux = llegeix();
  fe[u] = aux;
 
  return u;
}

int main() {
   
  llegeix();
   
  for (int i = 0; i < fe.size(); ++i) cerr << fe[i] << endl;
}

La función llegeix (que para que tenga sentido, significa lee en catalán), simplemente guarda en el vector fe la posición del siguiente 1 leído o -1 si se lee un cero (caso en el que para).

Naturalmente, el programa imprime lo siguiente, que es correcto.

Código [Seleccionar] Expandir

1
-1

Y aquí viene el juego de manos que convierte este código en la versión que manifiesta el comportamiento que no entiendo. Simplemente comento la línea 18 y asigno directamente al vector lo que devuelve la función:

Código (cpp) [Seleccionar] Expandir

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

typedef long long ll;
typedef vector<int> VI;

VI fe;

int llegeix() {
  char c;
  cin >> c;
  if (c == '0') return -1;
 
  int u = fe.size();
  fe.push_back(42);
 
  //int aux = llegeix();
  fe[u] = llegeix();
 
  return u;
}

int main() {
   
  llegeix();
   
  for (int i = 0; i < fe.size(); ++i) cerr << fe[i] << endl;
}

En mi ordenador, con esta versión de g++:

Código [Seleccionar] Expandir

alex@portatil:~$ g++ --version
g++ (Debian 4.7.2-5) 4.7.2
Copyright (C) 2012 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.


Da la siguiente salida, diferente del código anterior, por motivos que no entiendo:

Código [Seleccionar] Expandir

42
-1


He comprobado el código en IdeOne con la versión 4.8.1 que tienen actualmente y ambos códigos me dan los mismos resultados que en mi ordenador. A mi entender, dichos códigos deberían comportarse de la misma forma, ya que si bien la función recursiva modifica el vector (añade un elemento), la variable u no se ve modificada y es diferente en cada llamada de la función.

Para colmo, un amigo con Windows y Dev-C++, que creo que lleva una versión bastante antigua de g++, me dijo que al compilarlos ambos códigos daban la salida que me da a mí el primer código, es decir, la correcta.

Sinceramente no entiendo por qué ambos códigos dan resultados distintos y lo más curioso es que si el 42 que he puesto por poner algo se cambia por cualquier otro número en el segundo código, la salida del primer elemento del vector será dicho número, como si la asignación del primer elemento no se hiciera nunca.

¿Alguien puede decirme el motivo de este comportamiento?

Muchas gracias

Sólo necesitas realizar dos Dijkstras: uno desde el inicio del primer hombre al resto del grafo y otro des del segundo hombre al resto del grafo, teniendo en cuenta en cada caso los arcos válidos para cada uno. Así, tendrás la mínima distancia a cada nodo del grafo respecto cada inicio. Basta ahora que iteres sobre los nodos: si un nodo se puede alcanzar desde ambos extremos, se pueden encontrar en tiempo la suma de las distancias mínimas hasta ese nodo. Coges el mínimo de todos los vértices y es la solución, si no me equivoco.

Además, si los arcos no tienen costes, puedes usar un BFS en lugar de un Dijkstra, haciendo que el problema sea resuelto en complejidad lineal sobre el tamaño del grafo.

Dependerá de la función distancia que quieras utilizar.

Si he entendido bien, necesitas actualizar las posiciones de los barcos cada 30 segundos y una vez están actualizados, necesitas una función que sea algo como proximos(B, k) que retorne los barcos que estén a distancia menor de k del barco B.

La solución que te plantean sirve para la primera parte perfectamente, pero para la segunda en general no funcionará. Con un set supongo que te refieres a lo que internamente suele ser o bien un árbol AVL o bien un Red-Black Tree.

Esto plantea un problema y es que según la distancia que utilice no puedes contestar la segunda función rápido. Por ejemplo, consideremos la distancia euclidiana estándar. No podemos usar ninguna ordenación de manera que los contiguos a un elemento sean los más próximos a él (según esa distancia) y esto implicaría que habría que mirar todos los barcos para poder contestar, es decir, demasiado lento. Si tomamos como distancia que sólo considere la primera coordenada, entonces funcionaría pero no es que sea una distancia muy normal (y de hecho, no es una distancia en el sentido matemático).

Lo que se me ocurre que te puede ir mejor a simple vista es un Burkhard-Keller Tree (BK-Tree). Cada vez que cambies las posiciones tendrás que construir un nuevo árbol (para un millón de barcos le debería dar tiempo de hacerlo en uno o dos segundos así a ojo, por lo que vas sobrado con 30) y gracias a eso podrás contestar rápido las preguntas de proximidad. Además, sirve para cualquier distancia, siempre que sea una distancia en el sentido matemático:

• d(a, b) >= 0 y d(a, b) = 0 <=> a = b
• d(a, b) = d(b, a)
• d(a, b) <= d(a, c) + d(c, b), para cualquier c

Mirándolo por encima la idea es correcta, como no haya algún bug tonto parece que tu código es correcto (no lo he ejecutado). Te comento un par de cosas a tener en cuenta:

Para matrices relativamente pequeñas, tu código puede tener overflow puesto que el determinante implica muchos productos. Para evitar esto completamente tendrías que utilizar algún tipo de BigInts.

Más importante es la complejidad de tu algoritmo. El algoritmo de calcular el determinante por adjuntos es útil para hacerlo a mano con matrices pequeñas, pero es muy ineficiente probar todos los adjuntos, ya que deja una complejidad de O(n!), de modo que a partir de matrices de orden 13 o 14, olvídate de que acabe en un tiempo razonable tu programa. Puedes acelerar tu programa siguiendo el mismo algoritmo utilizando programación dinámica donde el estado es por qué fila de la matriz estás y una máscara de bits que indican qué filas puedes utilizar. Esto da un total de n2ⁿ estados que necesitan tratarse haciendo un bucle en cada uno, luego la complejidad total subiría a O(n²2ⁿ), menor que la anterior, aunque igualmente grande.

La manera buena para calcular el determinante es cúbica y se puede hacer de varias maneras. Por ejemplo por eliminación gaussiana o por descomposición LU de la matriz.

Si no te hace nada mi programa y no termina es porque no le pasarás correctamente la entrada. Si te fijas en lo que he dicho o en el código, verás que mi programa no trabaja con tres números, sino con los que tú quieras, lo he hecho para el caso general . El formato de la entrada es primero la cantidad de números que usarás (en tu caso sería 3), a continuación el resultado que buscas y luego los números que se deban usar (tantos como hayas indicado). Por ejemplo, para tu ejemplo sería:

Código [Seleccionar] Expandir

3 8                                                                                                                                           
7 2 1

Y la salida que produce es

Código [Seleccionar] Expandir

+7+2-1

Otro caso por ejemplo sería

Código [Seleccionar] Expandir

5 8
7 2 1 1 1

Y su salida es

Código [Seleccionar] Expandir

+7+2+1-1-1
+7+2-1+1-1
+7+2-1-1+1