Hola, solo quiero explicar la programación competitiva basada en mi experiencia de años compitiendo en ella.
Definición
La programación competitiva es resolver problemas bien definidos escribiendo programas de computadora bajo límites específicos .
Según la definición anterior, la programación competitiva tiene tres aspectos:
- Como extranjero, ¿cómo me involucro en la escena tecnológica de Taipei?
- ¿Qué tecnologías dependen de mediciones precisas de tiempo?
- .NET Framework: ¿Por qué veo tanta prevalencia de puestos en .NET?
- ¿Cuáles son los nuevos productos de Google Home y por qué son importantes?
- ¿Cuáles son algunos conceptos erróneos comunes sobre la tecnología?
- Problemas bien definidos . Se le presenta uno o más problemas. El enunciado del problema contiene variables, y debe poder responder al problema si se le da alguna combinación posible de valores de las variables. El problema estará bien definido: se le informará de las restricciones exactas de todas las variables, cualquier suposición necesaria, etc.
- Programas de computadora . Escribes programas de computadora que resuelven los problemas. Tenga en cuenta que el “programa de computadora” aquí es un programa de línea de comandos muy simple; sin GUI o aplicación web sofisticada, etc. El programa de línea de comandos lee los valores de las variables de la entrada estándar y debe escribir la respuesta en la salida estándar.
- Límites especificados . Su programa debe ejecutarse y producir la respuesta dentro de un límite de tiempo y memoria especificados. Además, debe escribir los programas en un conjunto específico de lenguajes de programación permitidos.
Para hacerlo más claro, ahora echemos un vistazo a un ejemplo de problema de programación competitiva.
Problema de muestra: bolas en canastas
Límite de tiempo: 1 segundo
Límite de memoria: 32 MB
Descripción
Tienes N bolas de colores. El color de la bola i-ésima está representado por el entero C [i]. Quieres llevar las pelotas con cestas. Una canasta puede contener un número ilimitado de bolas. También desea que por cada dos bolas de diferentes colores, estén en diferentes canastas.
¿Cuál es el número mínimo de canastas que necesitas para llevar todas las bolas?
Formato de entrada
La primera línea contiene un solo número entero N. La siguiente línea contiene N separados por espacios C [1], C [2], …, C [N].
Formato de salida
Un solo contiene el número mínimo de cestas.
Entrada de muestra
7 7
1 8 3 8 9 2 1
Salida de muestra
5 5
Restricciones
- 1 <= N <= 100,000
- Para cada i, 1 <= C [i] <= 1,000,000,000
Para aquellos que nunca han hecho programación competitiva: ¿pueden resolverlo? No hay problema, discutiremos la solución más tarde.
Propiedades del problema
Un problema de programación competitivo generalmente tiene estas propiedades.
- La exactitud de una respuesta al problema es absoluta : será revisada por computadoras, no por humanos. No hay subjetividad presente. Por ejemplo, este no es un problema válido: “Si una persona generalmente abre N pestañas de Chrome al mismo tiempo, ¿cuánta RAM debería tener?”
- La descripción contiene una historia de fondo para ocultar el problema real y hacerlo interesante. En este caso, el problema real se disfraza dentro de canastas y pelotas. Sin embargo, tenga en cuenta que algunos problemas también tienen una declaración directa.
- Se darán algunos ejemplos de entrada / salida . Esto es para que no entendamos mal el formato de entrada / salida e incluso la descripción del problema en sí.
- En última instancia, el problema está relacionado con la informática , las matemáticas o la lógica . Por eso, la solución se puede expresar algorítmicamente en un programa de computadora. Incluso la Programación competitiva 3 (libro) (Halim y Halim, 2013) define la programación competitiva como “Dados problemas conocidos de CS (informática), ¡resuélvalos lo más rápido posible!” .
Solución de problemas de muestra
Bien, ahora analicemos la solución del problema anterior, solo por diversión:
- Debido a la regla, una canasta solo puede contener bolas del mismo color.
- Como queremos minimizar el número de canastas, tiene sentido (y óptimo) llevar todas las bolas de un color en particular en una sola canasta.
- Por lo tanto, el número mínimo de canastas es igual al número de colores diferentes de las bolas.
O, en otras palabras, podemos reducir (simplificar) el problema anterior en:
Dada una lista de números, cuente el número de números distintos en la lista.
Ahora puede preguntarse, ¿qué tiene que ver el problema anterior con la informática ? Esto se debe a que tiene que hacer un análisis (por ejemplo, análisis de complejidad ) antes de encontrar un algoritmo para resolver el problema. Existen múltiples formas de escribir un programa que cuenta el número de elementos distintos en una lista, pero solo aquellos que se ejecutan como máximo 1 segundo, consumen como máximo 32 MB de memoria y pueden manejar N hasta 100,000, se considerarán correctos.
La solución real y un código fuente de muestra se pueden encontrar en el primer comentario de esta respuesta. Por favor, pruébelo antes de leer la solución.
Esquema de puntuación
Para cada problema, el jurado proporciona un conjunto de casos de prueba secretos . Cada caso de prueba consta de una entrada válida y la salida correcta para la entrada correspondiente. Los archivos de entrada y salida deben cumplir con los formatos de entrada / salida y las restricciones especificadas en la declaración del problema. Se dice que el programa del concursante pasa un caso de prueba si, cuando se le da la entrada del caso de prueba, produce la misma salida que la salida del caso de prueba.
Como jurado, ¿tenemos que preparar los casos de prueba para todas las combinaciones de N de 1 a 100,000 (y, todas las combinaciones de la lista C, cada elemento puede ser hasta 1,000,000,000)? ¡El número total de combinaciones es tan grande! La respuesta es simple: generalmente no tenemos que hacerlo . Por lo general, solo creamos aproximadamente 20 casos de prueba, que contienen casos de prueba con N pequeño, N grande (st), N generado aleatoriamente y la lista C, y cualquier otra variación complicada.
Su puntaje a un problema depende de las reglas del concurso. En un concurso determinado, su programa debe pasar todos los casos de prueba para recibir puntos por el problema; mientras que en otro concurso, puede recibir puntos parciales dependiendo de cuántos casos de prueba pueda pasar su programa.
Variaciones
Lo que acabo de explicar es la forma estándar de problemas de programación competitivos. Hay algunas variaciones interesantes, por ejemplo:
- No debe enviar el programa, sino solo los archivos de salida. (Se proporcionarán los archivos de entrada del caso de prueba oficial). Este tipo de problema generalmente se denomina problema de solo salida . Un ejemplo de ventaja de este tipo es que el límite de tiempo de este problema se convierte en la duración de todo el concurso .
- Su programa no lee la entrada. En su lugar, debe escribir la implementación de una función / método en particular. La entrada estará disponible como los parámetros de la función. Este es el caso de la Olimpiada Internacional de Informática (IOI) desde 2010 y los SRM de topcoder.
- En caso de problemas de optimización, el jurado ni siquiera tiene la respuesta óptima. En cambio, su puntaje dependerá de qué tan bueno pueda producir su programa. Cuanto mejor sea su respuesta, mayor será su puntaje. Los IOI más recientes tienen este tipo de problema.
- … y muchos otros.
Concursos
Hoy en día, hay muchos tipos de formatos de concurso de programación competitiva. Hay varios criterios. Algunos:
Ubicación
- En línea (por ejemplo, rondas de Codeforces, SRM de codificador superior)
- En el sitio (por ejemplo, concursos locales)
Frecuencia
- Anual (p. Ej., IOI, Google Code Jam, Facebook Hacker Cup)
- Mensualmente (por ejemplo, https://www.codechef.com/ (CodeChef) concursos largos)
- Varias veces al mes (p. Ej., Rondas de Codeforces, SRM de codificador superior)
Duración
- ~ 1 – 2 semanas (p. Ej., Concursos largos de CodeChef, Topcoder Marathon)
- ~ 1-3 días (por ejemplo, ronda de calificación de Google Code Jam)
- 5 horas (por ejemplo, el Concurso internacional de programación colegiada ACM-ICPC (ACM-ICPC), IOI)
- ~ 1 – 3 horas (p. Ej., Rondas de Codeforces, SRM de codificador superior)
Participantes permitidos
- Estudiantes universitarios (p. Ej., ACM-ICPC)
- Estudiantes de secundaria (p. Ej., IOI)
- Cualquiera (por ejemplo, Google Code Jam)
Tipo de participación
- 3 personas por equipo (p. Ej., ACM-ICPC)
- Individual (casi todos los concursos que no sean ACM-ICPC)
Juez en linea
Este término es muy popular en el mundo de la programación competitiva. Es un sitio web que contiene una colección de problemas de programación competitivos, donde puede enviar soluciones libremente, en cualquier momento. Por lo general, no hay una duración específica, a diferencia de los concursos. Las personas generalmente practican su habilidad en jueces en línea.
Algunos jueces en línea bien conocidos:
- Juez en línea de UVa – Inicio, junto con su sitio complementario uHunt :: UVa Hunting.
- ACM-ICPC Live Archive – Inicio, que contiene problemas pasados de ICPC.
- Juez Esfera Online (SPOJ)
- Además, la mayoría de los concursos en línea como Codeforces y Topcoder tienen sus propios archivos de problemas, donde puede enviar libremente soluciones como lo hace en los jueces en línea.
¡Espero que esta respuesta te dé una mejor comprensión de la programación competitiva! 🙂
