[1] Resolviendo nuestro primer problema

0 35

Written by

programación y videojuegos

2 years ago

Topics: Education, Español, Competitive Programming, Blog

Puede que estés entusiasmado o solamente con curiosidad por saber que viene ahora. A continuación veremos un ejemplo de como es el proceso para resolver un problema y enviarlo a un juez. El problema lo resolveremos en un editor de textos, escribiremos el código en C++, usaremos la ventana de comandos o terminal para compilar y ejecutar la solución y luego lo enviaremos al juez en linea para probar nuestra solución.

Eligiendo un juez en linea

Las plataformas que recomiendo para practicar, y con las cuales trabajaremos son Codeforces, Codechef, LeetCode y SPOJ. Todas estos jueces en lineas tienen muchas similitudes en como presentan los problemas:

Codeforces: Descripción del problema, Input, Output, Examples, Time Limit.
Codechef: Descripción del problema, Input, Output, Constraints, Examples, Time Limit.
LeetCode: Descripción del problema, Input, Output, Examples.
SPOJ: Descripción del problema, Input, Output, Examples, Time Limit.

La descripción del problema es la explicación que puede ser muy clara y directa indicando que se necesita resolver, o puede tener un contexto más amplio que influirá en la comprensión del problema. El Input es la descripción de los datos de entrada, se indica el orden en que se proporcionaran, en la mayoría de los casos aquí también se incluyen las restricciones (por ejemplo el problema puede indicar que se utilizarán n datos de entrada donde 0 <= n < 10^5, esto último sería la restricción). El Output es la descripción de como se debe presentar los resultados o respuesta del problema, aquí se enfatiza mucho en el formato de presentación, de esto depende si tu solución es aceptada o no. Los Constraints son las restricciones de las entradas, en algunos jueces están incluidos en el Input. Los Examples son una cantidad muy pequeña (entre 1 a 3) de los casos de prueba totales, acordémonos que existen una cantidad finita de casos de prueba que la solución debe resolver y que no se muestran al competidor. Y por último esta el Time Limit que seria el tiempo máximo permitido para que nuestra solución obtenga la respuesta a un caso de prueba.

Teniendo claro la estructura de un problema pasaremos a resolver eligiendo uno en Codeforces.

Entendiendo el problema

El problema que resolveremos se llama Watermelon, por favor tómese un tiempo para leerlo.

El problema cuenta el contratiempo que tienen dos amigos con una sandia, en esencia lo que el problema solicita es poder dividir la sandia que tiene un peso representado por w en dos partes que tengan un peso par y no necesariamente iguales.

Bien, veamos ahora como es la entrada y salida del problema:

Input: la entrada es un solo número w, y es el peso de la sandia el cual es mayor e igual a 1, y menor e igual a 100, siendo esta la restricción, por ende el juez nos dará solo números enteros positivos que estén dentro de este intervalo.
Output: la salida son dos posibles palabra YES o NO, que indican si es posible o no dividir la sandia teniendo en cuenta la descripción del problema (no olvidemos que tenemos que respetar este formato, en este caso las respuestas a la salida están en mayúsculas).

A continuación vemos los ejemplos que para este problema es solo un caso de prueba donde nos muestra su Input que es 8 y su Output que es YES, este ejemplo nos servirá para probar nuestra solución. Y por ultimo en la parte final, una nota que explica como fue dividida la sandia y por que de la salida que se da en el ejemplo.

Ya teniendo el problema muy claro, empecemos a resolverlo generando ideas a partir de conceptos matemáticos:

Los números con los que trataremos siempre son números enteros positivos.
Sabemos que la suma de 2 números pares positivos, o la suma de 2 números impares positivos siempre da un número par positivo.
Por lo tanto, ¿podríamos decir que un número par positivo es la suma de dos número pares positivos? Aquí me gustaría que lo pienses mientras seguimos con la resolución.
Si la respuesta a la pregunta anterior es cierta lo que tendríamos que hacer es responder YES cuando w es un número par, y NO en caso contrario.

Entonces solo nos queda hacer el código para probar nuestra hipótesis.

#include <bits/stdc++.h>
using namespace std;
#define FINOUT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main() {FINOUT
  
  	int w;
	cin >> w;
	
	if (w % 2 == 0) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
	
	return 0;
}

Expliquemos un poco el código:

