Dominatori di torneo

Aiuto
1

Ciao a tutti,
Sto cercando di risolvere il problema “domina”, ma senza successo. La mia soluzione, che totalizza 70/100, utilizza l’ordinamento topologico (o, perlomeno, una variante leggermente modificata, dato che il grafo non è sempre un DAG), ma non credo che questa sia la strada giusta per risolverlo. Qualcuno può darmi una mano?


Grazie mille :smiley:
2

Ancora non ho provato a scrivere codice, ma questo mi sembra tanto uno di quei problemi in cui, per farsi venire in mente la soluzione, è utile dimostrare che è sempre possibile trovare la risposta.

E magari fare la dimostrazione per induzione, che è molto molto amica della ricorsione!
3

Qualche ulteriore suggerimento?

E’ quasi tutto il giorno che ci provo, ma non mi vengono idee…

EDIT: certamente se riuscissi a dimostrare l’esistenza della coalizione per induzione potrei facilmente trovare l’algoritmo per costruirla: è questo però che non riesco a fare!
4

Il caso base è facile: se hai un nodo solo, la coalizione è composta da lui.

Poi il passo induttivo: per ipotesi esiste una coalizione per N nodi, vogliamo dimostrare che è possibile aggiungere un nodo al grafo e trovare la coalizione del grafo risultante.
Qua puoi procedere per casi.
Per esempio: 
caso 1) Esiste un membro dell’attuale coalizione che sconfigge il nuovo
caso 2) Non c’è nessun legame tra il nuovo e la coalizione
eccetera
Cerca di spezzettare in diversi casi tutti “facili” da risolvere.
5

L’unico caso un po’ “tosto” è quello in cui il nuovo elemento sconfigge qualcuno delle coalizione, ma nessuno della coalizione sconfigge il nuovo, nè un giocatore sconfitto dalla coalizione sconfigge il nuovo… Suppongo però che con qualche accorgimento si riesca a far quadrare tutto. Ora ci penso un po’, grazie :slight_smile: