Caso de prueba 7 en problema yurumi

Me refiero a este problema.

Este problema me da 92 puntos a excepción por el caso de prueba 7.
El caso de prueba no retornaba una salida incorrecta, sino que aparecía “Execution killed with signal 11” este es el mensaje comúnmente que intentaste hacer algo como array[-42].
Como ya lo habían resuelto varias personas pensé que el error estaba claramente en mi código.
Estuve mirándolo un largo rato y finalmente decidí empezar a cortar el problema hasta que la salida sea algo diferente.
Llegué a acortarlo tanto como esto, algo que estoy casi seguro que no debería fallar:

ifstream fin("yurumi.in");

int M, N, X;
fin >> M >> N >> X;

vector<vector<bool>> map = vector<vector<bool>>(M, vector<bool>(N, false));

int fil, col;
for (int i = 0; i < X; i++) {
	fin >> fil >> col;
	fil--;
	col--;
	map[fil][col] = true;
}

Resulta que si mandas este código al juez, en el caso de prueba 7 tira “Execution killed with signal 11”.
Si comentás la ante ultima línea, la salida es “A la superficie le falta 1992008”, que es esperable.

Despues pase a la fase voy a tirar todo por la ventana. Lo que hice fue cambiar esto:

vector<vector<bool>> map = vector<vector<bool>>(M + 1000, vector<bool>(N + 1000, false));

Le sumo 1000 de cada lado, y el error desaparece.
Por desgracia… si le sumo 1000 en mi programa real, el error no se va.

Al final hice un boundary check y obtuve 100 puntos:

	fin >> fil >> col;
	fil--;
	col--;
	if(fil < 0 || fil >= M)
		continue;
	if(col < 0 || col >= N)
		continue;
	map[fil][col] = true;

Acá hay algo raro :confused:
Despues por curiosidad me fui a fijar que habían hecho López y Lasorsa (crípticos sus códigos por cierto jaja) y ellos no tuvieron que realizar el checkeo, ni idea que pasó :man_shrugging:

1 me gusta

¡Gracias por el aviso! :smiley:

Como no veía razón por la que tu código causaba ese error, miré el caso y efectivamente tenés razón, había algo raro en el caso. Lo que estaba ocurriendo es que el caso 7 tenía un pequeño error y decía que había un obstáculo más de los que en verdad venían.

De todas formas los casos que teníamos en el juez en yurumí no eran de lo mejor y tenemos pendiente mejorarlos/agregar nuevos. De hecho, aprovechando esta situación, donde tuvimos que corregir un caso, agregamos otro donde se refleja mejor la solución deseada.

Ahora tu código saca 88/100 (hubo reajuste de pesos en los casos), porque no pasa este caso que agregamos. Quizá quieras pensar si el algoritmo que describís es correcto o no :wink:

Aprovecho para comentar. Siempre que crean que hay algo raro (ya sea en el juez o con los casos), por favor avisen. Si avisan hay dos opciones.

  1. Estaba mal algo en el juez, en cuyo caso hacemos lo posible por arreglarlo y todos tenemos un juez mejor.

  2. Había algún error en la interpretación del problema o lo que nos comentan y los ayudamos a superar la dificultad en el problema.

En ambos casos salimos ganando :grin:

3 Me gusta

Muy raro, lo estuve revisando mucho por este error que habia. Segun el juez a mi resultado le falta 1 de superficie.
Me fui a fijar al que quedó en “Usuarios con las mejores soluciones” pero solo estaba santo con su solución fantasma de 0.38 (no tiene envíos).
Yo lo resolví corriendo dp 2 veces sobre la grilla. Me tiras un tip de la solución deseada?

1 me gusta

Recién respondí por privado la consulta del problema para no desvirtuar el tema del post que era sobre un caso malo en el OIAJ.

Las consultas por problemas si pueden pónganlas en un post separado en la categoría Problemas para que sea más ordenado (este problema en particular además iría en la subcategoría de problemas de Selectivo).

Igual no se preocupen mucho por ponerlo en la categoría adecuada, si vemos que lo pusieron en una categoría que nada que ver, los moderadores podemos modificarlo.

1 me gusta

Qué groso, no sabía que tenía un envío fantasma, quedó de alguna cosa vieja borrada XD

Ahora hice un envío de verdad igual, experimentando algunas versiones distintas :stuck_out_tongue:

El tiempo límite estaba medio estricto: aunque era alcanzable optimizando las ideas y las pasadas del algoritmo, y reutilizando la misma tabla en lugar de crear nuevas, decidimos aumentarlo así que ahora es de 2 segundos y todo fue reevaluado.

Hola mlomb! Te tiro un caso de prueba para que reveas tu código:

4 10 2
1 3
1 8

O sea el tablero siguiente:

00x0000x00
0000000000
0000000000
0000000000

Tu respuesta ubica los tableros así:

22x1111x00
2201111000
0001111000
0001111000

Pero podrías tener un cuadrado de 3x3 comenzando en la casilla (2,1) , además del de 4x4.

A seguir viendo el código :muscle:

No sé si @Guty quiere tirar una pista, pero yo te diría que con este caso en mente mires tu código, y una vez que cambies lo que haya que cambiar y des una respuesta correcta a ese caso, si sigue sin dar 100 puntos o veo de buscar otro caso, o te tiro una pista.

Saludos!

2 Me gusta

Voy a hacer una aclaración ya que estoy. En lo que dice @sebach además de dar la respuesta correcta en ese caso, se ve reflejada la interpretación del enunciado.

Como estaba antes, podía ser un poco ambiguo qué quería decir que dos parcelas se toquen (podría interpretarse que la intersección sea completamente nula, que si comparten un vértice está todo bien pero toda una arista no, o que está todo bien si comparten aristas).

Recientemente se agregaron dos notas al final del enunciado, en particular una de ellas dice:

Nota: Se considera que las parcelas se tocan, si hay algún cuadrado de la cuadrícula que pertenece a ambas

Claro, me olvidé de hablar de lo de la interpretación aunque fue para no confundir, no había visto las Notas y no sabía cómo “demostrar” que esa era la interpretación correcta del “se toquen”. Mi manera de confirmarlo fue correr ese caso de prueba contra el código de Agustín je :stuck_out_tongue: