Mensajes

Si se quiere conservar un camino mínimo usando Dijkstra, una manera sencilla de hacerlo es guardar para cada nodo su antecesor, de manera que cada vez que se relaja el coste mínimo de un nodo, se pone como padre o antecesor el nodo origen de la arista (o arco) empleada.

Como he puesto, con esto se guarda un camino mínimo para cada nodo, no todos en caso de que haya más de un camino mínimo que acabe en un nodo.

Discrepo. Yo considero que para este caso es mejor una lista de adyacencia. El código no se complica para nada y en caso general es más eficiente que con una matriz de adyacencia para hacer un Dijkstra (pese a que con 45 nodos no se notará la mejoría).

He participado alguna vez en Topcoder, pero no participo regularmente, para eso prefiero Codeforces, me gusta más el estilo, aunque participo habitualmente en concursos de programación y compito con mi universidad en el ICPC, de modo que estoy habituado a este tipo de competiciones.

Cuando dices que el compilador de Topcoder te los rechaza no sé si te refieres a que no te compila o que te dice que no pasa los casos de prueba.

Si es lo primero, mira en la página que versión del compilador utilizan para cada lenguaje, yo he programado en C++ y no he tenido ningún problema con el compilador. Ten en cuenta que en Topcoder, a diferencia de otros concursos, no debes hacer un programa completo que lea entrada e imprima salida, sino que debes programar una clase con el nombre y método que te digan. Yo te recomiendo programar directamente en el compilador de la página, no por versiones ni nada, simplemente que si luego tienes que pasarlo allí, pierdes mucho tiempo y la puntuación que recibes por un problema correcto depende del tiempo que tardes en resolverlo una vez lo abres.

Si es lo segundo, el problema es que tu código no hace lo que tiene que hacer. Una cosa es que localmente te funcione bien con los casos que tú pruebas y otra es que haga correctamente todos los casos privados con los que lo comprueba la página, que contienen todos los casos límite (traducción algo libre de corner cases, es decir, entradas que son problemáticas por algún motivo, como que se tengan que tratar de forma especial o que sean los peores casos que se pueda encontrar tu algoritmo en cuanto a complejidad temporal o espacial).

Sin entrar en temas de si es mejor hacer de una forma u otra lo que comentáis, a modo de apunte comento una mejora que puede hacerse respecto al código original que son los módulos. Realizar la operación módulo es costoso, mucho más que una suma o una resta. Una técnica estándar para optimizar el código cuando se hacen módulos por potencias de dos es sustituir los módulos por ANDs bit a bit. Puede parecer una tontería, pero puede mejorar mucho el tiempo de ejecución de un programa.

La norma general sería convertir esto:

Código [Seleccionar] Expandir

a%pot
en esto otro:

Código [Seleccionar] Expandir

a&(pot - 1)

Simplemente hace un intercambio de las variables:
http://www.cplusplus.com/reference/algorithm/swap/

Tienes varios errores en tu código.

En la función para añadir al inicio, creas un nuevo nodo que pones como inicio, pero no haces que la lista anterior apunte a él (sólo el nuevo nodo apunta a lista). Básicamente, falta la línea que tienes comentada, que supongo que lo habrás hecho porque te daba Segmentation Fault. Esto sucedería porque al principio, a_inici es NULL, de forma que haría falta un if para comprobarlo.

La función de añadir al final la veo horrible por un simple motivo. Estás guardando un puntero al inicio de la lista, pero no uno para el final. Así, si quieres añadir al algo al final, tienes que recorrer la lista entera para llegar al final y después añadir: pasas una operación que teniendo un puntero extra sería O(1) a una operación O(n), siendo n el número de elementos de la lista.

La función para mirar si está el elemento parece correcta, mientras que la de borrar no entiendo qué haces, pero no veo que recorras la lista, de forma que dudo que sea correcta.

He picado ahora cómo haría yo las funciones que implementas, no lo he probado en profundidad, pero parece que funcionan bien.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

struct Node {
    int dada;
    Node *seguent;
    Node *anterior;
};

Node *inici = NULL, *final = NULL;

void afegirInici(int x) {
    Node *p = new Node;
    p->dada = x;
    p->seguent = inici;
    p->anterior = NULL;
    if (inici != NULL) inici->anterior = p;
    swap(p, inici);
    if (final == NULL) final = inici;
}

void afegirFinal(int x) {
    Node *p = new Node;
    p->dada = x;
    p->seguent = NULL;
    p->anterior = final;
    if (final != NULL) final->seguent = p;
    swap(p, final);
    if (inici == NULL) inici = final;
}

bool existeix(int x) {
    Node *actual = inici;
    while (actual != NULL) {
        if (actual->dada == x) return true;
        actual = actual->seguent;
    }
    return false;
}

