Mensajes

Si no recuerdo mal, la función strstr realiza la comprovación a lo bestia, es decir, si tenemos una string de n carácteres y queremos buscar en ella otra de m, para cada carácter de la primera mira si los m - 1 siguientes coinciden, quedando así un coste de O(nm).

Por si a alguien le interesa, existen algoritmos más eficientes para realizar esto, que consiguen costes de O(n + m), es decir, lineales sobre la longitud de las strings, como por ejemplo Knuth-Morris-Pratt.

El sistema se puede resolver perfectamente por Gauss que es lo que supongo que estás haciendo:

Código [Seleccionar] Expandir

2   14   -4   -2
-4   -3   1   8
3   -5   6   7
f1 = f1/2 (por simplificar)

Código [Seleccionar] Expandir

1   7   -2   -1
-4   -3   1   8
3   -5   6   7
f2 = f2 + 4f1
f3 = f3 -3f1

Código [Seleccionar] Expandir

1   7   -2   -1
0   25   -7   4
0   -26   12   10
f3 = f3/2 (por simplificar)

Código [Seleccionar] Expandir

1   7   -2   -1
0   25   -7   4
0   -13   6   5
f3 = 6f2 + 7f3

Código [Seleccionar] Expandir

1   7   -2   -1
0   25   -7   4
0   59   0   59

Por lo tanto, y = 1, z = 3 y x = -2.

He reaprovechado un código que hice hace un tiempo que multiplica usando Karatsuba, por lo que el código es largo y feo. Si alguien lo prefiere dejo una versión nueva y más legible sin usar Karatsuba. De hecho, Karatsuba sólo se usa si los dos números a multiplicar son suficiente grandes (unos 100 dígitos) en mi código, pero lo dejo por si a alguien le interesa.

Código (cpp) [Seleccionar] Expandir

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

typedef vector<long long> VL;

