Stile IMO problema combinatorio basato su algoritmo [duplicato]

Jan 03 2021

Il problema è descritto nella figura, la soluzione dovrebbe essere una prova costruttiva, quindi è necessario trovare un algoritmo che funzioni indipendentemente da cose come il tempo di esecuzione. Qualsiasi aiuto sarebbe grato che non riesca a risolverlo e ci sto provando da un po '

EDIT: La mia direzione principale era cambiare il segno su ogni raw con somma negativa, ora ogni raw è completo e la somma di tutte le voci non è negativa (poiché la somma di tutti i raw è ora non negativa)

Risposte

1 quasi Jan 03 2021 at 15:30

Se una riga o una colonna ha una somma negativa, scegline una e inverti i segni.

Ripeti il ​​processo.

Dopo ogni transizione, la somma di tutte le voci nella matrice viene aumentata.

Ma il valore assoluto delle voci rimane invariato, quindi ci sono solo molte possibilità per la somma totale.

Ne consegue che il processo alla fine terminerà.

1 AryanHemmati Jan 03 2021 at 15:33

Usa semplicemente il seguente semplice algoritmo: In ogni turno, inverti i segni di una riga o colonna casuale con somma negativa e dimostreremo che questa procedura termina con mosse finite: Nota che usando questo algoritmo la somma dei numeri in tutti i board aumenterà sempre e poiché questa somma è delimitata dall'alto e ci sono anche possibilità finite per questa somma, il nostro algoritmo si fermerà da qualche parte e c'è il punto che la somma di tutte le righe e le colonne non è negativa.