Retos C/C++

[ghastlyX]

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

[[D4N93R]]

ghastlyX, dices que hay una manera más rápido de hacerlo, no lo comprendo ya que como se si para un número que aún no he calculado cuál va a ser el resultado?

Es decir, si es un rango [1..10] para que comprobar si ya lo hice con 7 por ejemplo, si se que solo va a salir una sola vez. A menos de que haya entendido mal

[ghastlyX]

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.

[[D4N93R]]

Ah ok!! ya lo pillo xD vale.. a ver si me sale xD que eso complica un poco las cosas!

Y tienes razón, eso podría mejorar mucho el performance del código.

EDIT: ghastlyX la única forma que se me ocurre de hacerlo como tu dices creo que va a ser muy lenta. Ni idea.. xD

[ghastlyX]

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.

[[D4N93R]]

Justamente eso había hecho, pero no se, en casos donde esté iterando números muy grandes, tengo que revisar una lista en cada giro. Tengo que hacerle pruebas de rendimiento a ver que tal.


Saludos!

[ghastlyX]

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.

[[D4N93R]]

Si exacto, ese es el problema, yo pensé usar un binarytree pero no sabes la flojera que me dió. :/

Hice las dos pruebas, con vector y con list. Obviamente Vector es mucho más rápido en grandes intervalos. En pequeños no se nota la diferencia entre ambos.

Un saludo!

[[L]ord [R]NA]

GhastlyX publicaste la respuesta... pon el proximo reto.

[ghastlyX]

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