//Esborra totes les ocurrencies de x a la llista
void esborrar(int x) {
    Node *actual = inici;
    while (actual != NULL) {
        if (actual->dada == x) {
            if (actual->anterior != NULL) actual->anterior->seguent = actual->seguent;
            else inici = actual->seguent;
            if (actual->seguent != NULL) actual->seguent->anterior = actual->anterior;
            else final = actual->anterior;

            Node *aux = actual->seguent;
            delete actual;
            actual = aux;
        }
        else actual = actual->seguent;
    }
}

void llistar() {
    Node *actual = inici;
    while (actual != NULL) {
        cout << actual->dada;
        if (actual->seguent != NULL) cout << " <-> ";
        actual = actual->seguent;
    }
    cout << endl;
}

int main() {
    char c;
    while (cin >> c) {
        if (c == 'I') {
            int x;
            cin >> x;
            afegirInici(x);
        }
        else if (c == 'F') {
            int x;
            cin >> x;
            afegirFinal(x);
        }
        else if (c == 'E') {
            int x;
            cin >> x;
            cout << (existeix(x)?"Existeix":"No existeix") << endl;
        }
        else if (c == 'L') llistar();
        else {
            int x;
            cin >> x;
            esborrar(x);
        }
    }
}

Te pongo la prueba que he hecho:

Entrada:

Código [Seleccionar] Expandir

I 1 I 2 I 3
L
F 1
L
F 23
L
E 1
E 23
E 25
E 4
B 2
L
B 1
L
B 3
L
B 23
L
I 1
L
F 2
L

Salida:

Código [Seleccionar] Expandir

3 <-> 2 <-> 1
3 <-> 2 <-> 1 <-> 1
3 <-> 2 <-> 1 <-> 1 <-> 23
Existeix
Existeix
No existeix
No existeix
3 <-> 1 <-> 1 <-> 23
3 <-> 23
23

1
1 <-> 2

Tu solución parece que es incorrecta. La he probado y comparado con las tres mías y para casos pequeños dan lo mismo, pero a poco que los números empiezan a ser grandes falla y las mías coinciden.

El problema creo que es que no aplicas correctamente el módulo. Si he entendido tu solución, cada vez que te pasas del módulo restas hasta compensarlo (o lo que sería equivalente, haces % c). Esto sería correcto si no hubiera divisiones de por medio, pero al haber divisiones falla. No puedes dividir y hacer módulo a la vez, puesto que no es lo mismo. Lo correcto sería en lugar de dividir, multiplicar por el inverso del divisor módulo 1000000000, pero no es primo, de forma que no todos los divisores serán coprimos con él, de forma que no puedes solucionar el problema así...

Si miras mi solución, al final acabo calculando (n +m sobre m) - 1 mod 1000000000, pero para realizarlo, en lugar de usar la típica fórmula con factoriales (que implica divisiones) uso la recurrencia lineal que solo tiene sumas, que no dan problemas con el módulo, haciendo pasar una solución que matemáticamente es lineal a ser cuadrática con memoria cuadrática también.

Más que strings, para programar BigInts la práctica más extendida es usar vectores de enteros, de forma que en cada posición no se guarda un único dígito, sino varios de ellos, permitiendo aprovechar las operaciones de las variables nativas del lenguaje y además haciendo el cálculo de forma mucho más eficiente.

He picado un ejemplo para poder hacer potencias. No lo he testeado así que quizá tenga algún bug, pero la idea en sí creo que se entiende con el código.

Código (cpp) [Seleccionar] Expandir

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

typedef long long ll;
typedef vector<ll> VL;

const ll base = 1000000000;

class BigInt {
    public:
        VL v;
        int signo;

        BigInt() {
            v = VL(1, 0);
            signo = 1;
        }
        BigInt(ll x) {
            do {
                v.push_back(x%base);
                x /= base;
            } while (x > 0);
            signo = 1;
        }
        void operator*=(const BigInt& b) {
            BigInt c;
            c.v.resize(v.size() + b.v.size(), 0);
            c.signo = signo*b.signo;
            for (int i = 0; i < v.size(); ++i) {
                for (int j = 0; j < b.v.size(); ++j) {
                    int k = i + j;
                    c.v[k] += v[i]*b.v[j];
                    while (c.v[k] >= base) {
                        c.v[k + 1] += c.v[k]/base;
                        c.v[k++] %= base;
                    }
                }
            }
            int i;
            for (i = c.v.size() - 1; i > 0 and c.v[i] == 0; --i);
            c.v.resize(i + 1);
            *this = c;
        }
        BigInt pow(ll k) {
            if (k == 0) return BigInt(1);
            BigInt res = this->pow(k >> 1);
            res *= res;
            if (k&1) res *= (*this);
            return res;
        }
        friend ostream &operator<<(ostream &out, BigInt &b) {
            if (b.signo < 0) out << '-';
            int i = b.v.size() - 1;
            out << b.v[i];
            for (--i; i >= 0; --i) out << setw(9) << setfill('0') << b.v[i];
            return out;
        }
};

