Preguntas frecuentes de USACO

P: ¿Qué es USACO?

La USA Computing Olympiad  es una competencia nacional de programación que ocurre cuatro veces al año, con contests en diciembre, enero, febrero y US Open (marzo). Los contests regulares duran cuatro horas, y el US Open dura cinco. Cada contest tiene tres problemas. Las soluciones se evalúan y se puntúan contra un conjunto de casos de prueba predeterminados. El puntaje es sobre 1000 puntos, y cada problema pesa lo mismo (~333 puntos). Hay cuatro divisiones de contests: Bronce, Plata, Oro y Platino. Después de cada contest, quienes alcancen el corte de promoción (que depende del contest) competirán en la siguiente división en los contests futuros.

P: ¿Cómo se participa en un contest de USACO?

Hay que registrarse con una cuenta (gratuita) en usaco.org  y esperar a que empiece la ventana de cuatro días del contest. Cuando arranca la ventana, la página principal de USACO se actualiza con instrucciones sobre cómo participar.

P: No recibo un email después de registrarme en usaco.org  con mi cuenta de Gmail. ¿A quién pido ayuda?

Es un problema conocido. Si aparecen problemas técnicos con usaco.org , hay que contactar al director del contest de USACO (Brian Dean). No hay que enviar el formulario de contacto de USACO Guide; USACO Guide no está afiliado a USACO, así que no vamos a poder ayudar.

P: ¿Hace falta participar en el contest de diciembre de USACO antes de participar en los otros?

No.

P: ¿Cómo se puntúan los contests de USACO?

Los contests de USACO se puntúan sobre $1000$ puntos. Cada problema vale $1000/3 = 333.333 \dots$ puntos. Cuando se envía una solución a un problema, se ejecuta contra una cantidad de casos de prueba (ver el segundo enlace de arriba para más detalles). Todos los casos de prueba de un problema (típicamente 10-30) pesan lo mismo, excepto el o los casos de ejemplo, que no cuentan para el puntaje.^{En contests más antiguos, los casos de ejemplo sí contaban para el puntaje.} Las entradas y salidas de los casos de prueba que no son de ejemplo no son visibles durante el contest.

Por ejemplo, Cow College  tiene 1 caso de ejemplo (caso de prueba 1) y 11 casos que no son de ejemplo (casos de prueba 2-12). Por cada uno de los casos 2-12 que se acierte, se ganan $333.333 \dots/11 = 30.3030\dots$ puntos.

P: ¿Pasar todos los casos de prueba garantiza que la solución es correcta?

No; es perfectamente posible que exista un caso de prueba para el cual la solución falle. En el caso extremadamente raro de que se agreguen casos de prueba después del final del contest, soluciones que antes recibían puntaje completo a menudo dejan de recibirlo después.

En general, es extremadamente difícil comprobar que la solución es correcta con 100% de certeza, pero una forma de verificar que no hay nada obviamente mal es hacer un stress test contra una solución modelo.

P: ¿Qué lenguaje de programación debería usar para USACO?

Los lenguajes más populares que soporta USACO son C++, Java y Python. En general, recomendamos lo siguiente:

• Si ya se conoce uno o más de estos lenguajes, usar el que resulte más cómodo.
• Si no se conoce ninguno, conviene empezar con C++, ya que quienes usan C++ en general no tienen que preocuparse tanto de que sus soluciones queden un factor constante por debajo del límite. Además, la mayoría de los módulos todavía no tienen soporte para Java ni Python.

¡No hay que pensarlo de más al elegir un lenguaje: siempre se puede cambiar más adelante!

Cubrimos la elección de un lenguaje con más detalle en el módulo “Elegir un lenguaje”.

P: ¿Cómo se envía una solución a un problema pasado de USACO?

Este módulo incluye soluciones de ejemplo e instrucciones sobre cómo enviarlas.

P: ¿Cómo funcionan las promociones?

Todos los competidores empiezan en la división Bronce. Al final del contest, se determina un “puntaje de corte” para cada división según la dificultad del contest. Si el puntaje es al menos el puntaje de corte de la división, se obtiene una promoción permanente a la siguiente división. Históricamente, el puntaje de corte siempre ha sido un múltiplo de $50$ puntos en el rango $600\ldots 850$ (típicamente $750$).

