Skip to content

progcompuc/IIC2562-2018-2

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

158 Commits
README.md
README.md
 
 

Repository files navigation

IIC2562 - Taller de Programacion II

2018-2

Bienvenidos a la página de apoyo del curso Taller de Programacion II.

Instrucciones del Curso

Este es un curso 100% práctico, orientado a entrenar a alumnos en programación competitiva y preparar equipos que participen en la ACM ICPC (celebrada anualmente) representando a la universidad. Por lo tanto, la nota final dependerá de la resolución por parte del alumno de problemas de programación competitiva. Cada cierto tiempo (una vez cada 1 o 2 semanas) se publicará un contest (o competencia, en español). Los contests se caracterizan por lo siguiente:

  • Se publicarán en codepit.io, un sitio web brasileño (sí, casi todo está en portugués) que permite crear competencias utilizando problemas obtenidos de diferentes jueces online (los enunciados de estos problemas están casi siempre en inglés eso sí), con un scoreboard que se actualiza en tiempo real a medida que los participantes resuelven problemas. Para competir sólo basta con crearse una cuenta en codepet.io y posteriormente unirse a los contests a medida que estos vayan siendo publicados.
  • Las competencias pueden ser ya sea individuales o grupales.
  • En el caso de competencias grupales, les está permitido armar grupos de un máximo de 3 alumn@s (codepit.io permite hacer esto fácilmente).
  • Cada contest tiene su propia exigencia default, es decir, un número mínimo de problemas a resolver (el cual puede ser diferente para cada contest). Sin embargo, si el alumno asiste a clases, se le restará 1 problema a su exigencia en el contest correspondiente, obteniéndose así una exigencia personalizada. Por ejemplo, si un contest tiene una duración de 3 semanas con una exigencia default de X problemas, y supongamos que 2 clases están asociadas a dicho contest, si un alumno asiste a ambas clases entonces obtendrá una exigencia personalizada de (X-2), mientra que si sólo asiste a una clase será de (X-1), y si no asiste a ninguna tendrá una exigencia de X.
  • Cada contest tendrá una duración oficial máxima (generalmente 2 o 3 semanas). El alumno (o grupo de alumnos) tendrá dicho plazo para resolver los problemas del contest. Sean N los problemas resueltos por el alumno (o grupo de alumnos) y Xp la exigencia personalizada de un alumno "p". Según la cantidad de problemas resueltos, se generan dos posibles sub-casos:
    • Si N >= Xp, dicho alumno obtiene una asistencia de 100% en dicho contest. Además, todos los problemas adicionales resueltos (N - Xp) se sumarán a un contador llamado excedente total.
    • Si N < Xp, dicho alumno obtiene una asistencia de 100 * (Xp / N) % en dicho contest. Además, todos los problemas que le faltaron (Xp - N) se sumarán a un contador llamado deuda total.
  • En codepit.io, cuando el plazo de un contest se acaba, los participantes pueden seguir enviando soluciones en un modo post-competencia conocido como upsolving. Todos los problemas resueltos en modo upsolving se agregarán a un contador llamado total upsolving Codepit.