int main() {
    BigInt x(10);
    x = x.pow(1000);
    cout << x << endl;
}


Como veo que la cosa está bastante parada, me tomo la libertad de poner mi análisis para el primer problema a ver si así se reactiva esto un poco, que lo considero una interesante idea. Pongo el texto en Latex a continuación:

Código [Seleccionar] Expandir

\documentclass[a4paper,article,10pt]{article}
\usepackage{geometry}
\ttfamily
\usepackage[dvips]{graphicx,psfrag,overpic,color}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{pstricks}
\usepackage[postscript]{ucs}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{fancyhdr}
\usepackage{listings}
\geometry{margin=1.5cm}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead{}
\fancyfoot{}
\rhead{\thepage}
\chead{Espirales - ghastlyX}
\rfoot{\thepage}

\newtheorem{teo}{{Teorema}}
\newtheorem{recu}{{Recurrencia}}
\newtheorem*{lema}{{Lema}}
\newtheorem*{coro}{{Corolario}}
\newenvironment{demo}[1][Demostración:]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{defi}[1][Definición]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{exemple}[1][Ejemplo]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remarca]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\renewcommand{\labelenumi}{(\alph{enumi})}

\begin{document}
\noindent Se va a proceder paso a paso en la resoluci\'on de este problema.
Dejando a un lado la soluci\'on por backtracking, puesto que es demasiado
ineficiente, se puede considerar una primera soluci\'on usando programaci\'on din\'amica.
Basta hacer un par de consideraciones para llegar a esta primera
soluci\'on. Sea $f(n, m)$ el n\'umero de espirales diferentes (sin tomar m\'odulo) en un tablero de $n\times m$.
\begin{lema}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(m, n)$.
\end{lema}
\begin{demo}
Es evidente por simetr\'ia. $\blacksquare$
\end{demo}

\noindent Visto esto, dado un tablero de $n\times m$, las posibles espirales
son las que realizan una \textbf{L} y se acaban y las que despu\'es de realizarla
siguen avanzando. Esta \textbf{L} primero puede avanzar $n$ casillas y despu\'es
puede bajar hasta $m$ casillas, dando un total de $nm$ posibles \textbf{L}s.
Teniendo en cuenta que tras realizar la \textbf{L} vuelve a quedar un tablero de
$i\times j$, donde $i + 1 \leq n$ y $j + 1 \leq m$ son las dimensiones de
dicha \textbf{L}, se obtiene una primera recurrencia:

\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que
$f(n, m) = nm + \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}f(i, j)$.
\end{recu}
\noindent Con esta recurrencia se obtiene un primer c\'odigo, cuya complejidad es $O(n^2m^2)$:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001]; //Tabla para la dinamica

