Competencia más intelectual: Campeonato mundial de programación

El bloguero de Livejournal, Sergei Mukhamedov, escribe: El otro día, un corresponsal de Nedosmi estuvo en un evento internacional muy importante y casi secreto. No encontrarás fotografías suyas en Internet, salvo la presentación de la copa o, en el mejor de los casos, planos generales, aunque se lleva realizando desde 1977. Ni siquiera intentes adivinar qué es sin mirar debajo del corte: el año del primer campeonato seguramente te confundirá.

(Total 37 fotos)

Fuente: Revista/ottenki-serogo

1. Estadio deportivo. Ciento veinte equipos. Público. Dos cámaras de televisión transmiten en línea. Y... silencio absoluto durante cinco horas.

2. Sin acción, solo un trabajo mental increíble.

3. Es difícil imaginar cómo se realizaban estos concursos hace 37 años. ¿El aritmómetro Felix, la regla de cálculo y un lápiz con una hoja de papel? Las computadoras en ese momento eran del tamaño de una casa o una habitación.

4. Esta es la final del Campeonato Mundial de Programación por Equipos Internacionales ACM ICPC. Por primera vez en la historia, se llevó a cabo en Rusia.

5. Esta es la competencia de programación por equipos más genial del mundo.

6. 35 mil participantes de 2322 universidades de 91 países compitieron para ingresar a esta sala y resolver 11 problemas algorítmicos complejos

7. Estos son los mejores cerebros jóvenes del mundo.

8. A pesar de que todavía están estudiando en las universidades, todos los que han llegado a la final ya están empleados.

9. Comenzaron a seguirlos desde sexto grado, cuando ganaron su primera olimpiada de programación.

10. Ya tienen garantizados salarios de $120.000 al año y acciones en empresas.

11. Y no es en absoluto necesario que estas empresas sean extranjeras

12. En nuestro país se les pagará no menos que en Occidente. Y la motivación de esas personas es completamente diferente.

13. Ya son del mundo entero. Hay muy pocas empresas que puedan cargar constantemente de tareas a programadores de este nivel.

14. Son personas muy complejas. Las acciones de la compañía podrían colapsar por millones de dólares si sus principales desarrolladores se van. Les cuesta crear condiciones de trabajo y es casi imposible armar un equipo en el que puedan trabajar.

15. Las empresas que usa a diario las están esperando: estas son Google, Facebook, Yandex ... Y, por supuesto, nuevas empresas complejas e interesantes. Consideran el trabajo en los bancos "por debajo del pedestal".

16. Pero el concepto mismo del campeonato no implica la caza de empleados. El mismo Yandex, actuando como socio oficial de ACM ICPC, ni siquiera tenía un cartel publicitario en la sala. La empresa conoce personalmente a todos los niños rusos, ucranianos y bielorrusos, gracias a sus programas académicos en los que gastó mil millones (!) de rublos durante seis años.

17. El objetivo principal es diferente: apoyar un entorno en el que los chicos talentosos puedan crecer y desarrollarse.

18

19

20

21

22. Se otorgan balones por problemas resueltos, así como por otros méritos como "El primer equipo en completar la tarea F"

23. En 5 horas, estos chicos con camisetas negras serán los ganadores. Antes de esto, en diferentes composiciones, el equipo de Pererburg de la Universidad Nacional de Investigación de Tecnologías de la Información, Mecánica y Óptica (NRU ITMO) se convirtió en cuatro veces campeón mundial.

24. El segundo lugar lo ocupó el equipo de la Universidad Técnica de Shanghai, el tercero, la Universidad de Tokio.

25. Por ejemplo, la traducción de una tarea de este año. El original, por supuesto, estaba en inglés:

La reciente recesión ha afectado duramente a los lugares de entretenimiento, incluidos los juegos de azar. Existe una competencia feroz entre los casinos, y para atraer jugadores, algunos de ellos comenzaron a realizar promociones especialmente atractivas.