Además de estos contests, existen otras 4 formas adicionales de obtener bonus para mejorar su nota final:

  • BONUS EXPLICACIÓN PROBLEMA DIFÍCIL (individual): Este bonus permite obtener hasta un máximo de 3 décimas cada vez, las que se sumarán directamente a su nota final. ¿Cómo obtener este bonus?:

    • El alumno debe sacar accepted en un problema difícil que casi nadie más haya podido resolver. El problema debe pertenecer a alguno de los contests del semestre y puede ser resuelto en modo upsolving también (no es obligatorio alcanzar a resolverlo dentro de plazo).
    • El alumno debe publicar su solución para que todos los demás la puedan ver (por ej. pueden subirla a un repositorio público en github).
    • El alumno debe preparar y dar una explicación de la solución adelante durante la clase y debe asegurarse de que los demás compañeros le entiendan.
    • **EXTRA: si están motivados con un problema difícil pero no saben por dónde empezar, pueden consultar con el staff del curso y nosotros trataremos de ayudarles/orientarles con material de estudio y consejos para resolver el problema.

  • BONUS RPC (grupal): Cada cierto tiempo la Red de Programación Competitiva (RPC) organiza competencias de entrenamiento. El calendario y registro para estas competencias se encuentran acá: http://registro.redprogramacioncompetitiva.com/contests, y los scoreboards de las competencias pasadas se pueden encontrar acá: http://redprogramacioncompetitiva.com/Contest. Nótese que se trata de un bonus grupal, por ende para obtener este bonus deben:

    • Registrarse en grupos de 2 o 3 alumnos.
    • Mandar una foto del grupo con todos sus integrantes juntos frente a un mismo computador (sí, la idea es que se junten físicamente usando un solo computador, como en la competencia real).
    • Mandar el link al scoreboard final de la competencia RPC en que participaron.
    • El bonus se calculará como 6 * (X/N) décimas, donde X = problemas resueltos por el grupo, N = problemas resueltos por el equipo que quedó en primer lugar. Las 6 * (X/N) décimas obtenidas se sumarán directamente a su nota final.
    • **EXTRA: las RPCs tienen un modo post-maratón (lo mismo que el upsolving de codepit.io), así que si los alumnos lo desean pueden seguir resolviendo problemas en este modo, avisarnos, y estos problemas se les sumarán a un contador llamado total upsolving RPC.

  • BONUS Codeforces (individual): Cada cierto tiempo Codeforces organiza competencias individuales, que generalmente duran alrededor de 2 horas, con problemas de diferentes niveles de dificultad. Si se registran en Codeforces, el sitio les debería ir avisando por email sobre las próximas competencias. Alternativamente, pueden revisar el siguiente calendario o bien utilizar esta página y en el search box tipear "codeforces". Para obtener este bonus deben:

    • Registrarse en Codeforces.
    • Participar en una competencia.
    • Al final de la competencia avisarnos en qué competencia participaron (por ej. mandar el link a su perfil de Codeforces).
    • El bonus se calculará como 3 * (X/N) décimas, donde X = problemas resueltos por el alumno, N = problemas resueltos por la persona que quedó en primer lugar. Las 3 * (X/N) décimas obtenidas se sumarán directamente a su nota final.
    • **EXTRA: al finalizar la competencia, si quedaron con ganas de resolver problemas que no alcanzaron a resolver durante la competencia, pueden hacerlo, avisarnos, y estos problemas se les sumarán a un contador llamado total upsolving Codeforces.

  • BONUS Regional (grupal): Cada año las universidades mandan sus mejores equipos para participar en las competencias regionales de la ACM ICPC. Sólo los mejores equipos en cada región logran clasificar a las ACM ICPC World Finals. La PUC no es una excepción así que seleccionaremos los mejores 3 equipos (cada equipo con 3 alumnos) que nos representarán en la regional, la cual este año se llevará a cabo el 10 de Noviembre en la Universidad Austral de Chile, Valdivia. ¿Cómo obtener este bonus?

    • Deben ser parte de alguno de los 3 mejores equipos seleccionados para representar a la PUC en la regional.
    • El bonus se calculará como 10 * (X/N) décimas, donde X = problemas resueltos por el equipo, N = problemas resueltos por el equipo que quedó en primer lugar. Las 10 * (X/N) décimas obtenidas se sumarán directamente a su nota final.

Cálculo de la Nota Final

La nota final se calcula calculando muchas cosas:

  • El promedio de la asistencia de todos los contests (llamémoslo X).
  • En caso de que X < 100%, el porcentaje que les falte (100% - X) lo pueden recuperar "reduciendo" su deuda total de problemas (llamémosla D). Para esto se hará el siguiente update:
    • D := deuda total de problemas
    • K := X * (excedente total + total upsolving Codepit + total upsolving RPC + total upsolving Codeforces)
      • nótese que la sumatoria anterior es "penalizada" por la asistencia promedio (i.e. vale más resolver problemas dentro de plazo que fuera de plazo).
    • D_reducido = max {D - K, 0}
    • X_aumentado = X + (1 - X) * ((D - D_reducido) / D)
  • Así se puede calcular su nota:
    • Nota = 1 + 6 * X_aumentado
  • Sin embargo, luego se bajará la escala del curso, donde el alumno con mayor asistencia quedará con nota 7 (siempre y cuando la escala baje "poco" - i.e. habrá un límite para bajar la escala).
    • Nota_v2 = aplicar_escala_reducida(Nota)
  • Finalmente, se aplicarán las décimas de bonus:
    • Nota_v3 = Nota_v2 + BONUS EXPL. PROB. DIFÍCILES + BONUS RPC + BONUS Codeforces + BONUS Regional

Seguimiento de Asistencia y Problemas Resueltos:

Todo lo anterior se encuentra formalizado en el siguiente google spreadsheet: https://docs.google.com/spreadsheets/d/1wm2jleZBV_M8V6FbTBpKfcI4uzNTg9ReMvnjq21LBXY/edit?usp=sharing

