Una mejor manera de abordar la programación competitiva

Este artículo ayuda a todos aquellos que quieran iniciarse en la Programación Competitiva. El único requisito previo que se necesita es el conocimiento de un lenguaje de programación.

Ahora, busquemos un mejor enfoque para la programación competitiva. Tenga en cuenta:

1. Uno debe leer el formato de entrada y salida adecuado porque la mayoría de los principiantes cometen errores al tener declaraciones impresas adicionales en la salida. Por lo tanto, tenga cuidado con el formato de salida. Ejemplo : «Ingrese el siguiente número:» y «La salida es: .
2. Analice las restricciones del problema antes de escribir el código porque la mayoría de las veces ha escrito el código que es fuerza bruta y no se ejecutará en la restricción de límite de tiempo dada.

Los siguientes son algunos de los problemas que podría enfrentar si es un principiante. :

1. Límite de tiempo : se da en segundos. Le da una idea del orden de la solución correcta. Considere la siguiente situación. Límite de tiempo = 1
   segundo Supongamos que 1 segundo aproximadamente puede realizar 10^8 operaciones.
   Si escribe un programa que es de orden O(N^2) y el problema tiene T casos de prueba. Luego, el orden total de su programa se convierte en O (T * N ^ 2).
   Si T <= 1000 y N <= 1000, entonces (ignorando las constantes ocultas en las notaciones asintóticas) es posible que su código no se acepte en el peor de los casos, ya que 1000*1000*1000 son 10^9 operaciones, lo que significa 10 segundos.
   Para evitar TLE, siempre piense en los peores casos de prueba posibles para el problema y analice su código en esa situación.
2. Error de tiempo de ejecución : es uno de los problemas más encontrados por los principiantes. La razón principal podría ser:
   1. Fallo de segmentación: es el acceso ilegal a la dirección de memoria.
      por ejemplo int[] array = new int[100]; Sistema.salida.println(array[101]);
   2. Declaración de una array de más de 10^8.
   3. Dividir y tomar módulo con 0 .
   4. Debe saber cómo usar GDB que lo ayudará a corregir su error de tiempo de ejecución.
3. Error de compilación : es uno de los errores que se enfrentan con frecuencia al programar en C/C++.

4. Respuesta incorrecta : cada vez que encuentre WA, escriba un código de fuerza bruta y asegúrese de que sea perfecto. Ahora genere casos de prueba usando la función aleatoria en C++. Ejecute su código en estos casos de prueba y haga coincidir el resultado. Ahora piensa en los casos de esquina que te ayudarán a encontrar el problema en tu algoritmo.

5. IntOverflow : Muchas veces sin saberlo superarás el valor máximo que se puede almacenar en el tipo primitivo int. por ejemplo, Restricciones: 0 <num1,num2 <= 10^9

   #include<iostream.h> int main() {     int num1, num2;     cin >> num1 >> num2;     int answer = num1 + num2;        // error if num1 and num2 are large     // numbers     cout<< answer;         return 0; }

   El programa anterior no siempre se ejecutará correctamente porque (2*10^9) puede exceder el valor máximo que se puede almacenar en INTS. es decir, 10 ^ 9. Por lo tanto, tendrá que usar el tipo de datos primitivo long long int o unsigned int para la respuesta en tal caso.

6. Comparando dobles :

   int main() {     float a ;     cin >> a;     if (a == 10)       cout << “YES”; }

   Los tipos de datos float y double no tienen una precisión infinita. Cuidado (precisión de 6/15 dígitos para ellos respectivamente). Así que siempre use un margen de (~0.0000001) al comparar. Ejemplo –

   if (abs(a -10) < (0.0000001))
   {
       cout << “YES”;
   }
   

Otros puntos útiles:
A veces, cuando estás atascado. Verifique el tiempo de ejecución de otro código aceptado y analice el orden de solución requerido y la cantidad de memoria permitida.

1. 4 MB ~ array de enteros de tamaño 10 ^ 6 (suponiendo que int ocupa 4 bytes) o array bidimensional de tamaño 10 ^ 3 * 10 ^ 3

Los límites de memoria estándar en la mayor parte del problema son del orden de 256 MB.

Si tiene que asignar una array grande, entonces NO es una buena idea hacer la asignación dentro de una función, ya que la memoria se asigna y se libera para cada caso de prueba, y la memoria se asigna en la pila de llamadas a la función (el tamaño de la pila está limitado en muchos lugares). ). Por lo tanto, si tiene que hacer una array de gran tamaño, hágala global.

Espero que este artículo le haya sido de ayuda y espero que ahora pueda intentar preguntas estando mejor preparado y, por lo tanto, desempeñarse mejor y más rápido. 🙂

Este artículo es una contribución de Ujjwal Kanodia. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.