long long f(int n, int m) {
    if (M[n][m] == -1) { //Si no esta calculado
        //Si el simetrico esta calculado, se devuelve ese por el lema
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n*m% MOD; //Espirales en forma de L sin continuar
        //Se suma el resto de espirales
        for (int i = 1; i <= n - 1; ++i)
            for (int j = 1; j <= m - 1; ++j)
                M[n][m] = (M[n][m] + f(i,j))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    //Inicializacion de la tabla a -1
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Esta recurrencia puede simplificarse, para as\'i eliminar uno de los
dos bucles de cada estado en la din\'amica. Si en lugar de considerar la
\textbf{L}, se avanza tan solo en la primera direcci\'on, se tienen $n$ posibles
espirales m\'as las que luego siguen creciendo en el tablero que queda, de
dimensiones $i\times (m - 1)$, donde $1 \leq i \leq n$ es lo que se avanza antes
de seguir. Con esto se obtiene la segunda recurrencia:
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que
$f(n, m) = n + \sum\limits_{i = 1}^{n}f(i, m - 1)$.
\end{recu}
\noindent Esta segunda recurrencia permite conseguir una complejidad de $O(n^2m)$.
El siguiente c\'odigo muestra como usarla adaptando el primer c\'odigo:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1000000000;
long long M[1001][1001];

long long f(int n, int m) {
    if (M[n][m] == -1) {
        if (m == 1) return M[n][m] = n;
        if (M[m][n] != -1) return M[n][m] = M[m][n];
        M[n][m] = n% MOD; //Posibles inicios de la L
        //Suma del resto de espirales
        for (int i = 1; i <= n; ++i)
            M[n][m] = (M[n][m] + f(i, m - 1))%MOD;
    }
    return M[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= 1000; ++i) for (int j = 0; j <= 1000; ++j) M[i][j] = -1;
    cout << f(n, m)%MOD << endl;
}
\end{lstlisting}
\noindent Si bien este c\'odigo es bastante m\'as r\'apido que el primero,
se puede mejorar a\'un m\'as trabajando un poco m\'as la recurrencia. El siguiente
resultado muestra como poder hacerlo.
\begin{recu}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$.
\end{recu}
\begin{demo}
Queremos ver que $f(n, m) = f(n - 1, m) + f(n, m - 1) + 1$.
Aplicando la segunda recurrencia, se tiene que ser\'a cierto si y s\'olo si $n + \sum\limits_{i =
1}^{n}f(i, m - 1) = n - 1 + \sum\limits_{i = 1}^{n - 1}f(i, m - 1) + n + \sum\limits_{i = 1}^{n}f(i, m - 2 ) + 1$
es cierto. Simplificando esta segunda
expresi\'on queda $f(n, m - 1) = n + \sum\limits_{i = 1}^{n}f(i, m - 2)$,
que es cierta, puesto que es precisamente la segunda recurrencia vista
anteriormente. $\blacksquare$
\end{demo}
\noindent Por esta recurrencia y el lema se obtiene el \'ultimo resultado:
\begin{coro}
Sean $n, m\in \mathbb{N}$ arbitrarios. Se cumple que $f(n, m) = \binom{n+m}{m} - 1$.
\end{coro}
\noindent Por \'ultimo, el c\'odigo que utiliza este resultado:
\lstset{language=C++}
\begin{lstlisting}
#include <iostream>
using namespace std;

int M[2002][2002];
const int MOD = 1000000000;

int main() {
    int n, m;
    for (int i = 0; i < 2002; ++i) M[i][0] = M[i][i] = 1;
    for (int i = 2; i < 2002; ++i)
        for (int j = 1; j < i; ++j) 
            M[i][j] = (M[i - 1][j - 1] + M[i - 1][j])%MOD;
    cin >> n >> m;
    cout << (M[n + m][m] + MOD - 1)%MOD << endl;
}
\end{lstlisting}
A continuaci\'on se puede ver una comparativa de los diferentes c\'odigos con diferentes entradas:\\\\
\begin{tabular}{|c|c|c|c|c|}
\hline
& $n=m=100$ & $n=m=500$ & $n=m=750$& $n=m=1000$ \\
\hline
C\'odigo 1 & 0m0.288s & 2m31.501s & 12m44.252s & No realizado\\
\hline
C\'odigo 2 & 0m0.012s & 0m0.492s & 0m1.688s & 0m4.280s \\
\hline
C\'odigo 3 & 0m0.032s & 0m0.032s & 0m0.032s & 0m0.032s\\
\hline
\end{tabular}
\end{document}

Como ya te han dicho, los árboles se suelen hacer de un determinado tipo según el problema que quieras resolver. Por ponerte un ejemplo de cómo sería un árbol de 3 hijos por nodo, te he picado un código para una posible implementación de un TST (Ternary Search Tree).

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

struct Nodo {
    char c;
    Nodo *lo, *eq, *hi;
};

void add(Nodo *&nodo, string& s, int p) {
    if (p == s.size()) return;
    if (nodo == NULL) {
        nodo = new Nodo;
        nodo->c = s[p];
        nodo->lo = nodo->hi = nodo->eq = NULL;
        add(nodo->eq, s, p + 1);
    }
    else {
        if (s[p] < nodo->c) add(nodo->lo, s, p);
        else if (s[p] > nodo->c) add(nodo->hi, s, p);
        else add(nodo->eq, s, p + 1);
    }
}

bool search(Nodo *nodo, string& s, int p) {
    if (p == s.size()) return true;
    if (nodo == NULL) return false;
    if (s[p] < nodo->c) return search(nodo->lo, s, p);
    else if (s[p] > nodo->c) return search(nodo->hi, s, p);
    else return search(nodo->eq, s, p + 1);
}

int main() {
    Nodo *raiz = NULL;
    char c;
    while (cin >> c) {
        if (c == 'A') {
            string s;
            cin >> s;
            add(raiz, s, 0);
        }
        else if (c == 'S') {
            string s;
            cin >> s;
            if (search(raiz, s, 0)) cout << "String encontrada" << endl;
            else cout << "String NO encontrada" << endl;
        }
    }
}

No es difícil poner n hijos a un árbol, pero hay que tener en cuenta si sirve para algo hacerlo. Hay estructuras de tipo árbol más díficiles de implementar que otras, pero la dificultad no suele estar en el número de hijos, sino en la morfología del árbol. Por poner un par de ejemplos de algunos árboles más díficiles de picar, tienes por ejemplo los Suffix Trees o los TST con funciones de fallo para hacer un Aho-Corasick.