Estás organizando una liga de baloncesto 1 v 1 con un calendario de juegos. Al final de la liga, hace que cada jugador informe su supuesto récord de victorias y derrotas (no hay empates), pero desea verificar si las clasificaciones propuestas eran realmente posibles dado el calendario.
Por ejemplo: tienes cuatro jugadores (Alice + Bob + Carol + Dave) y tu agenda es un simple round robin. Las clasificaciones informadas [ A: 3-0 B: 1-2 C: 1-2 D: 1-2] y [ A: 2-1 B: 1-2 C: 1-2 D: 2-1] serían posible, pero la posición [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] no lo sería.
Ahora supongamos que el horario es un juego de 3 juegos cara a cara entre Alice + Bob y Carol + Dave. La posición informada [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] ahora es posible, pero [ A: 3-0 B: 1-2 C: 1-2 D: 1- 2] ya no lo sería.
(El horario no necesita ser simétrico de ninguna manera. Podría hacer que Alice solo juegue contra Bob 10 veces, luego haga que Bob + Carol + Dave jueguen 58 round robins uno contra el otro).
Problema : Dado un horario con k participantes yn juegos totales, verifique de manera eficiente si una clasificación propuesta de ganar-perder realmente podría ocurrir a partir de ese horario.
El O () el método de fuerza bruta es obvio, enumere todos los resultados posibles del juego y vea si alguno coincide con la clasificación propuesta. Y si k es pequeño, el aumento de n no agrega mucha complejidad: es muy fácil verificar la clasificación de una liga de dos personas independientemente de si juegan diez o diez mil millones de juegos. Más allá de eso, no he avanzado mucho en la búsqueda de un método mejor, y tenía curiosidad por saber si alguien había visto un problema similar antes.
fuente