Programación Competitiva: Conquistando un problema dado

La programación es el proceso de desarrollar e implementar conjuntos de instrucciones para permitir que una computadora realice una determinada tarea. Los concursos de programación como ACM ICPC, Google CodeJam e IEEE Extreme, etc. son campos de juego deliciosos para la exploración de la inteligencia de los programadores.
Desde conocer el concurso al principio hasta estar en ACM ICPC Amritapuri Regionals, he aprendido mucho y me gustaría compartir algunos consejos para que los codificadores aborden los problemas del concurso.

Durante un concurso en tiempo real, equipos formados por tres estudiantes y una computadora deben resolver tantos problemas como sea posible en 5 horas. El equipo con más problemas resueltos gana, donde ‘resuelto’ significa producir los resultados correctos para un conjunto de entradas de prueba (triviales y secretas). Aunque las habilidades individuales de los miembros del equipo son importantes, para ser un equipo superior, es necesario hacer uso de la sinergia dentro del equipo.

Sin embargo, para hacer un uso completo de una estrategia, también es importante que sus habilidades individuales estén lo más perfeccionadas posible. No tienes que ser un genio ya que practicar te puede llevar bastante lejos. En cuanto a la sensación, hay tres factores cruciales para ser un buen equipo de programación:

1. Conocimiento de algoritmos estándar y la capacidad de encontrar un algoritmo apropiado para cada problema en el conjunto.
2. Capacidad para codificar un algoritmo en un programa de trabajo
3. Tener una estrategia cooperativa con tus compañeros

¿Qué es un algoritmo?

El algoritmo es una secuencia paso a paso de instrucciones que debe seguir la computadora.

Para poder hacer algo competitivo en los concursos de programación, debe conocer muchos algoritmos conocidos y la capacidad de identificar qué algoritmos son adecuados para un problema en particular (si el problema es sencillo), o qué combinaciones o variantes de algoritmos ( si el problema es un poco más complejo).

Capacidad para identificar rápidamente los tipos de problemas.

En todos los concursos de programación, solo hay tres tipos de problemas:

1. No he visto este antes.
2. He visto este tipo antes, pero no lo he hecho o no puedo resolverlo.
3. He resuelto este tipo antes.

En los concursos de programación, se enfrentará a un conjunto de problemas, en lugar de un solo problema. La capacidad de identificar rápidamente los problemas en las clasificaciones de contexto mencionadas anteriormente (no he visto, he visto, he resuelto) será un factor clave para tener éxito en los concursos de programación. Según mi conocimiento y repositorio, un problema generalmente se clasifica entre categorías dadas:

1. Matemáticas : número primo, entero grande, permutación, teoría de números, factorial, Fibonacci, secuencias, módulo
2. Programación dinámica : subsecuencia común más larga, subsecuencia creciente más larga, distancia de edición, mochila 0/1, cambio de moneda, multiplicación de string de array, suma de intervalo máximo
3. Gráfico transversal : relleno de inundación, Floyd Warshal, MST, coincidencia bipartita máxima, flujo de red, punto de articulación
4. Clasificación : Clasificación de burbujas, Clasificación rápida, Clasificación de combinación, Clasificación de selección, Clasificación de Radix, Clasificación de cubeta
5. Búsqueda : búsqueda completa, fuerza bruta, búsqueda binaria
6. Procesamiento de strings: coincidencia de strings, coincidencia de patrones
7. Problemas ad hoc : problemas triviales

Habilidad para analizar su algoritmo

Has identificado tu problema. Crees que sabes cómo resolverlo. La pregunta que debe hacerse ahora es simple: dado el límite de entrada máximo (generalmente dado en la descripción del problema), ¿puede mi algoritmo, con la complejidad que puedo calcular, pasar el límite de tiempo dado en el concurso de programación?

Por lo general, hay más de una manera de resolver un problema. Sin embargo, algunos de ellos pueden ser incorrectos y otros no son lo suficientemente rápidos. Sin embargo, la regla general es: haga una lluvia de ideas sobre muchos algoritmos posibles, ¡luego elija el más estúpido que funcione!

Es útil memorizar el siguiente orden para determinar rápidamente qué algoritmo funciona mejor asintóticamente: constante < log n < n < n log n < n^2 < n^3 < 2^n < n!

Codificando el problema

Siga el principio KISS: manténgalo simple e inteligente, manteniendo todas las versiones funcionando y refinando el código paso a paso.

Después de haber codificado con el mejor algoritmo, emparejando la complejidad de tiempo/espacio y satisfaciendo los casos de prueba (los casos de prueba de muestra son triviales, así que nunca mida la corrección del código de acuerdo con ellos y pruebe también los casos complicados), luego envíe la solución: ‘ ACEPTADO
‘ un caso de prueba complicado para derribar al oponente es tan importante como resolver el problema en el que su mente trabaja más en las condiciones límite.

A modo de resumen, estos son algunos puntos clave:

1. Lea todos los problemas, seleccione el problema en orden: fácil a difícil (si todos están resolviendo un problema seleccionado, échele un vistazo)
2. Bosqueje los algoritmos, la complejidad, las condiciones, las estructuras de datos y los detalles complicados
3. Haga una lluvia de ideas sobre otros algoritmos posibles (si los hay), luego elija el más estúpido que funcione
4. Haz todas las matemáticas y selecciona el mejor algoritmo.
5. Codifíquelo, lo más rápido posible, y debe ser correcto.
6. Intente romper el algoritmo: busque casos de prueba de límite.

El mantra principal para tener éxito en un problema es mantener la calma, administrar su tiempo y tener un enfoque estratégico, descansar su experiencia y la práctica juega el papel.

 ¡¡ Sigue practicando !!

Este artículo está escrito por Vinay Garg. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@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.