Os propongo un concurso

Hawkings

Todo depende de cómo lo hayas planteado. Si quieres cuéntame por MP cómo tienes planteado tu algoritmo y te puedo ayudar. Según cómo lo hayas hecho, estos son algunos casos que podrían ser problemáticos:

20 20 10
25 20 10
31 20 12

30 30 8
30 34 8
34 32 8

PD: gracias por el applet salva, me vino bien para poner los ejempos

Nhur

Esos 3 dan 1 verdad? no me falla ninguno.

La metodología de mi algoritmo es, para cada mina, hacer una explosión en cadena y contar cuantas minas explota, me quedo con la que más ha explotado, y repito el algoritmo con las restantes, sin contar con las que han explotado ya, evidentemente.

Por lógica aplastante, si siempre coges la cadena de explosiones más grande, hasta que no queda ninguna mina, llegas a la solución óptima.

Si aun así se os ocurre algún caso en el que el algoritmo pueda resentirse, os invito a sugerir más casos raros, xq en serio, no se que clase de problema puede tener el maldito UVa...

EDIT: Valeeeeee, encontre el ligero problema que me decia wrong answer, ahora toy en Time Limit exceeded, asi k... a reducir carga!

Salvatore

ese método debería funcionar, es lo mismo que pensé yo para resolverlo.

también se me ocurrió hacer explotar siempre la mina que no esté contenida en ninguna otra mina. Si no está contenida, nunca va a explotar si no la explotas a mano no?
Así se evita andar desencadenando explosiones

El problema de este otro método es para los casos como este:

Nhur

Sí, ese fue el primer caso que se me ocurrió, explotar minas que no tuviesen ninguna otra... pero claro tenía ese problema.
Y si... hago una combinación de ambos? y solo uso las cadenas para cuando haya casos cíclicos? Iwal ahorro btt tiempo.

Salvatore

exacto, así surgió la idea.
Andar desencadenando explosiones con cada mina del mapa lleva mucho tiempo. ¿cómo evitas hacerlo con todas las minas? ¿es posible saber cuándo una mina claramente NO va a ser candidata a ser explosionada a mano?
Si está contenida en otra mina, podemos saltárnosla, esa no nos sirve.

Yo pensaba añadirle esa comprobación, partiendo del algoritmo del desencadenamiento de explosiones, algo tipo:
if (minaEstaContenidaEnOtra())
saltarALaSiguiente()

Con lo cual, te ahorras un montón de explosiones, pero a cambio con cada mina estás realizando una comprobación (si está contenida en otra mina) que puede ser peor.

hr
Otra idea que se me ocurre es almacenar las minas en forma de árboles. Según vas leyendo las minas. Me explico:
cada vez que lees una mina, creas con ella un árbol en el que está como raíz. a continuación intentas 2 cosas:
a) insertar esa mina como raíz de alguno de los otros árboles.
b) insertar esa mina en el resto de árboles, como "hija" de algún nodo.

De esta forma si una mina está dentro de un árbol, significa que alguna de las minas de dicho árbol la contiene en su área de explosión.

Al final tomas el árbol con más nodos, lo haces explotar, y trabajas con el resto de árboles, con la ventaja de que ya están hechos, simplemente habría que limpiarlos de nodos que ya no existen. Cosa que me parece sería sencillo, puesto que con mirar la raíz de cada árbol bastaría si no me equivoco.

Nhur

La solución del árbol parece lógica, pero no has contado con que una mina puede explotar a otra, que a su vez es explotada por esta, así tendrías un nodo cuyo padre e hijo son el mismo...

Hawkings

Os explico cómo lo he hecho yo a ver si os ayuda. Por si alguien no quiere leerlo lo pongo en un spoiler, pero sabed que solo está la explicación, no hay ni una línea de código

Primero tengo una estructura, clase o lo que sea, llamada mina. En ella almaceno algunos datos, como las minas que explotarían si la actual detona o un valor booleano que indica si la mina ya ha sido visitada para evitar caer en bucles infinitos a la hora de hacer búsquedas en profundidad.

En el programa, leo todos los datos de las minas y los almaceno (complejidad O(n)). Después para cada mina compruebo qué minas serían activadas si la actual explota (complejidad O(n²-n)). A continuación ordeno el grafo en orden posterior, con una función recursiva que empieza en una mina y va haciendo una búsqueda en profundidad, poniendo un número a cada mina (complejidad O(n)). Ahora inicio una función recursiva que explota todas las minas, dejando 4 estados posibles en cada mina: 'S' (sin explotar), 'I' (mina que inicia una exlposión), 'O' (mina explotada por otra) y 'P' (primera mina que explota). Este último estado lo tengo para evitar bucles infinitos si hay ciclos. Para cada mina, si su estado es 'I' lo cambio por 'O', y si no paso a la siguiente mina sin hacer nada (complejidad O(n)). Por último recorro todas las minas para ver cuántas tienen estado 'I' (complejidad O(n)). En total la complejidad es O(n²+2n), y no me da TLE.

Un saludo :icon_cheesygrin:

Salvatore

bastaría con evitar que una mina se añada como raíz y como hija de un mismo árbol. Se intenta primero la opción "a) como padre". Si se cumple, pasas a otro árbol. Si no, intentas insertarla como hija.
Pero nunca ambas cosas, para evitar eso, que el nodo esté presente duplicado en un árbol.

Si buscas el ejemplo de hawkings, el de las 3 minas:

Y las llamas Top, Bottol y Right por identificarlas de alguna forma (T, B y R).
lees la mina T. Creas un árbol por ser la primera.
lees la mina B, intentas meterla como padre de T. Funciona (T está dentro de B).
lees la mina R, intentas meterla como padre en el árbol, funciona, con lo q te queda:
R -> B -> T

Si buscas otro ejemplo, por ejemplo este:

Y las numeramos de izq a derecha: 1, 2, 3, 4 y 5

Imagina que el orden en que las leemos es ese mismo, de izq a dcha:
Leemos la 1, creamos árbol.
Leemos la 2, es padre de la 1 : 2 -> 1
Leemos la 3, padre de la 2: 3 -> 2 -> 1
Leemos la 4, padre de la 3: 4 -> 3 -> 2 -> 1
Leemos la 5, que es padre de la 4: 5 -> 4 -> 3 -> 2 -> 1

Si nos las diesen al revés, primero la 5 hasta la 1:
5
5 -> 4
al leer la 3, vemos que no es padre de nuestra raíz (la 5), así que tratamos de insertarla como hija. Hija de la 5? no. Hija de la 4? Sí:
5 -> 4 -> 3
etc.

Yo creo que podría funcionar.

hr
Hawkings, no entiendo de qué grafo hablas _xD_
Dices que lo ordenas, pero ¿cómo lo construyes? Las minas son los nodos del grafo? Es un grafo dirigido? Es un grafo o son varios? Me he perdido.

Hawkings

Las minas son los nodos del grafo dirigido. En cada nodo tengo una lista de nodos hijo pero no me hace falta tener guardado ningún nodo padre.

Nhur

Es curioso, he utilizado el sistema en árbol, y ya no da TLE, de hecho, le lleva 2.8 segundos darse cuenta de que es wrong answer... :T.T: