Comprobando si la clasificación de victorias y derrotas de una liga es posible

8

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 (2n) 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.

Muchas cookies
fuente

Respuestas:

8

Esto se puede modelar como un problema de Max-Flow.

Como paso de preprocesamiento, asegúrese de que el número de juegos sea igual a la suma del número de victorias (si no, sabe que algo está mal).

Dejar G ser un conjunto de vértices correspondientes a los juegos jugados, y PUn conjunto de vértices correspondientes a los jugadores. Dejars y t denotan dos vértices adicionales (fuente y sumidero).

Ahora para cada juego gG jugado entre p1P y p2P, agregue un borde de s a g con capacidad 1 y bordes de g a p1 y g a p2 también con capacidad 1. Esto modela el hecho de que el juego puede dar un punto a cualquiera de los jugadores.

Entonces para cada jugador pP agregar un borde de p a t con capacidad igual al número reportado de victorias para el jugador p. Esto modela el hecho de que este jugador debería ganar como máximo este número de juegos.

Es fácil ver desde aquí que si los puntajes reportados son posibles, habrá un flujo de saturación de s a ty recíprocamente. Entonces, todo lo que necesita verificar es si el máximos,t-flujo en este gráfico es igual al número de juegos jugados.

Alternativamente, también podría tener un gráfico con un vértice por juego y un número de vértices para cada jugador correspondiente al número de victorias, conectarlos de la misma manera que antes y ver si el número de bordes en una coincidencia máxima es igual a la cantidad de juegos (pero esto es casi lo mismo realmente).

Borla
fuente
¡Muy agradable! Y en lugar de tener un nodo para cada uno de los m juegos separados entre P1 y P2, que podrían consolidar todos ellos en un solo nodo (una "serie" nodo) con capacidades borde m en lugar de 1?
ManyCookies
En el preprocesamiento, también debe verificar que el número de victorias + pérdidas reportadas por cada jugador es igual al número total de juegos que ese jugador ha jugado.
Ilmari Karonen
Además, aunque su respuesta parece técnicamente correcta, tenga en cuenta que, en la práctica, resolver el problema de flujo máximo no es necesario para atrapar trampas simples (donde los jugadores solo hacen trampas al reclamar victorias adicionales y / o menos pérdidas; el preprocesamiento solo atrapará eso) ni suficiente para atrapar trampas más sutiles (donde, por ejemplo, Alice pierde un partido con Bob, pero ambos acuerdan luego informarlo como la victoria de Alice de todos modos; no hay forma de detectar eso usando solo los datos proporcionados). Pero ese es un problema con el problema de @ ManyCookies como se indicó, no con su solución.
Ilmari Karonen
@ManyCookies: Claro, eso también debería funcionar :)
Tassle
@IlmariKaronen: Sí, puede agregar cualquier cantidad de pasos de preprocesamiento que desee para que las cosas funcionen más rápido en la práctica, pero estos no son estrictamente necesarios, mientras que el paso de preprocesamiento que propuse fue principalmente para facilitar la verificación de la condición de flujo máximo (sin ella necesitaría verificar que el flujo se esté saturando en ambos extremos, lo que se reduciría a ese paso de preprocesamiento).
Tassle