Si se obtiene un puntaje perfecto durante el contest (es decir, se resuelven por completo los tres problemas), se obtiene una promoción durante el contest (in-contest promotion), y se pasa de inmediato a la siguiente división. Se puede empezar el contest de la siguiente división cuando se quiera durante la ventana del contest; el cronómetro de cuatro o cinco horas se reinicia al empezar el contest. Una vez promovidos, los competidores permanecen en su nueva división, ya que no hay descensos.

Una vez que se conoce el lenguaje elegido, se puede resolver el siguiente problema para comprobar la comprensión:

P: ¿Cómo me preparo para USACO?

Hay que aprender algoritmos, hacer problemas de práctica y reflexionar sobre por qué se están fallando problemas. Si se aprende de cada problema que se hace, se mejora con el tiempo. Si se busca una hoja de ruta guiada para mejorar en USACO, conviene revisar USACO Guide (¡este sitio!).

Si se quiere mejorar en USACO, lo clave es practicar más.

P: ¿Cuál es el mejor recurso para mejorar en USACO?

Hicimos USACO Guide específicamente para ofrecer recursos de alta calidad que ayuden a mejorar en USACO; ¡alentamos a probarla! También listamos recursos adicionales que pueden ser útiles. Además, USACO tiene su propia página de recursos .

P: ¿Qué temas hay que saber para cada división de USACO?

Aunque no hay un temario oficial de USACO, compilamos temas para cada división a partir de contests históricos:

• Temas de USACO Bronce
• Temas de USACO Plata
• Temas de USACO Oro
• Temas de USACO Platino

P: ¿Dónde se pueden encontrar más problemas de práctica?

1. El sitio de USACO  tiene problemas desde 2011 en adelante.

   • Ofrecemos una lista de problemas recientes de USACO (desde 2015) aquí.
   • Los problemas más antiguos de USACO pueden ser más fáciles que los de contests recientes debido a aumentos de dificultad.

2. Codeforces  — se puede buscar por etiqueta (tag), nivel de dificultad, etc.

3. CSAcademy Archive 

4. Para más fuentes de problemas, ver la página de contests.

P: ¿También debería usar las USACO Training Pages ?

Pueden resultar útiles. Hay que tener en cuenta que:

• No son amigables para principiantes, como señaló el propio Rob Kolstad aquí .
• No permiten ver la solución de un problema hasta resolverlo. No permiten pasar de una sección hasta haber resuelto todos los problemas de esa sección.
  • Aunque algunas personas lo consideran una ventaja (como se menciona aquí ).
• No cubren muchos temas que aparecen con frecuencia en contests actuales (como Árboles de Segmentos), como se señala aquí .

P: Estoy trabado. ¿Dónde puedo pedir ayuda para USACO?

Recomendamos ir al (no oficial) USACO Forum  para pedir ayuda cuando uno se traba. Como alternativa, se puede unir al (no oficial) USACO Discord Server . Tienen canales llamados #discussion y #help dedicados a preguntas sobre programación competitiva.

P: ¿Por qué el sitio me da WA cuando mi código da la respuesta correcta en mi computadora?

Es probable que se deba a comportamiento indefinido; ver este módulo para más información.

P: ¿Qué tiene de malo mi código?

Hay que seguir todas las instrucciones de esta publicación del foro . Se puede intentar preguntar en el foro, pero si es evidente que no se siguieron todas las instrucciones, es probable que la única respuesta sea seguir las instrucciones con más cuidado.

P: ¿Dónde se encuentran los datos de prueba y las soluciones oficiales de USACO?

Desde la página del problema, hacer clic en “Return to Problem List” y después en “Test Data” o “Solution” debajo del problema correspondiente.

P: ¿Cuándo debería leer las soluciones oficiales de USACO?

Depende de la preferencia personal; no hay una respuesta correcta o incorrecta: hay que hacer lo que funcione para cada uno. Dicho esto, preguntamos a numerosos competidores top de USACO qué piensan sobre esta pregunta. Este módulo lista sus ideas sobre cómo practicar de forma efectiva para USACO.

P: ¿Debería implementar cada problema que resuelvo?