La promoción del casino incluye lo siguiente: puedes jugar todo lo que quieras. Y después de que termine, no importa cuánto haya perdido desde que comenzó, el casino le devuelve el x% de sus pérdidas. Naturalmente, si ganas, te lo llevas todo.

Al mismo tiempo, no hay restricciones en la duración del juego, ni en la cantidad de dinero con la que ingresa al juego, pero puede usar esta promoción solo una vez.

Para simplificar, supongamos que todas las apuestas valen $1 y las ganancias son $2. Ahora digamos que x es 20. Si haces solo 10 apuestas antes de terminar el juego y solo 3 de ellas ganan, entonces tu pérdida total es de $3.2. Si ganan 6 apuestas, sus ganancias serán de $2.

Dados x y p (la probabilidad de ganar una sola apuesta en porcentaje), debe escribir un programa para determinar el pago máximo esperado que puede obtener utilizando cualquier estrategia de juego.

La entrada consta de una única prueba que contiene un porcentaje de retorno x (0 ≤ x < 100) y un porcentaje de probabilidad de ganar p (0 ≤ p <= 50). x y p tienen como máximo dos decimales.

Muestra el pago máximo esperado con un error absoluto de no más de 10 -3

26. Para aquellos que conocen los conceptos básicos de la teoría de la probabilidad y saben cómo programar, la tarea puede parecer simple, pero no lo es: cuando los parámetros se acercan a los límites aceptables, surgen problemas serios ...

27. Así es como Aleksey Dergunov del equipo de la Universidad Aeroespacial del Estado de Samara, que ocupó el puesto 35, describió el campeonato:

Al comienzo del concurso, estábamos muy confundidos. craus y yo pensamos en el problema F durante mucho tiempo: lo entregamos al final de la primera hora, eliminamos algunas soluciones incorrectas en el camino y escribimos una para la que no pudimos encontrar un contraejemplo. Luego resolvimos el Problema D. Sin entender cómo hacerlo, Hohol imprimió las respuestas a las primeras pruebas, pero no extrajo nada. Luego recordé la tarea del timo y escribí exactamente la misma enumeración: resultó que había alrededor de 50 mil candidatos para la respuesta (por supuesto, un especialista de ACM decente debería saber que hay pocos, pero no somos como eso), por lo que el precálculo funciona. Luego llegaron las soluciones a los problemas A y H, que hubo que depurar un poco, ya que nunca aprendimos a escribir la primera vez. Luego resolvimos el problema C: el envío en 3:5x ya era correcto, pero TL-ny: el equipo de tres participantes amarillos no puede escribir maxflow y, por lo tanto, lo copia y pega desde la referencia del equipo, donde solo está el algoritmo Dinits, y incluso con un montón de ArrayList- ov. Reemplazando todas las ArrayList-s con matrices, obtuvimos la aceptación de inmediato. Quedando un poco más de media hora, decidimos que no podíamos resolver J en ese tiempo (debo decir, una tarea muy desagradable, una de esas que odio especialmente, un montón de implementación estúpida y sin sentido), y así intentamos resolver B, pero resultó que era necesario resolver un sistema específico de ecuaciones en O(1), como enseñaron una vez en el tercer año (en realidad, una sorpresa agradable: el conocimiento adquirido y olvidado con éxito en ¡la universidad resultó ser necesaria en ACM ICPC!)

28

29

treinta.

31

32.

33.

34.

35.

36.

37. El día después de la final, el ministro de Defensa ruso, Sergei Shoigu, ordenó encontrar (!) estudiantes de San Petersburgo que se habían convertido cinco veces en campeones mundiales en programación para formar parte del personal de las empresas científicas que se estaban creando en el ejército ruso. Mikhail Kever, Niyaz Nigmatullin y Gennady Korotkevich, terminen sus estudios y aléjense del ministro. Mereces algo más que rellenar ensayos escolares al hijo del jefe de la unidad.