La battaglia del convoglio

Nota storica: tra il 7 e il 10 marzo del 1943 c’è stata nell’Atlantico quella che è stata definita la più grande battaglia di convogli mai combattuta.
Sottomarini tedeschi si comunicavano, in maniera cifrata, le posizioni dei convogli americani da attaccare.
Gli alleati conoscevano, ovviamente, le posizioni dei loro convogli, ed intercettavano le comunicazioni dei tedeschi.
Le informazioni acquisite da queste comunicazioni cifrate, insieme alle posizioni note dei convogli americani, sono state fondamentali per il lavoro di Alan Turing a Bletchley Park: qui Turing ha ideato la macchina Bomba, che ha consentito agli alleati di rompere il codice di Enigma, la macchina per comunicazioni cifrate dei tedeschi.

Torniamo alla battaglia: un convoglio americano, composto da N navi, è in viaggio nell’Atlantico.
Sottomarini tedeschi si comunicano le posizioni delle navi e si coordinano per l’attacco.
Gli alleati intercettano le comunicazioni tedesche ma riescono a decrittare solo parzialmente i messaggi: non sempre si riesce a identificare di quale nave stiano parlando i tedeschi, e spesso più di una nave americana potrebbe essere quella a cui fanno riferimento.
In particolare, se indichiamo con M0 .. MN-1 gli N messaggi intercettati, e con S0 .. SN-1 le N navi della flotta, alla luce di quanto decodificato ogni messaggio puo riferirsi a una o più navi, come si vede nella figura (dove N=3), dove, per esempio, il primo messaggio può riferirsi sia alla prima (S0) che alla terza (S2) nave.
oii_2012_convoglioTuring riesce a trovare una corrispondenza univoca tra i messaggi e le navi: una corrispondenza in cui ad ogni messaggio distinto corrisponde una nave distinta.
Per esempio, le 3 linee a tratto spesso in figura evidenziano 3 coppie messaggio-nave (M0−S2, M1−S0 e M2−S1).
Questa è una corrispondenza univoca in quanto:

  • per ogni i=1,2,3 esiste uno ed un solo j tale che la coppia Mi−Sj è stata inclusa;
  • per ogni j=1,2,3 esiste uno ed un solo i tale che la coppia Mi−Sj è stata inclusa.

Per poter proteggere la flotta bisogna essere sicuri della corrispondenza, e quindi dobbiamo ora accertarci che non esistano altre corrispondenze univoche interamente costituite da coppie messaggio-nave consentite dall’istanza (gli archi in figura, sia in grassetto che in tratto semplice).

Per esempio, nel caso della Figura 1 esiste anche una seconda corrispondenza univoca: M0−S0, M1−S2 e M2−S1.

Aiutate Turing a capire se la corrispondenza univoca da lui trovata e anche unica!

Dati in Input

La struttura del file di input e la seguente: la prima riga contiene 2 interi, N e M, che rappresentano, rispettivamente, il numero di navi (che coincide con il numero dei messaggi intercettati) e il numero complessivo di possibili corrispondenze tra messaggi e navi.
I messaggi sono identificati da interi compresi tra 0 e N−1, e anche le navi sono identificate da interi compresi tra 0 e N−1.
Le successive M righe contengono una coppia ordinata di interi rappresentanti, rispettivamente, un messaggio e una nave corrispondente.
Di queste M righe, le prime N contengono tutti i messaggi e tutte le navi, e identificano la corrispondenza univoca trovata da Turing.

Con riferimento alla figura, rappresentando i messaggi M0, M1 e M2 con gli interi 0, 1 e 2, e le navi S0, S1 e S2 con gli interi 0, 1 e 2, l’istanza nella figura viene rappresentata dal file di input a fondo pagina.

Dati in Output

Se non esiste nessuna altra corrispondenza possibile, il file di output deve essere costituito da una sola linea, contenente l’intero -1. Altrimenti, se esiste un’altra soluzione, il file di testo contiene N linee, corrispondenti alla soluzione trovata, rappresentata come lista di coppie di interi, messaggio e nave, ordinate per numero di messaggio.

Con riferimento alla figura, rappresentando i messaggi M0, M1 e M2 con gli interi 0, 1 e 2, e le navi S0, S1 e S2 con gli interi 0, 1 e 2, la seconda possibile soluzione univoca viene rappresentata dal file di output a fondo pagina.

Assunzioni

  • N ≤ 100.000
  • M ≤ 200.000

Esempi

input.txt output.txt
3 6
0 2
1 0
2 1
0 0
1 2
2 2
0 0
1 2
2 1
Notice: This work is licensed under a BY-NC-SA. Permalink: La battaglia del convoglio

Comments are closed.