Questo problema e' una generalizzazione immediata del problema 4 (Avogadro) del Contest 5 (Feb 23, 2008) delle COCI 2007/2008. Nel problema Avogadro si avevano sempre m=3, ossia ogni matrice istanza aveva precisamente 3 righe. Quando uno legge e si figura il problema e' portato a considerare che, visto che la prima riga e' una permutazione (e quindi ogni numero appare al piu' una volta in essa) allora se su una riga abbiamo piu' occorrenze di uno stesso numero allora dobbiamo necessariamente rimuovere delle colonne corrispondenti a queste occorrenze in eccesso. Il problema e' sapere quali, in quanto una di queste colonne potrebbe dover essere mantenuta, e scegliere se e quale ... senza un criterio e' non-determinismo. Ed in effetti questo criterio non sembra esserci. Come anche in altri problemi, da questa situazione di stallo se ne esce adottando un altro punto di vista, ed in particolare riferendosi ad un approccio complementare. Per una faccenda di piccioni, su una riga abbiamo occorrenze multiple di un numero se e solo se sulla stessa riga qualche altro numero manca. Ora, un numero che non occorre nella riga r, e' vero che non ha molto da dira alla riga r, ma tuttavia conduce ad una conseguenza definitiva e non-ambigua: quel numero deve sparire! Quindi vanno rimosse tutte le colonne che contengono tale numero. L'idea e' quindi di continuare cosi' finche' tutti i numeri non ancora scartati appaiono in ogni riga. Il punto e' che, una volta che questo succede, allora abbiamo finito. Perche'? La ragione, forse meno diretta che nel first-scratch approccio piu' immediato sopra accenato sta comunque nel fatto che la prima riga ... Controllare per credere. OK, questo sul piano problem solving/piano algoritmico alto/scomposizione matematica del problema. Bisogna poi progettare un algoritmo efficiente, il che passera' per la determinazione di un giusto ordine in cui procedere ed il progetto delle opportune strutture dati di cui avvalersi da un lato ma da mantenere aggiornate dall'atro. Il fiuto (e la dimensionalita' degli input) devono suggerire che qui si deve puntare per un algoritmo lineare. Prima di leggere la soluzione, vi consiglio di provare a pensarci voi, e, se non avete cantiere, nel prossimo file di hint suggerisco, senza fornire la soluzione, spunti metodologici di supporto. Rimando al sito del COCI per la formulazione originale, per una spiegazione, per dei codici risolutori e per delle istanze.