IMPORTANTE: mensaje para los alumnos nuevos

El nivel de dificultad de los problemas en las regionales ICPC es bien alto, y por lo tanto un buen entrenamiento requiere que los alumnos sean expuestos a problemas de ese nivel. Sin embargo, entendemos que tirar a los alumnos nuevos "a los leones" de golpe puede ser un poco traumático. Por lo tanto, para los primeros 3 contests tendremos dos divisiones: división 1 (más difícil) y división 2 (más fácil). Los alumnos nuevos pueden optar por participar en la división 2 si así lo desean.

IMPORTANTE: sobre lenguajes de programación

En programación competitiva el lenguaje más utilizado por lejos es C++ (y dentro de C++ generalmente se usa de C++11 para arriba). En segundo lugar se encuentra Java. Y hace muy poco se comenzó a utilizar también Python. Sin embargo, lamentablemente la mayoría de los jueces online (los servidores que tienen los enunciados de los problemas y ejecutan los códigos enviados por la gente) generalmente están calibrados para aceptar soluciones en C++ y a veces Java, y pasa mucho que las soluciones en Python fallan con el famoso Time Limit Exceeded (TLE), ya que Python de por sí es un lenguaje interpretado que se demora mucho más en ejecutar que lenguajes compilados a código de máquina como C++. Además, la mayoría de los códigos de ejemplo disponibles en internet para progcomp están en C++ o quizá Java. Dado lo anterior, el consejo típico es aprender C++. A los alumnos nuevos que quieran seguir este consejo, les recomendamos aprovechar los primeros 3 contests en división 2 para aprender a programar en C++. Más abajo pueden encontrar harto material de estudio al respecto.

IMPORTANTE: tips generales parar resolver problemas

  • En C++, en general pueden hacer un poco más de 10^8 operaciones por segundo (una estimación bien al ojo por experiencia con diferentes jueces online).
  • Siempre estimen la complejidad computacional de su algoritmo y evalúenla con el caso de prueba más grande (peor caso). Por ejemplo, si un problema depende de N donde 1 <= N <= 10^5 y mi algoritmo es cuadrático (complejidad = O(N^2)), entonces en el peor caso haré (10^5)^2 = 10^10 operaciones, y por ende según el punto anterior necesitaría 100 segundos para correrlo. En cambio, si mi algoritmo tiene complejidad O(N*log(N)) entonces en el peor caso sólo haré 10^5 * log(10^5) = 1.7 * 10^6 operaciones (aprox.), y por ende sólo necesitaría 0.017 segundos (la nada misma) para correrlo. Entonces, si mi problema tiene un tiempo máximo de ejecución de 2 segundos, ¿qué algoritmo va a funcionar? Claramente el segundo.
  • Si van a usar mucha memoria, preocúpense de no pasarse del límite de memoria permitido. Por ejemplo si les dan 256MB de memoria, en bytes eso es 256 * 1024 * 1024 = 268435456 bytes, un int32 ocupa 4 bytes, así que como máximo podrían crear un arreglo de int32 de largo 67108864 = 6.7 * 10^7 aprox (o la mitad si usan un int64, un double, etc.). También podría acabárseles la memoria si hacen demasiadas llamadas recursivas [1, 2].

IMPORTANTE: sobre ética

En este curso está totalmente permitido buscar en internet material, explicaciones e incluso ejemplos de soluciones de problemas. Tienen todo el internet a su disposición. Las únicas reglas que deben cumplir son:

  1. no buscar explicaciones / soluciones de problemas a menos que ya estén rendidos intelectualmente
  2. nunca hacer copy-paste de soluciones ajenas, sino que deben entender la solución (teoría + implementación) y ser capaces de programar dicha solución por ustedes mismos después (la idea es que aprendan, si hacen copy-paste no van a estar aprendiendo nada)

Material de Apoyo

General

Soluciones de Regionales Latinoamericanas

Soluciones, Inputs y Outputs oficiales de Regionales Norteamericanas

Para aprender C++ (MUY RECOMENDADO)

Material para Temas Específicos

Tricks para problemas Ad-Hoc:

Search:

Data Structures:

Dynamic Programming (DP):

Graphs:

Strings:

Mathematics:

Geometry:

Contests

About

No description, website, or topics provided.

Resources

Readme
Activity
Custom properties

Stars

13 stars

Watchers

5 watching

Forks

1 fork
Report repository

Releases

No releases published

Packages

No packages published