Por lo general, sí (salvo que el problema sea significativamente demasiado fácil). Resolver problemas de programación competitiva consiste en dos partes: idear el algoritmo e implementar el algoritmo. Hay que implementar para practicar ambas partes.

P: ¿Qué rating de Codeforces corresponde a cada división de USACO?

El rating de Codeforces y las divisiones de USACO no se pueden comparar de forma directa, ya que CF enfatiza resolver más problemas en menos tiempo (los contests de CF tienen 5-8 problemas en 2-3 horas, mientras que los de USACO tienen 3 problemas en 4-5 horas). Las estimaciones de abajo solo pretenden ser comparaciones aproximadas, no cortes exactos. En particular, los ratings de problemas de CF y los ratings de competidores de CF miden cosas distintas, y un estudiante puede ser capaz de resolver un problema al estilo CF de rating más alto en un contest de USACO porque hay más tiempo por problema.

Con eso en mente, estas son algunas estimaciones muy aproximadas:

• Quienes compiten en USACO Bronce probablemente estén por debajo de 1300 de rating en CF, y los problemas de Bronce corresponden a problemas de CF de rating 900-1500.
• Quienes compiten en USACO Plata probablemente tengan 1200-1500 de rating en CF, y los problemas de Plata corresponden a problemas de CF de rating 1200-1900.
• Quienes compiten en USACO Oro probablemente tengan 1500-1800 de rating en CF, y los problemas de Oro corresponden a problemas de CF de rating 1500-2200.
• Quienes compiten en USACO Platino probablemente tengan 1650+ de rating en CF, y los problemas de Platino corresponden a problemas de CF de rating 1900+. (Nótese que en el nivel Platino hay mucha variación en los ratings de CF.)

De nuevo, los problemas y contests de CF son significativamente distintos de USACO, así que estos rangos hay que tratarlos como orientación aproximada y no como fronteras estrictas.

P: ¿Se permite el trabajo colaborativo?

Colaborar con otras personas durante el contest está estrictamente prohibido para mantener la equidad y la integridad. Los contests de USACO están diseñados para evaluar habilidades individuales de resolución de problemas, y la colaboración da una ventaja injusta. Sin embargo, fuera del entorno del contest, se alienta a estudiar y prepararse juntos, compartiendo conocimiento y técnicas para mejorar las habilidades de forma colectiva.

P: ¿Cuáles son las restricciones de memoria y tiempo para programas en C++, Python y Java?

En los contests de USACO, los programas escritos en distintos lenguajes están sujetos a restricciones específicas para asegurar una competencia justa y eficiente. Estas restricciones incluyen tanto límites de tiempo como asignaciones de memoria, que varían un poco según el lenguaje usado.

• Restricciones de tiempo: cada caso de prueba de entrada tiene asignado un límite de tiempo específico para la ejecución del programa. Este límite suele rondar los 4 segundos, aunque puede variar según la complejidad del problema y el contest concreto. Dentro de ese plazo, el programa debe terminar su ejecución y producir la salida correcta. Superar el límite de tiempo hace que el programa se termine, lo que lleva al veredicto de “límite de tiempo excedido” (Time Limit Exceeded).
• Restricciones de memoria: a los programas se les asigna una cierta cantidad de memoria para su ejecución. La memoria asignada se usa para almacenar variables, estructuras de datos y otra información relacionada con el programa durante la ejecución. Es esencial administrar la memoria de forma eficiente para no superar el límite asignado, lo que llevaría al veredicto de “límite de memoria excedido” (Memory Limit Exceeded).

Esta tabla resume las restricciones para distintos lenguajes de programación en contests de USACO:

P: ¿Dónde se puede ver el historial de contests y las promociones?

Se pueden ver los puntajes de contests pasados y la división actual iniciando sesión en la cuenta de USACO.

Después de cada contest, USACO también publica resultados oficiales y cortes de promoción. Puede que no haya rankings públicos para cada división o contest.

P: ¿Dónde se encuentra la respuesta a una pregunta que no está contestada aquí?

Probablemente se encuentre la respuesta en usaco.org  o buscando en Google.

También se puede hacer una pregunta enviando el formulario “Contact Us” en la parte inferior izquierda de esta página, o en el USACO Forum .

Cierre

¡Esperamos que esta FAQ haya sido útil! Mucha suerte en el camino de la programación competitiva.