Introducción a la programación de las Olimpíadas. Análisis de problemas de las Olimpíadas.
Población:
- Biblioteca de códigos de indy256 (GitHub)
- Algoritmos y clientes Java de R. Sedgewick y K. Wayne (GitHub)
Libros
Algoritmos (libros de texto clásicos)
- Introducción a los algoritmos / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. — 3ª edición. - Cambridge, MA: MIT Press, 2009. - 1292 p. (sitio web del libro)
- Algoritmos: construcción y análisis / Thomas H. Corman, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. — 2ª ed. - M.: Williams, 2005. - 1296 p.
- Sedgwick R., Wayne K. Algoritmos en Java / Robert Sedgwick, Kevin Wayne. — 4ª ed. - M.: Williams, 2013. - 848 p.
Skiena S. Manual de diseño de algoritmos / Steven S. Skiena. — 2ª ed. - Londres: Springer-Verlag, 2008. - 746 p. (sitio web del libro)
- Skiena S. Algoritmos. Guía de desarrollo / Steven S. Skiena. — 2ª ed. - San Petersburgo: BHV-Petersburgo, 2011. - 720 p.
- programación olimpiada
- Concurso El Arte de la Programación/Ed. por A. S. Arefin. — 2ª ed. — Dhaka: Gyankosh Prokashoni, 2006. — 247 p.
- Halim S. Programación competitiva / Steven Halim, Felix Halim. - Raleigh, Carolina del Norte: Lulu, 2010. - 152 p.
- Dolinsky M. S. Resolución de problemas complejos y olímpicos en programación / M. S. Dolinsky. - San Petersburgo: Peter, 2006. - 366 p.
- Okulov S. M. Conceptos básicos de programación / S. M. Okulov. — 4ª ed. - M.: BINOM, 2008. - 440 p.
- Okulov S. M. Programación en algoritmos / S. M. Okulov. — 3ª edición. - M.: BINOM, 2007. - 383 p.
Porublev I. N., Stavrovsky A. B. Algoritmos y programas. Resolver problemas de la Olimpiada. - M.: Williams, 2007. - 480 p.
- Alekseev A.V., Belyaev S.N. Preparar a los escolares para las Olimpiadas de informática utilizando un sitio web / A.V. - Khanty-Mansiysk: RIO IRO, 2008. - 284 p.
- Brudno A. L., Kaplan L. I. Olimpiadas de Programación de Moscú / Ed. B. N. Naumova. — 2ª ed. - M.: Nauka, 1990. - 208 p.
- Kiryukhin V. M., Okulov S. M. Metodología para la resolución de problemas en informática. Olimpiadas Internacionales / V. M. Kiryukhin, S. M. Okulov. - M.: BINOM, 2007. - 600 p.
- Olimpiadas de Informática de Moscú / Ed. E. V. Andreeva, V. M. Gurovitsa y V. A. Matyukhina. - M.: MTsNMO, 2006 - 256 p.
- Campamentos educativos y de formación en informática en Moscú. Primavera–2006 / Ed. V. M. Gurovitsa. - M.: MTsNMO, 2007 - 194 p.
- Menshikov F.V. Problemas de la Olimpiada en programación / F.V. - San Petersburgo: Peter, 2006. - 315 p.
- Características de los problemas nacionales en informática / V. I. Berov, A. V. Lapunov, V. A. Matyukhin, A. E. Ponomarev. - Kirov: Triada-S, 2000. - 160 p.
- Shen A. Programación: teoremas y problemas / A. Shen. — 2ª ed. - M.: MTsNMO, 2004 - 296 p.
Literatura por tema
Algoritmos y estructuras de datos.
- Erickson J. Algoritmos / Jeff Erickson. - Urbana, IL: Universidad de Illinois en Urbana-Champaign, 2015. - 514 p.
- Sedgewick R., Flajolet P. Introducción al análisis de algoritmos / Robert Sedgewick, Philippe Flajolet. — 2ª ed. - Boston, MA: Addison-Wesley, 2013. - 592 p.
- Aho A., Hopcroft D., Ullman D. Construcción y análisis de algoritmos computacionales / A. Aho, J. Hopcroft, J. Ullman. - M.: Mir, 1979. - 536 p.
- Aho A., Hopcroft D., Ullman D. Estructuras de datos y algoritmos / Alfred W. Aho, John Hopcroft, Jeffrey D. Ullman. - M.: Williams, 2000. - 384 p.
- Babenko M. A., Levin M. V. Introducción a la teoría de algoritmos y estructuras de datos / M. A. Babenko, M. V. Levin. - M.: MTsNMO, 2016. - 144 p.
- Wirth N. Algoritmos y estructuras de datos / N. Wirth. - M.: Mir, 1989. - 360 p.
- Dasgupta S., Papadimitriou H., Vazirani U. Algoritmos / S. Dasgupta, H. Papadimitriou, U. Vazirani. - M.: MTsNMO, 2014. - 320 p.
- Kleinberg J., Tardos E. Algoritmos: desarrollo y aplicación / John Kleinberg, Eva Tardos. - San Petersburgo: Peter, 2016. - 800 p. (diapositivas de la conferencia)
- Algoritmos de Levitin A.V.: introducción al desarrollo y análisis / Ananiy V. Levitin. - M.: Williams, 2006. - 576 p.
- McConnell J. Análisis de algoritmos. Curso introductorio / J. McConnell. - M.: Tekhnosfera, 2002. - 304 p.
- Stevens R. Algoritmos. Teoría y aplicación práctica / Rod Stevens. - M.: E, 2016. - 544 p.
Matemáticas discretas
- Asanov M. O. Baranovsky V. A., Rasin V. V. Matemáticas discretas: gráficos, matroides, algoritmos / M. O. Asanov, V. A. Baranovsky, V. V. Rasin. - San Petersburgo: Lan, 2010. - 368 p.
- Graham R., Knuth D., Patashnik O. Matemáticas concretas. Fundación de la informática / R. Graham, D. Knuth, O. Patashnik. - M.: Mir, 1998. - 703 p.
- Cook D., Baze G. Matemáticas informáticas / D. Cook, G. Baze. - M.: Nauka, 1990. - 384 p.
- Novikov F. A. Matemáticas discretas para programadores / F. A. Novikov. — 2ª ed. - San Petersburgo: Pedro. 2007. - 364 págs.
- Okulov S. M. Matemáticas discretas. Teoría y práctica de la resolución de problemas en informática / S. M. Okulov. — 2ª ed. - M.: BINOM, 2012. - 422 p.
- Haggarty R. Matemáticas discretas para programadores / R. Haggarty - M.: Tekhnosphere, 2004. - 320 p.
Geometría computacional
- Geometría computacional: algoritmos y aplicaciones / Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. — 3ª edición. - Berlín: Springer-Verlag, 2008. - 386 p.
- Andreeva E. V., Egorov Yu. E. Geometría computacional en el plano / E. V. Andreeva, Yu. // Ciencias de la Computación. - 2002. - N° 39, 40, 43, 44
- Preparata F., Sheimos M. Geometría computacional / F. Preparata, M. Sheimos. - M.: Mir, 1989. - 478 p.
"...aquí, a las doce de la noche de Nochevieja, después de haber atravesado la tormenta de nieve, vino gente que estaba más interesada en terminar o empezar de nuevo algún trabajo útil que en ahogarse en vodka, patalear sin sentido, jugar pérdidas y participando en varios grados de facilidad para coquetear... Eran magos porque sabían mucho, tanto que la cantidad finalmente se convirtió en calidad, y comenzaron a tener una relación con el mundo diferente a la de la gente común”.
A. y B. Strugatsky.
“Hoy en día es generalmente aceptado
el de todo lo relacionado con el arte de una forma u otra,
ya nada puede considerarse universalmente aceptado”.
Theodor Adorno
Todo comenzó con una persona que intentaba encontrar la solución a un problema en un concurso que se estaba llevando a cabo en ese momento. La tarea era muy sencilla, era obvio para todos que esta persona no ocuparía un buen lugar, no recibiría camiseta, etc. Sin embargo, ninguno de los más de 5000 miembros de la comunidad dio una sola pista (o al menos de las más de 30 personas que lo vieron y supieron la respuesta). Este resultado me pareció natural durante mucho tiempo y traté de explicarlo en pocas palabras. Ahora lo intentaré con un poco más de detalle. Pido disculpas de antemano a las personas que interpretan este concepto de manera diferente a mí. Sólo quería expresar mi punto de vista.
Primero, un poco de teoría de Wikipedia: programación, olimpíadas de programación, art. Tenga en cuenta que el último artículo dice: "El concepto de arte es extremadamente amplio: puede manifestarse como una habilidad extremadamente desarrollada en un campo particular".
Siempre me pareció que la programación es una especie de arte. Hay un área estrecha: la clase de problemas de las Olimpiadas en programación. La capacidad de resolver problemas de forma rápida y precisa es similar a la de los deportes, y la programación de los Juegos Olímpicos a menudo se llama deportes, porque aquí, como en los deportes, primero entrenas durante varios años, luego actúas una vez, tiras todo y te olvidas de la programación, logras algunos resultados. y disfrútalos. Pero por otro lado, el deporte no es una actividad muy creativa. Normalmente, las estrategias no son elaboradas por los principales participantes y no brillan con originalidad y belleza. Pero en programación no es así.
Nadie argumentará que la poesía es arte. Pero ¿qué son los poemas? Los poemas son la capacidad de poner tus pensamientos en un marco claro de ritmo y rima, estilo y vocabulario. Existen muchas restricciones que le impiden simplemente indicar lo que quiere. ¿Por qué lo son? Esto agrega belleza y gracia al verso, muestra que el autor se ha esforzado en expresar sus pensamientos de esta manera, en consecuencia, estos pensamientos han sido cuidadosamente pensados por el autor, pulidos y dados forma material en forma de verso. Además, el lenguaje del pensamiento es muy diferente de casi todos los lenguajes del mundo, ya sea el lenguaje de las palabras, el lenguaje de las imágenes, el lenguaje de los sonidos o el lenguaje de la arquitectura.
La situación es similar con la programación. Si un autor quiere escribir poesía, necesita imaginar un pensamiento y luego crear un poema que exprese ese pensamiento. Para resolver un problema, primero es necesario encontrar una solución y luego, sucesivamente, convertirla en un algoritmo y luego en un programa en un lenguaje de programación. Pero el lenguaje de programación no encaja bien con el lenguaje del pensamiento, por lo que debemos buscar la manera de expresar nuestros pensamientos a través de este lenguaje. Y año tras año mejoramos esta habilidad creando obras de arte cada vez más perfectas.
Aquí ves un tablero en la casa de la creatividad de la ciudad. En la parte superior del tablero, en letras pares está escrito “Exposición de dibujos infantiles”, y debajo de la inscripción se representan, no tan suavemente, varios episodios de la vida de los niños. Intenta responder: ¿es esto arte? Mi respuesta es sí, absolutamente. Estos niños han encontrado su propia manera de comunicarse con el mundo, de mostrarle sus pensamientos. Incluso si son muy primitivos y están representados de manera tosca (aunque sucede de diferentes maneras, algunos niños son capaces de realizar obras maestras con las que los artistas adultos nunca habrían soñado), pero esto es arte. Quizás algún día uno de estos niños pinte cuadros legendarios y gente de todo el mundo venga a verlos. Todo empieza poco a poco.
Me gustaría que estas sociedades fueran una especie de clubes sobre el arte de la programación (como, por ejemplo, Budutlyans), en los que las personas se comunican, comparten secretos, crean juntas, ayudan a los principiantes, pero nunca hacen pasar los pensamientos de otras personas como propios. .
Mantendré una lista de buenos comentarios y adiciones.
Esta sección está destinada a usuarios que empiezan a dominar la programación y sirve como introducción al campo de la programación de Olimpíadas. Si aún no sabes qué son los problemas de la Olimpiada, cómo se presentan y qué criterios de evaluación existen para comprobar las soluciones, entonces esta sección es para ti.
A diferencia de los programas ordinarios creados por programadores todos los días, la clase de problemas de la Olimpiada es bastante limitada, pero práctica en términos de criterios para identificar la capacidad de los participantes para programar en poco tiempo. Como regla general, una tarea olímpica representa algún tipo de problema, cuya solución requiere usar su coeficiente intelectual casi al límite; sin embargo, el texto del programa en sí puede ser bastante insignificante y caber en una sola página.
Si una persona no ha estado involucrada en programación, entonces probablemente podrá evaluar sus habilidades en esta área si la estudia. Mucha gente cree que la capacidad de programación está asociada con la capacidad de resolver problemas matemáticos y combinatorios. En otras palabras, si obtuviste una A sólida en álgebra, geometría y otras disciplinas matemáticas en la escuela, y también sabes jugar bien a las damas y al ajedrez, entonces es probable que seas un buen programador si comienzas a hacerlo. Y viceversa, si en la escuela obtienes una C en álgebra, no importa cuánto lo intentes, es poco probable que programar sea lo que debas hacer. También cabe señalar que tus méritos en el campo del dominio de temas humanitarios te ayudarán poco a dominar la programación, que, como ya entiendes, pertenece a las ciencias exactas.
Aquí hay una clasificación condicional de los problemas de la Olimpiada:
- Aritmética- problemas matemáticos, trabajo con números grandes (aritmética larga), tales tareas, por regla general, requieren conocimiento de fórmulas, la capacidad de aplicarlas y el código del programa puede ser pequeño
- Geometría- problemas geométricos, aquí se puede describir cualquier situación de interacción de cuerpos en un plano y en el espacio
- Programación dinámica- tareas destinadas a identificar relaciones recurrentes
- Clasificación y secuencias- trabajar con datos presentados en forma de matriz
- Graficos- problemas con gráficos (estructuras de datos basadas en vértices y aristas)
- recursividad- tareas de búsqueda con enumeración recursiva de opciones
Por supuesto, las tareas pueden combinar varias áreas a la vez y, a menudo, resulta difícil asignar una tarea específica a una u otra sección.
Cualquier tarea de la Olimpiada implica entrada y salida de datos. Aquellos. la formulación de la tarea describe necesariamente el formato de los datos de entrada y salida, y su programa debe leer estos datos, procesarlos y generar el resultado en el formato establecido. La mayoría de las veces, la lectura se produce desde algún archivo INPUT.TXT y la salida a algún archivo OUTPUT.TXT. Aquellos. Para resolver los problemas de la Olimpiada es necesario poder trabajar con archivos: leerlos, crearlos y escribirlos, pero es poco probable que el conocimiento de las funciones gráficas le resulte útil. Vale la pena señalar que muchos sistemas, por ejemplo http://acm.timus.ru, utilizan el modo de E/S de consola y no se recomienda trabajar con archivos. Este sitio le permite enviar tareas tanto utilizando los archivos mencionados anteriormente como sin ellos. Tú eliges la opción de entrada/salida. Además de las condiciones de la tarea, las reglas para ingresar y enviar información, cada tarea está sujeta a restricciones en el tiempo de ejecución y la RAM utilizada por su programa.
Demos un ejemplo de la formulación de un problema de Olimpíada de programación (Tarea No. 1 en el sistema actual de la sección Archivo de problemas):
A+B
(Tiempo: 1 seg. Memoria: 16 MB Dificultad: 2%)Necesitas sumar dos números enteros A y B.
Datos de entrada
La única línea del archivo de entrada INPUT.TXT contiene dos números naturales separados por espacios que no superan 10 9.
Imprimir
En una sola línea del archivo de salida OUTPUT.TXT necesita imprimir un número entero: la suma de los números A y B.
Ejemplo
| № | ENTRADA.TXT | SALIDA.TXT |
|---|---|---|
| 1 | 2 3 | 5 |
Este problema clásico y sencillo se utiliza para familiarizar a los participantes con el sistema de verificación automática y cumple con todos los criterios para plantear correctamente el problema de la Olimpiada. Para resolver este problema, necesita contar 2 números enteros del archivo de entrada input.txt (o del teclado), ubicado en la carpeta actual (donde está su programa), y mostrar su suma en el archivo de salida output.txt (o en la pantalla). Limitaciones de memoria de 16MB y tiempo de 1 segundo. muy condicional, ya que una tarea tan simple requerirá una memoria mínima y se completará en un período de tiempo mínimo (la operación de suma se realizará instantáneamente; las computadoras modernas son capaces de realizar 10 8 operaciones de este tipo por segundo). Cada tarea tiene un ejemplo de datos de entrada y salida (a menudo incluso varios ejemplos), esto permite a los participantes comprender más claramente el contenido de la tarea. En este ejemplo, la sección "Ejemplo" muestra un ejemplo de datos de entrada "2 3" y datos de salida "5", esto significa que 2+3=5.
Dependiendo de las reglas del concurso o del sistema de pruebas, se podrán utilizar determinados lenguajes de programación. Las herramientas más utilizadas para crear programas se enumeran en la sección "Distribuciones", desde donde puede descargarlas e instalarlas en su computadora.
En el mundo se da preferencia al lenguaje C++, pero en Rusia Pascal sigue siendo el lenguaje de programación clásico, es decir, la mayoría de los problemas de las Olimpíadas en Rusia se resuelven en Delphi. Recomendamos dominar el lenguaje C++, que con el tiempo se convertirá en el más popular en nuestro país. En lo que sigue, utilizaremos principalmente el lenguaje C++ para considerar ejemplos de resolución de problemas. Puede familiarizarse con varios entornos de desarrollo de programas C++ utilizando el ejemplo de resolución del problema "A+B".
Ahora puede familiarizarse con el funcionamiento del sistema y enviar la tarea "A+B" en este sitio web. Se pueden encontrar otras tareas en el "Archivo de tareas" y en "Cursos". Es posible realizar una transición rápida al número de tarea desde la página principal utilizando la sección "Búsqueda del sitio" si ingresa "#N" o "№N" (sin comillas) en la barra de búsqueda, donde N es el número de tarea.
En el cuarto año, nuestro equipo provincial (Orel STU) llegó a la final del ACM ICPC. Fue, por decirlo suavemente, un éxito fabuloso; después de todo, nunca habíamos arrancado estrellas del cielo y la selección fue más seria que ahora. Para nuestra inquietante alegría, se produjo una revolución en Egipto, que se convirtió en el motivo del traslado de la final de Sharm El-Sheikh a la ciudad de Orlando, en los soleados estados de América.
Y ahí fue donde ocurrió esa breve conversación. Una noche, en la zona de descanso, estábamos charlando con Misha Levin sobre la unidad de baile, cuando de repente se acercó Seryozha Chernyshev, desconocido para mí en ese momento, y, reconociendo al último participante por su camiseta, preguntó: "¿Quieres unirse a nosotros en Yandex? ¿Por qué negarse? =)
Todo resultó sorprendentemente sencillo. Intercambiamos un par de cartas. Resolvimos algo de burocracia: completamos un formulario, acordamos las fechas. Terminé teniendo un jefe formal y varios reales a la vez.
El programa de prácticas de verano me vino perfecto: llego en pleno verano, me proporcionan comida y alojamiento, hago prácticas durante dos meses y medio y a finales de septiembre vuelvo a Bird City para Terminar mi último año y defender mi diploma.
Es curioso, pero el primer día "laborable" coincidió con el cierre de ShAD y el resumen del algoritmo Yandex. Así que de todos modos vendría a Moscú. =) Disfruté mi jornada laboral. Hasta las cuatro de la tarde estuve con mis amigos olímpicos en Extropolis y comí brochetas de pollo. Sin salir del edificio, recibí una placa con una inscripción seria: “Departamento de Desarrollo”.
En general, cabe señalar que estaba seriamente preocupado. ¿Cuándo, cuándo me asignarán mi primera tarea? ¿Mis escasos conocimientos sobre las Olimpiadas serán suficientes para afrontarlo? Dos meses y medio es bastante, así que esperaba, si no un galope europeo, al menos un modo de vals.
Sin embargo, nadie se rascó siquiera. Bueno, supongo que eso pensé. Lyosha Mirzoyan me tranquilizó con distintos grados de éxito: “¿Qué estás haciendo? Durante la primera semana, conoce a tu jefe, a los chicos y a la oficina. ¡No te molestes! En general, el final del día lo pasamos alternativamente en el billar y en la sala de música. ;)
La mayor sorpresa fue mi vecino de al lado. Sasha Prudaev, con quien durante un par de años discutimos los problemas de la Olimpiada en ICQ, se mudó de la lejana Tyumen a la capital. Y él fue a trabajar dos días antes que yo. ¡Esta es la noticia, esta es la reunión! Mi otro vecino resultó ser Daniil Burdakov, un tipo muy inteligente con quien ahora nos encontramos a menudo en ShAD. Por tanto, el grupo encontró lo que necesitaba. Vivíamos a dos minutos a pie de Nagornaya y, teniendo en cuenta que la carretera de circunvalación del Parque de la Cultura estaba cerrada por reparaciones, estuvimos unos cuarenta minutos en el camino de ida.
Al día siguiente tenía una computadora portátil en mis manos. Con Windows. Esto ya es genial, porque nunca he usado Linux en mi vida. La dirección eligió la tarea con todo su corazón. Tuvimos que aprender de alguna manera a comparar documentos en busca de similitud, introducir una definición de similitud y hacerlo todo lo suficientemente rápido; bueno, suponiendo que tenemos más de 10 ^ 9 documentos.
Pero hablemos de todo en orden. Me inscribí en el proyecto de prácticas de Yabrakadabra, donde trabajaron en un nuevo motor de búsqueda desde cero. En base a él, podrá estudiar y demostrar con confianza la arquitectura de cualquier motor de búsqueda, explicar los principios de recuperación de información, etc., etc.
En teoría, no todo daba mucho miedo. En la práctica fue aterrador. Me cayeron tantas cosas terriblemente desconocidas que ni siquiera tuve que usar Git; junto con los muchachos, descargué el repositorio solo una vez y luego hice todo localmente. De cara al futuro, diré que el último día de la pasantía de verano le envié mi código por correo electrónico a mi jefe, en lugar de implementar algo en alguna parte. Probablemente, personas con experiencia leyendo estas líneas estén rodando por el suelo riendo, agarrándose el estómago.
Casi de inmediato me di cuenta de que hay dos problemas en la programación industrial: la programación orientada a objetos y los nombres de variables. Con dolor y la ayuda de Dios, habiendo descompuesto el problema, comencé a buscar una solución. Los chicos me recomendaron varios artículos en inglés, prácticamente desconocido para mí en ese momento, sobre simhash y minhash. Pero, ¿qué debería hacer un verdadero atleta olímpico? ¡Por supuesto, inventa algo propio! (Lo único que falta es el cómic del trapeador).
Leí los artículos y pensé durante aproximadamente una semana. Por supuesto, sin dejar de conocer su entorno. Los días de trabajo se alegraban con una bonita oficina y reuniones en cafeterías con Sasha Prudaev y otros programadores deportivos. Entonces se produjo un punto de inflexión del que todavía estoy orgulloso: se me ocurrió una solución. Fue en un tren subterráneo, según recuerdo ahora. =) La práctica posterior demostró que ciertamente no era peor que los análogos, que aún tenían que implementarse para construir gráficos y convencer a las autoridades.
Como resultado, para mi primera revisión "envié" algo que constaba de más de 300 líneas de código. En mi defensa, puedo decir que estas más de 300 líneas resolvieron completamente el problema. =)
Los chicos estaban histéricos. Artyom Babenko lloró lágrimas de sangre y dijo que no aceptaría mi código más de cinco veces. Otro momento tremendamente divertido fue que en la copia impresa (y la reseña fue así: imprimí el código y fuimos a leerlo entre la multitud) en la parte superior hay una ruta como ".../cadabra/kpr /hash.cpp”. Respondí en consecuencia a la pregunta correspondiente y Artyom me recordaba "Kuprinkhash" durante mucho tiempo y regularmente con lágrimas en los ojos. .
Posteriormente, mi código creció y se expandió. Fue algo estúpido y extraño, considerando que la funcionalidad no cambió. Cinco veces se agotaron rápidamente y otro jefe, Yegor Samosvat, pasó una parte importante de su tiempo conmigo. Aunque me sentía como un idiota y no parecía más inteligente, me gustaba lo que estaba pasando. De hecho, estudié en condiciones cómodas y combativas.
Ha llegado el momento del campamento de verano en Petrozavodsk, donde pedí ir a Yandex para difundir luz y bondad (tachado) para poder hablar sobre los placeres de una pasantía de verano. La gente no reaccionó de muy buena gana, y luego me acordé de mí mismo en mi tercer año: un verdadero estudiante de la Olimpiada estudiará los problemas de la Olimpiada sin cesar. Bueno, señores, llegará su momento. ;)
Mientras tanto, nos mudamos a otro apartamento, en Belorusskaya. La estación Park Kultury todavía estaba cerrada y, al final del segundo mes de prácticas, mi rutina finalmente desapareció. Simplemente me daba pereza pasar una hora y media al día viajando, así que pasaba casi todo el día y la noche en la oficina, durmiendo en suaves sacos de dormir, hamacas y pufs. Fue realmente genial. Logré pasar mucho tiempo en la sala de música; pasé las noches atormentando el sintetizador y las guitarras. Caminar por la oficina de noche dejaba perplejos a los guardias, ¡pero qué ambiente!
Mientras tanto, el trabajo poco a poco iba llegando a su fin. "Kuprinhash" adquirió un nuevo nombre - FirstLetterHash, creció de un archivo a una docena, tiene nuevas funciones y hermanos que tienen la misma interfaz, se han recopilado estadísticas sobre la solicitud "problemas de existencia" y mucho, mucho más.
Me parece que, en general, lo logré. Aunque no fue tan bueno como podría haber sido, lo logré. Para no perder contactos, me prometieron llevarme a un trabajo remoto en algún lugar durante el invierno.
Y en mi universidad de origen, las discusiones y batallas estaban en pleno apogeo sobre los temas de las tesis. Habiendo acordado previamente con los chicos de Yandex, logré convencer al director de tesis del patetismo sin fin y la aplicabilidad práctica de FirstLetterHash. Así que, en cierto modo, tenía el diploma en el bolsillo; lo único que faltaba era añadir agua a la nota explicativa, lo que resultó ser cuestión de un par de semanas.
El 1 de febrero “volví” a trabajar. Aquí es donde necesitaba git, putty y muchos otros placeres de la vida previamente desconocidos. La tarea volvió a resultar grandiosa. Esta vez, utilizando palabras clave, fue necesario construir un fragmento: una pequeña unión de fragmentos de texto fuente que contendría simultáneamente muchas palabras clave y sería percibido por una persona como extractos de un documento, y no como un fragmento de frase.
¡Programación dinámica al rescate! La solución esta vez resultó ser prácticamente superficial; la cuestión eran las limitaciones de tiempo y memoria. La jornada laboral de dos horas resultó ser un formato repugnante, por lo que normalmente elegía una semana del mes durante la cual trabajaba fructíferamente y el resto del tiempo me dedicaba a mis asuntos.
Me sentí como si me dejaran solo y fue muy relajante. Y, aunque honestamente completé la tarea, probé y me comprometí, me parece que fui un aprovechado. En algún momento entre abril y mayo, cuando se completó el 90% del trabajo, dejaron de llegar tareas razonables, y aquí la lógica era bastante simple: no podré hacer frente a una nueva gran tarea, pero todavía hay tiempo.
Después de defender con éxito mi tesis, ingresé a la maestría en HSE en un programa combinado con Yandex ShAD, es decir, de hecho, fui a estudiar a dos lugares a la vez. La atenta HSE instaló a los futuros amos en un tranquilo y acogedor pueblo forestal llamado Dubki, por lo que le agradecemos mucho. Casi de inmediato llegué a la conclusión de que cinco horas de viaje al día se pueden cambiar por una jornada laboral a tiempo parcial y vivir cerca de la oficina.
Muy pronto surgió una gran oportunidad: en la conferencia ShAD, mi amigo Pasha Shishkin, medallista de oro del ACM ICPC, anunció que Yandex.Images estaba buscando un desarrollador. ¡Hurra, aquí está, mi oportunidad!
Pronto tuvo lugar una entrevista, durante la cual respondí las preguntas de una prueba llamada “Prueba Pure Evil C++ 2” con gran dificultad. Por alguna razón, solo en el segundo intento resolví correctamente un problema simple en teoría, pero me mataron por completo. por la velocidad de escribir un problema algorítmico en un estilo industrial.
Es cierto que no había ningún puesto a tiempo parcial, solo a tiempo completo. Pero quizás sea incluso mejor así. En las fotos estoy desde el 1 de octubre, han pasado exactamente cinco meses. Y desde dentro siento que todo es realmente genial.
Y así, con una breve conversación, comenzó el camino del estudiante de la Olimpiada hacia la programación industrial. Y estoy seguro de que esto es sólo el comienzo. Así que muchachos, adelante, estudien, entrenen y ¡seguro que todo saldrá bien!
¡Hola!
Le escribe un alumno de noveno grado, ganador de la etapa regional de la Olimpiada Panrusa de Informática. Recientemente, comencé a notar que ha aumentado el interés de los lectores por los concursos de programación. Como participante activo, intentaré responder todas las preguntas, hablar sobre mi camino y dar ejemplos de tareas reales que recuerdo.
Sobre la formación
Estudio en una escuela con estudios en profundidad de física, matemáticas e informática.
¿Qué tipo de escuela es ésta, cómo estudiar en ella y cómo matricularse?
La selección se realiza en dos etapas. El primero es un examen de física y matemáticas. Luego, algunos estudiantes afortunados van a una entrevista, donde se les pide que resuelvan varios problemas de Olimpiada en matemáticas. Y sólo después de esto los más inteligentes y afortunados se convierten en estudiantes.
Estudiar es muy duro y difícil. Los profesores requieren un conocimiento perfecto de casi todas las materias. En la reunión de padres dijeron: “Al comienzo de sus estudios, absolutamente todos los estudiantes bajan al segundo grado, incluso los estudiantes excelentes. Los que empiezan a estudiar de verdad obtienen buenas notas. El resto queda eliminado." Tuve más problemas con la lengua y la literatura rusas, por extraño que parezca.
Siempre me ha atraído la programación (me di cuenta de lo que era ya en cuarto grado). Me alegré mucho cuando empezaron a enseñar Pascal y varios algoritmos informáticos en séptimo grado. Fue entonces cuando escribí el primer "¡Hola Mundo!", el algoritmo de Euclides; Estudié declaraciones condicionales, bucles y matrices.
Desde octavo grado, los profesores nos invitaron a asignaturas optativas de informática, donde estudiamos gráficos, algoritmos de clasificación de matrices y mucho más.
Tareas
Veamos una tarea completamente típica para programadores novatos de la Olimpiada.
¡Cinco cinco son veinticinco!
(Tiempo: 1 seg. Memoria: 16 MB Dificultad: 8%)
Vasya y Petya estudian en la misma clase en la escuela. Recientemente, Petya le contó a Vasya acerca de una forma inteligente de elevar al cuadrado números naturales que terminan en 5. Ahora Vasya puede elevar fácilmente al cuadrado números de dos dígitos (e incluso algunos de tres dígitos) que terminan en 5. El método es el siguiente: elevar al cuadrado un número que termina en 5, basta con multiplicar el número obtenido del original tachando los últimos cinco por el siguiente número en orden, luego solo queda sumar “25” al resultado resultante de la derecha. Por ejemplo, para elevar al cuadrado el número 125, basta con multiplicar 12 por 13 y sumar 25, es decir sumando el número 25 al número 12*13=156, obtenemos el resultado 15625, es decir 1252=15625. Escribe un programa que eleve al cuadrado un número terminado en 5 para que Vasya pueda poner a prueba sus habilidades.
Datos de entrada
La única línea del archivo de entrada INPUT.TXT contiene un número natural A que termina en 5, sin exceder 4*105.
Imprimir
En el archivo de salida OUTPUT.TXT, genere un número natural: A2 sin ceros a la izquierda.
Ejemplos:
ENTRADA.TXT
5
75
4255
SALIDA.TXT
25
5625
18105025
Requisitos
El participante de la Olimpiada debe escribir un programa en uno de los lenguajes aceptados (generalmente este conjunto consta de Pascal (lo escribo yo mismo, nunca tuve ningún problema), Delphi, C++, Java, Visual Basic, y C# se agregó recientemente ). Luego, el archivo fuente se envía al sistema sandbox, donde se compila y ejecuta en un grupo de pruebas. Por cada prueba, el participante de la Olimpiada recibe un punto determinado, que luego se suma. Después de los Juegos Olímpicos, los resultados se vuelven visibles para todos. Cuanto mayor sea la puntuación total, mayor será el lugar.
Vale la pena señalar que, por lo general, los sistemas de verificación procesan mal el código administrado (Java, C#). Mi amigo personalmente recibió 0 puntos en tres de cada cuatro tareas en la etapa regional debido a un error de ejecución (escrito en C#), aunque todo se verificó normalmente. Ni él ni yo entendimos qué hacer en este caso; En la apelación, el jurado simplemente se encogió de hombros.
Riesgos
¿En qué puedes perder? Hay 7 tipos de errores:
Texto oculto
respuesta incorrecta
Respuesta incorrecta. El resultado del programa no coincide con la respuesta del jurado.
Formato de salida no válido o error algorítmico en el programa
Límite de tiempo excedido
Se ha superado el límite de tiempo especificado en la tarea. El programa dura más que el tiempo establecido.
Solución ineficaz o error algorítmico en el programa.
Error de presentación
Falta el archivo de salida OUTPUT.TXT
El archivo no se creó, el nombre del archivo es incorrecto o el programa falló antes de abrir el archivo de salida.
Error de compilación
Error de compilación. Como resultado de la compilación, no se creó ningún archivo ejecutable.
Hay un error de sintaxis en el programa o la extensión del archivo es incorrecta. Es posible que se haya utilizado una clase distinta a Main en la implementación de Java.
Límite de memoria excedido
Se ha excedido el límite de memoria especificado en la tarea. El programa está utilizando más del tamaño de memoria configurado.
Algoritmo ineficiente o uso irracional de la memoria.
Error de tiempo de ejecución
Error de ejecución. El programa salió con un código de retorno distinto de cero. En este caso, no se comprueba el resultado del trabajo.
Quizás el programa accedió a un elemento de matriz inexistente, dividido por cero, etc. Es posible que el programa C++ no termine con una declaración "devuelve 0", o puede devolver un código de retorno distinto de cero.
Juegos Olímpicos
¿Cómo va la Olimpiada Panrusa de Informática?
Pasé solo por 5 etapas: 8-9 grados en la escuela, 8-11 grados en la escuela, etapa municipal, gira a distancia de la Olimpiada regional, Olimpiada regional. Luego viene la gira por toda Rusia, pero, lamentablemente, no pude participar. Ahora les contaré las tareas que realmente me gustaron.
Etapa entre los estudiantes de secundaria.
Durante el recorrido, entre los grados 8-11 se realizó la tarea “Funciones hash polinómicas”, cuya condición estaba escrita en dos páginas A5. En esta condición, se proporcionó información breve sobre las funciones hash, su historial y se propuso una de esas funciones. La tarea consistía en calcularlo para una serie de datos de entrada. Nos asustó el nombre tan aterrador, la terminología compleja, registrar la cantidad con su ícono (el que se parece a la letra E) y como resultado, pocas personas siquiera comenzaron a resolverlo. Desafortunadamente, no puedo encontrar la condición ahora.
escenario municipal
La etapa municipal resultó ser simplemente mortal en complejidad.
Aquí está la tarea desde allí.
B. castor
Límites de memoria: 64 MB
El castor va a construir una cascada de represas y una acogedora cabaña en el lecho de un estrecho río. Sucede que el río fluye a lo largo de un camino perfectamente recto y el ancho del río es tan pequeño que para los propósitos de este problema podemos ignorarlo. Hay árboles en las orillas del río que el castor puede utilizar para construir. Los científicos decidieron descubrir qué tan óptimo es el castor para elegir los lugares para construir presas y refugios en términos de la distancia mínima total a lo largo de la cual deben moverse los árboles.
Escribe un programa que, dadas las coordenadas de los árboles con respecto al inicio del tramo recto del río, si consideramos que el eje es codireccional con el flujo, determine las coordenadas de los objetos correspondientes a la distancia total mínima a la que los árboles deben ser movidos.
Formato de entrada:
<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Formato de salida:
Para cada bloque de prueba, en una línea separada, debe imprimir un solo número: la suma de las coordenadas de los lugares donde se deben construir los objetos, de modo que la distancia total a lo largo de la cual será necesario mover los árboles para la construcción sea mínima. , indicando tres dígitos exactos después del separador decimal.
Datos de entrada
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Imprimir
7.300
1.000
Resolver el problema si solo hay un objeto es bastante sencillo. Pero cuando hay más objetos, hay que utilizar una sección de programación bastante compleja, “Programación dinámica”. El maestro que enseñó nuestra materia optativa admitió que tenía poca idea de cómo resolver este problema (con esfuerzos conjuntos obtuvimos el valor que debe minimizarse simplemente construyendo varios gráficos, ni siquiera preguntes cuál es este valor; convenientemente lo olvidé). ).
Como resultado, sólo un participante de la Olimpiada resolvió el problema con la máxima puntuación.
Y aquí hay otro problema, cuya decisión del jurado fue revisada (de la misma etapa municipal):
A. Albatros
Límites de tiempo: 1 segundo por prueba
Límites de memoria: 64 MB
El albatros puede realizar largos vuelos, cubriendo largas distancias sobre el océano. Los ornitólogos decidieron determinar cuántos kilómetros puede volar un albatros sin visitar tierra. Para ello, una flotilla de laboratorios de investigación flotantes se dispersó por el océano y registró datos sobre el individuo estudiado, al que se le colocó una etiqueta de radio. Los científicos registran el momento y las coordenadas actuales del lugar donde descubrieron al albatros.
Escribe un programa que determine la distancia que recorrió el albatros durante el experimento, si asumimos que en la zona de observación nuestro planeta es una esfera ideal con un radio de 6366,197 kilómetros.
Formato de entrada:
La primera línea de la entrada contiene un único número entero positivo 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Formato de salida:
Para cada uno de los bloques de prueba, en una línea separada, debe imprimir un único número entero: la distancia que recorrió el albatros, redondeada al número entero par más cercano.
Ejemplo de datos de entrada y salida:
Datos de entrada
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Imprimir
4
2
Una tarea bastante simple: debes ordenar los valores por fecha de aparición del Albatros, calcular la longitud de cada arco entre dos puntos y luego sumarlos todos. La solución parte de una suposición que permite el uso del teorema de Pitágoras.
Pero ¿por qué se revisó la decisión? Echemos un vistazo al rango de minutos y segundos.
0<=m1<=90, 0<=s1<=90
¿Probablemente asumiste ingenuamente que un grado tiene 60 minutos? ¿O que hay 60 segundos en un minuto? ¡Ja ja! "90" está claramente escrito allí mismo.
Las pruebas se elaboraron teniendo en cuenta la traducción: un grado tiene 60 minutos, un minuto 60 segundos. Esta indignación fue desafiada con éxito por nuestros profesores.
Lo más molesto es que hasta el ejemplo salió mal.
Como resultado, en mi opinión, nadie resolvió el problema en absoluto.
Se puede consultar el texto completo de la fase municipal.
Tour remoto
Las tareas del recorrido a distancia fueron mucho más interesantes. Recuerdo dos tareas.
Aquí está el primero
G. Héroe del día
E/S: estándar
El holding de medios Perm the Great monitorea los mensajes de los bloggers de la región de Perm y todos los días intenta descubrir quién es el más popular en las publicaciones para incluir a esta persona en la tradicional sección "Héroe del día".
Para cada entrada incluida en la lista de seguimiento, se conoce el número de visualizaciones y las personalidades mencionadas en la misma. Escriba un programa que determine la persona para quien el número total de vistas de las publicaciones en las que se le menciona es máximo.
Formato de entrada:
La primera línea de la entrada contiene un único número entero 1<=L<=10000 – количество записей, попавших в обзор за текущий день. В каждой из следующих строк вначале указывается число – количество просмотров соответствующей записи и затем имена и фамилии людей, упоминающихся в записи. Имена и фамилии состоят из букв английского алфавита, число, а также все соседние слова отделяются друг от друга ровно одним пробелом. Суммарная длина строки составляет не более 200 символов.
Formato de salida:
En una sola línea de datos de salida, debe mostrar el nombre y apellido de la persona cuyas publicaciones mencionadas recibieron la mayor cantidad de visitas. Si hay varias personas así, debes seleccionar la que va primero en el alfabeto.
Datos de entrada
1
100500 John Travolta John Lennon
5
5 Vasya Pupkin Sergey Syroezhkin
10Harry Potter
5 Garry Potter Vasya Pupkin
5 Serguéi Syroezhkin
12341234463456234123466543342Arnold Schwarzenegger
Imprimir
John Lennon
Arnold Schwarzenegger
Fue después de esta tarea que se me ocurrió la idea de un “diccionario”, un tipo de datos con una cómoda búsqueda por parte de las personas. Si a alguien le interesa lo escribo en los comentarios, pueden preguntar por MP, pero siento que es la misma moto.
Necesitamos crear una lista de personas con un número total de vistas (mira a la persona con el ID de Arnold Schwarzenegger, requiere mucha aritmética) y luego simplemente seleccionar a la persona deseada de nuestra lista. Para simplificar el algoritmo, nuestros alumnos de undécimo grado utilizaron una función hash para el nombre (la suma de todos los números de caracteres ASCII en el nombre), lo que aceleró significativamente el programa, las colisiones eran pequeñas;
Segunda tarea o tarea de archivo
V. Gran Archivero
E/S: estándar
Límites de tiempo: 1 segundo
En el planeta de los robots, el procesamiento automático de textos es muy popular. Para ello, los robots introdujeron una posición especial del Gran Archivero. Los deberes del Gran Archivero incluyen compilar una lista de todas las palabras del texto y reemplazar las palabras con un número que indique el número de esa palabra en la lista.
Escribe un programa que realice las funciones del Gran Archiver.
Formato de entrada:
Una sola línea de datos de entrada contiene una cadena de no más de un millón de caracteres, que consta de letras minúsculas y mayúsculas del alfabeto inglés y espacios. Dos palabras adyacentes cualesquiera en el texto están separadas exactamente por un espacio. Las palabras se consideran iguales si son iguales en términos de comparación de cadenas, y las letras minúsculas y mayúsculas se consideran diferentes.
Formato de salida:
En una sola línea de salida, debe mostrar la secuencia de números de palabras del texto, y las palabras de la lista deben ordenarse en el orden en que aparecen en el texto. La numeración de palabras debe comenzar con una.
Ejemplos de datos de entrada y salida:
Datos de entrada
Ser o no ser
¿Por qué lloras Willie? ¿Por qué lloras? ¿Por qué Willie? ¿Por qué Willie? ¿Por qué Willie? ¿Por qué?
Imprimir
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Explicación de los ejemplos de entrada y salida: El texto del segundo ejemplo no contiene saltos de línea ni retornos de carro.
Un algoritmo de compresión bastante simple (no recuerdo cómo se llama). Estaba interesado en implementarlo. Resolví este problema creando una serie de palabras y agregando la primera palabra allí. Luego leyó cada palabra siguiente y comprobó si estaba en la matriz. Si había uno, escribía la palabra número en el flujo de salida; de lo contrario, lo agregaba a la matriz y escribía el número.
Básicamente, mi solución no obtuvo la máxima puntuación.
Se puede encontrar el texto completo de las tareas.
Obtuve el 1er lugar entre los alumnos de noveno grado en la ronda a distancia.
Etapa regional
En la fase regional no fue tan divertido, hubo dos rondas. Tenía miedo de decepcionar a la escuela y no pasar a la siguiente etapa, de mostrar mal nuestra escuela. Por tanto, las tareas no se percibían como divertidas y placenteras. En general: no recordaba nada de allí, pero recibí el codiciado diploma. Y no pude encontrar las condiciones.
El segundo día, representantes de la empresa local “Prognoz” vinieron a nosotros y tocaron “¿Qué? ¿Dónde? ¿Cuándo?”, realizó un cuestionario. Los ganadores recibieron premios.
Preparación
¿Cómo me preparé?
La respuesta es bastante sencilla: tengo buenos profesores. Fue interesante para mí y disfruté todo lo que estaba pasando. Me preparé duro y logré lo que quería.
¿Qué hacer si a ti también te interesa esto y quieres participar en todo esto?
- Existen sistemas para preparar a los escolares para la programación de olimpíadas, tienen un sistema de pruebas y un montón de condiciones con soluciones. Según tengo entendido, todos estos sistemas requieren registro. Lo preparé con la ayuda de dos:
- acmp.ru/ Hay muchas tareas de diversa complejidad, la sección "Curso Olímpico" también es interesante.
- http://acm.timus.ru/ Un montón de problemas de una variedad de Olimpíadas, algunos en inglés. En la sección http://acm.timus.ru/offline realizamos etapas remotas y regionales.
- Hay Olimpíadas online, yo sólo participé en una: NetOI de los ucranianos. La reseña es: ¡¡¡DURO!!! No pasó de la segunda ronda. El código debe escribirse de manera muy óptima (no puedo hacerlo), para cada prueba existen condiciones individuales (el doble de tiempo que el programa del jurado).
¿Qué sigue?
Con esto me refiero a la cuestión de qué tan bien se adaptan los atletas olímpicos para trabajar en condiciones reales.
Aunque todavía no he trabajado en la industria de TI, creo que los participantes de la Olimpiada no están adaptados en modo alguno al trabajo real. En tales Olimpiadas, es necesario poder inventar rápidamente una "bicicleta" y tener un buen conocimiento de los algoritmos. Mi amigo y yo escribimos juegos pequeños y entiendo que es mucho más importante poder elegir la tecnología adecuada para nuestros propósitos, poder encontrar una solución preparada para acelerar el desarrollo, "No se necesitan bicicletas". Corrígeme si esto no es cierto.
Si alguien está interesado en lo que quiero en la vida: de hecho, no me gustan mucho las tecnologías de la información y la informática, mi sueño es estudiar física teórica e investigar. Y como en la Federación Rusa hay problemas con esto, planeo ir a Canadá o Estados Unidos.
Aceptaré cualquier deseo en PM o en los comentarios. Espero que este artículo no haya resultado largo. Espero que haya sido interesante para ti. Espero que no te haya molestado mi analfabetismo, realmente no sé muy bien la puntuación.