VL mult(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i2 > f2) return VL(1,0);
    if (f1 >= a.size()) return mult(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return mult(a, i1, f1, b, i2, b.size() - 1);
    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
    int n = f1 - i1 + 1, m = f2 - i2 + 1;
    VL c(max(n,m)*2 + 1, 0);
    for (int i = i1; i <= f1; ++i) {
        for (int j = i2; j <= f2; ++j) {
            c[i - i1 + j - i2] += (a[i]*b[j]);
            c[i - i1 + j - i2 + 1] += (c[i - i1 + j - i2]/1000000000);
            c[i - i1 + j - i2] %= 1000000000;
        }
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}

VL suma(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i1 >= a.size()) {
        VL cero(1,0);
        return suma(cero, 0, 0, b, i2, f2);
    }
    if (i2 > f2 or i2 >= b.size()) {
        VL cero(1, 0);
        return suma(a, i1, f1, cero, 0, 0);
    }
    if (f1 >= a.size()) return suma(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return suma(a, i1, f1, b, i2, b.size() - 1);
    int n = f1 - i1 + 1, m = f2 - i2 + 1;
    VL c(n + m + 2, 0);
    int i = i1, j = i2, k = 0;
    while (i <= f1 and j <= f2) {
        c[k] += (a[i] + b[j]);
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++i; ++j; ++k;
    }
    while (i <= f1) {
        c[k] += a[i];
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++i; ++k;
    }
    while (j <= f2) {
        c[k] += b[j];
        c[k + 1] += (c[k]/1000000000);
        c[k] %= 1000000000;
        ++j; ++k;
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}
   
VL resta(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    VL c;
    c = a;
    for (int i = i2; i <= f2; ++i) {
        c[i] -= b[i];
        while (c[i] < 0) {
            c[i] += 1000000000;
            c[i + 1]--;
        }
    }
    int pos = c.size() - 1;
    while (pos > 0 and c[pos--] == 0) c.pop_back();
    return c;
}

VL karatsuba(VL& a, int i1, int f1, VL& b, int i2, int f2) {
    if (i1 > f1 or i2 > f2) return VL(1,0);
    if (f1 >= a.size()) return karatsuba(a, i1, a.size() - 1, b, i2, f2);
    if (f2 >= b.size()) return karatsuba(a, i1, f1, b, i2, b.size() - 1);
    if (i1 >= a.size() or i2 >= b.size()) return VL(1,0);
    int p = f1 - i1 + 1, m = f2 - i2 + 1;
    if (min(p, m) <= 10) return mult(a, i1, f1, b, i2, f2);
    int n = max(p, m);
    VL c1, c2, c3, x, y;
    int mit = n/2;
    c1 = karatsuba(a, i1 + mit, f1, b, i2 + mit, f2);
    c3 = karatsuba(a, i1, i1 + mit - 1, b, i2, i2 + mit - 1);
    x = suma(a, i1, i1 + mit - 1, a, i1 + mit, f1);
    y = suma(b, i2, i2 + mit - 1, b, i2 + mit, f2);
    c2 = karatsuba(x, 0, x.size() - 1, y, 0, y.size() - 1);
    c2 = resta(c2, 0, c2.size() - 1, c1, 0, c1.size() - 1);
    c2 = resta(c2, 0, c2.size() - 1, c3, 0, c3.size() - 1);
    VL res(2*n + 3, 0);
    for (int i = 0; i < c1.size(); ++i) {
        res[i + 2*mit] += c1[i];
        res[i + 2*mit + 1] += (res[i + 2*mit]/1000000000);
        res[i + 2*mit] %= 1000000000;
    }
    for (int i = 0; i < c2.size(); ++i) {
        res[i + mit] += c2[i];
        res[i + mit + 1] += (res[i + mit]/1000000000);
        res[i + mit] %= 1000000000;
    }
    for (int i = 0; i < c3.size(); ++i) {
        res[i] += c3[i];
        res[i + 1] += (res[i]/1000000000);
        res[i] %= 1000000000;
    }
    int pos = res.size() - 1;
    while (pos > 0 and res[pos--] == 0) res.pop_back();
    return res;
}

string str(long long x) {
    string s;
    do {
        s += char(x%10 + '0');
        x /= 10;
    } while(x > 0);
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    int n;
    cin >> n;
    VL res(1,1);
    for (int i = 1; i <= n; ++i) {
        VL a(1,i);
        VL c;
        c = karatsuba(a, 0, a.size() - 1, res, 0, res.size() - 1);
        res = c;
    }
    cout << res[res.size() - 1];
    for (int i = res.size() - 2; i >= 0; --i) {
        string s = str(res[i]);
        cout << string(9 - s.size(), '0') << s;
    }
    cout << endl;
}


Ahora pasemos al reto de Og. y a ver si alguien se anima, que es una dinámica sencillita.

Tal y como he puesto el código, si M es la matriz de antecesores y u, v son dos nodos cualquiera tales que existe un camino entre ellos (la distancia mínima entre ellos tras hacer Floyd-Warshall no es INF), M[ u][ v] indica el penúltimo nodo del camino mínimo entre u y v. Por ejemplo, si M[ u][v] vale k, significa que el menor camino de u a v será:
u -> (camino entre u y k) -> k -> v.

Y dicho camino entre u y k naturalmente será el mínimo camino entre u y k, por lo que volviendo a consultar la matriz de antecesores podemos ir creando el camino, hasta llegar al origen. La siguiente función, te devolvería el camino mínimo entre s y t con el código anterior que puse:

Código (cpp) [Seleccionar] Expandir

void camino(int s, int t, vector<vector<int> >& A) {
    if (t != s) camino(s, A[s][t], A);
    cout << t << " ";
}

Por ejemplo, en el caso de un grafo más complejo como tú decías, si tienes el siguiente grafo (pongo la entrada como la recibe mi programa):

Código [Seleccionar] Expandir

5 7
0 1 1
0 2 4
0 3 3
1 3 1
2 3 1
2 4 1
3 4 5

Es evidente que el camino mínimo entre los nodos 0 y 4 tiene coste 4 y pasa por todos los nodos. Si llamas a la función que te he puesto:

Código (cpp) [Seleccionar] Expandir

cout << "Camino de nodo 0 a nodo 4" << endl;
camino(0, 4, A);

Devuelve la siguiente salida:

Código [Seleccionar] Expandir

Camino de nodo 0 a nodo 4
0 1 3 2 4

Que es efectivamente el camino mínimo entre 0 y 4.

[Reto #14]

Reto #14
Como aún no he mirado los de este año, os dejo uno de la IOI del año pasado, a mi opinión, el más fácil de todos y con diferencia. Es bastante asequible.
http://www.ioi2009.org/GetResource?id=1271

Si tienes que consultar una lista es muy lento, la idea es usar un vector, para, por ejemplo, el primer millón de números. Obviamente se pasará de ese límite calculando ciertos números, para esos simplemente si ocurre repetiré los cálculos, puesto que no tenemos memoria infinita. Así al menos el intervalo completo [1, 1000000] lo hace de forma instantánea el siguiente programa (aunque repita cálculos si sale del rango):

Código (cpp) [Seleccionar] Expandir

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

typedef long long ll;

ll f(ll n, vector<ll>& v) {
    if (n == 1) return 1;
    if (n >= v.size()) return 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
    if (v[n] == -1) v[n] = 1 + ((n%2 == 1)?f(3*n + 1, v):f(n/2, v));
    return v[n];
}

int main() {
    vector<ll> v(1000000, -1);
    ll a, b;
    while (cin >> a >> b) {
        ll res = 0;
        for (ll i = min(a,b); i <= max(a,b); ++i) res = max(res, f(i, v));
        cout << a << " " << b << " " << res << endl;
    }
}

De hecho esto sería una manera de resolver el problema usando memoization.

Para poder guardar todos los valores, ya que un vector no se puede usar (demasiada memoria) y una lista como tú decías es demasiado lenta (hay que recorrerla entera en el peor caso, coste lineal), la mejor manera que se me ocurre es usar un árbol binario balanceado que permita consultar si está calculado (y su valor) en tiempo logarítmico. Estos están implementados en los contenedores map de la STL de C++. En este problema en concreto no sé qué sería más rápido, si guardar todo con maps aumentando el coste de cada consulta o bien hacer cada consulta instántanea consultando un vector a costa de repetir los cálculos de números fuera del rango del vector.

La gracia es que sea más rápido, si no mal vamos. Simplemente guarda lo que hayas calculado una vez. Cada vez que pases por un número, antes de calcularlo mira si ya está hecho.

Si tu intervalo es el [1, 10], por ejemplo cuando mires el 3 pasarás por el 10, que luego volverás a calcular cuando llegues al 10. Lo que comentaba era evitar estas repeticiones de cálculos, puesto que si el intervalo es grande (según el enunciado los números del intervalo pueden llegar a 1000000), la diferencia es notoria.

No entiendo del todo el código porque no conozco el lenguaje, pero por lo que veo vas de uno en uno dentro del rango y vas haciendo el algoritmo hasta acabar. Hay una manera de hacerlo mucho más rápido.

Como pista, intenta no calcular los pasos para ningún número más de una sola vez

Según las normas tras tres días cualquiera puede poner otro reto, mejor que lo ponga otro, que yo puse este último con intención de que fuera muy sencillo...