¿Qué son los problemas ad hoc en la programación competitiva?

Los problemas Ad Hoc son problemas que no se pueden clasificar en ningún otro lugar de las categorías con soluciones bien estudiadas ya que cada descripción del problema y su correspondiente solución son únicas. Estos problemas no entran en categorías estándar, no existe una técnica específica o general para resolverlos. Muchos problemas Ad Hoc son fáciles, pero esto no se aplica a todos los problemas Ad Hoc.

1. Los problemas ad hoc aparecen con frecuencia en los concursos de programación. En ICPC , ≈ 1-2 problemas de cada ≈ 10 problemas son problemas Ad Hoc. En un concurso de programación, si el problema Ad Hoc es fácil, normalmente será el primer problema resuelto por los equipos. Sin embargo, en los casos en que las soluciones a los problemas Ad Hoc eran demasiado complicadas de implementar, provocaba que algunos equipos las resolvieran en la última hora. En un concurso regional del ICPC con alrededor de 60 equipos, su equipo se clasificaría en la mitad inferior (puesto 30-60) si solo puede resolver problemas Ad Hoc.
2. En IOI 2009 y 2010, ha habido 1 tarea fácil por día de competencia 11, generalmente una tarea (Fácil) Ad Hoc. Si eres un concursante de IOI , definitivamente no ganarás ninguna medalla solo por resolver las 2 tareas sencillas Ad Hoc durante los 2 días de competencia. Sin embargo, cuanto más rápido pueda completar estas 2 tareas fáciles, más tiempo tendrá para trabajar en las otras 2 × 3 = 6 tareas desafiantes.

Consejos para problemas ad hoc

Hay algunos consejos generales para abordar un problema que parece ser Ad Hoc:

1. Escribir ideas: siempre que haya una observación que parezca útil, escríbala, ya que escribir las ideas asegura que no se olviden y que puedan ser la solución.
2. No te quedes atascado: no te quedes atascado en ninguna idea específica, a menos que parezca ser una solución completa para el problema. Es una mejor idea completar la búsqueda ya que los problemas Adhoc pueden hacer perder mucho tiempo.
3. Dibujar muchos casos pequeños: Para lograr una mejor comprensión del problema, se recomienda practicar dibujar muchos casos pequeños. Dibuja más casos cuando-
   • Hay un problema con la depuración.
   • Si no sabes cómo empezar con un problema.
   • Siempre que no se esté seguro de cómo abordar más el problema.
   • La mejor idea es dibujar más casos y hacer observaciones sobre las propiedades del problema.
4. Diferentes perspectivas: Trate de abordar el problema desde diferentes perspectivas. Continúe probando las ideas, dibuje una representación visual del problema, pruebe diferentes fórmulas, diferentes valores en las fórmulas hasta lograr avances.
5. Realice un patrón en la solución: después de resolver una serie de problemas de programación, intente realizar un patrón en las soluciones. Hay ciertos modismos que se usan con bastante frecuencia en la programación competitiva. 
   1. Por ejemplo, desde una perspectiva de C/C++, estos modismos pueden incluir bibliotecas como cstdio, cmath, cstring, etc., atajos de tipos de datos, rutinas de E/S básicas, macros de bucle y algunas otras. 
   2. El programador competitivo de C/ C++ puede almacenarlos en un archivo de encabezado como ‘adhocproblems.h’. Con un archivo de encabezado de este tipo, la solución a cada problema puede comenzar con un archivo de encabezado simple al comienzo del programa #include<adhocproblems.h>. 

Conjunto de categorías de problemas ad hoc

Analicemos algunas de las categorías del conjunto de problemas Adhoc:

1. Juego de cartas: Hay muchos problemas Ad Hoc relacionados con los juegos de cartas. Uno de los enfoques es analizar las strings de entrada ya que las cartas tienen ambos palos:
   1. D/Diamante, C/Trébol, H/Corazón y S/Picas.
   2. Para los rangos, el orden habitual es: 2 < 3 < . . .< 9 < T/Diez < J/Jota < Q/Reina < K/Rey < A/As12. 
   3. Puede ser una buena idea asignar estas strings a índices enteros. 
   4. Por ejemplo, un mapeo posible es mapear D2 → 0, D3 → 1, . . . , AD → 12, C2 → 13, C3 → 14,. . . , SA → 51. Entonces se vuelve mucho más fácil trabajar con índices enteros.
2. Juego de ajedrez: El ajedrez es otro juego popular que aparece en problemas de concursos de programación y algunos de estos problemas son problemas Ad Hoc. Por ejemplo, la tarea combinatoria de contar cuántas maneras hay de colocar 8 reinas en un tablero de ajedrez de 8×8.
3. Otros juegos: Muchos otros juegos como Tic Tac Toe, Rock-Paper-Scissors, Snakes/Ladders, BINGO, Bowling, etc. también han llegado a los concursos de programación. Conocer los detalles de estos juegos puede resultar útil, pero la mayoría de las reglas del juego se enumeran en la descripción del problema para evitar perjudicar a los concursantes que no están familiarizados con los juegos.
4. Problemas relacionados con palíndromos: un palíndromo es una palabra (o una secuencia) que se puede leer de la misma manera en cualquier dirección. La estrategia más común para verificar si una palabra es palindrómica es pasar del primer carácter al del medio y verificar si los caracteres coinciden en la posición correspondiente desde atrás. Por ejemplo, ‘ABCDCBA’ es un palíndromo. 
5. Problemas relacionados con anagramas: Un anagrama es una palabra (o frase) cuyas letras se pueden reorganizar para obtener otra palabra (o frase). La estrategia común para verificar si dos palabras son anagramas es ordenar las letras de las palabras y comparar los resultados. Por ejemplo, tome wordA = ‘cab’, wordB = ‘bca’. Después de ordenar, wordA= ‘abc’ y wordB = ‘abc’ también, por lo que son anagramas.