Primero declaramos un variable w de tipo int que será para almacenar el peso de la sandia.
Luego recibimos la entrada en la variable w, por intermedio de cin que es el flujo de entrada estándar de C++.
Continuamos con una operación de modulo representado por %, la operación modulo es binario y devuelve el residuo de la división A entre B, si la operación modulo fuera A % B. Para nuestro ejemplo con este resultado sabremos si el número es par, sí es igual a 0 o impar en caso contrario, y esto lo verificamos usando el operador de comparación ==, que devuelve verdadero si A es igual a B y falso en caso contrario, para A == B.
Usamos la condicional if - else para guiar a la operación anterior según el resultado verdadero o falso, y según que valor se le dé, continuará con un porción de código diferente.
Por ultimo imprimiremos la salida por intermedio de cout, que es el flujo de salida estándar de C++.
El código necesario para resolver nuestro problema esta descrito en los puntos anteriores, el código que no se menciono se podría decir que es el código base para que nuestro programa en C++ pueda ejecutarse sin ningún error (en algún articulo posterior se explicara con detalle que aporta cada una de esas lineas).

Con esto tendríamos listo nuestra solución, pero no cantemos victoria, quizás ya te diste cuenta que nuestra solución no funciona para un caso. Que pasaría si w es 2, la respuesta seria YES, pero es una respuesta incorrecta, si nos ponemos a pensar en 2 números pares positivos que sumen 2 no los hallaremos, ahora nos viene la duda, ¿sera el único o habrá otros números más que no cumplan?. Pues para no alargar mucho, este es el único caso, ahora modificaremos el código teniendo en cuenta este detalle.

#include <bits/stdc++.h>
using namespace std;
#define FINOUT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main() {FINOUT
  
	int w;
	cin >> w;
	
	if (w != 2 && w % 2 == 0) {  // Agregamos una comparación en nuestra operación lógica
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
	
	return 0;
}

Modificamos la condición de if - else con la siguiente sentencia:

w != 2 && w % 2 == 0, obtendremos verdadero solo si el peso es diferente de 2 y el residuo de la división entre 2 es cero.

Ahora si tenemos una solución ganadora, guardemos este código en un archivo con el nombre main.cpp, luego compilemos con el siguiente comando en un terminal o ventana de comandos:

g++ -std=c++17 -o main -O2 main.cpp

Ahora ejecutemos nuestro programa compilado:

./main

El programa esperará hasta que ingresemos por teclado un número, si probamos el ejemplo que nos proporciono el problema, la interacción debería ser algo como esto:

En algunos editores de texto ya viene la opción Compile and Run, que ejecutara automáticamente los anteriores dos comandos.

Con esto estamos listos para enviar nuestra solución al juez en linea, ¿que respuesta nos dará el juez?

Enviando la solución

Tenemos listo nuestro archivo main.cpp que enviaremos al juez en linea. Todos los jueces en linea tienen un apartado para enviar la solución al problema que estas tratando de resolver, busque el apartado de SUBMIT, en los jueces Codeforces, Codechef y SPOJ nos proporcionaran dos opciones, la primera es copiar y pegar todo nuestro código en el editor de texto que nos proporciona y la segunda es cargar nuestro archivo. En el caso de LeetCode solo se permite copiar y pegar el código.

Luego de copiar el código, elegir el lenguaje con el que se hizo la solución y dar al botón de Submit, solo nos queda esperar la respuesta del juez. Cuando el juez termine de ejecutar la solución para todos los casos de prueba del problema nos dará un veredicto.

Éxito, hemos resuelto nuestro primer problema :).

En la respuesta del juez hay que tener en cuenta 3 puntos:

El veredicto: indica si la solución fue aceptada o no, es el más importante.
El tiempo: es el tiempo que se demoró en ejecutar la solución enviada, para el problema que hemos resuelto el tiempo limite o Time Limit era de 1 segundo, y el tiempo que demoro nuestra solución es de 30 mili segundos, en otras palabras estamos dentro del tiempo limite.
La memoria: es la memoria usada en la ejecución de nuestra solución, en el problema que hemos resuelto la memoria limite era 64 MB, y solo usamos 0 KB.

Cuando obtenemos un veredicto que no es aceptado, el tiempo y memoria que nos otorga el juez en el resultado nos podría darnos un indicio de que tipo de error tiene nuestra solución.

Y para concluir mencionare los tipos de veredicto que el juez puede dar, estos son los mas comunes:

Accepted (AC): La solución paso todos los casos de prueba, fue aceptada.
Wrong answer (WA): La solución no pasó ninguno o algún caso de prueba por dar una respuesta o salida incorrecta.
Time limit exceeded (TLE): La solución no termino en el tiempo limite indicado por el problema.
Memory limit exceeded (MLE): La solución intenta consumir más memoria de la indicada en el problema.
Runtime error (RTE): La solución finalizó con un código de retorno distinto de cero (posibles razones: acceso al array fuera de límite, división por cero, desbordamiento de pila, uso incorrecto de punteros entre otros).

Espero que haya sido de mucha ayuda esta guía aclarando dudas de como se puede empezar a practicar resolviendo problemas en los jueces en linea.