Problema de combinação baseado em algoritmo estilo IMO [duplicado]
O problema é descrito na imagem, a solução deve ser uma prova construtiva, então você precisa encontrar um algoritmo que funcione independentemente de coisas como o tempo de execução. Qualquer ajuda seria desagradável. Não consigo resolver isso e estou tentando por um tempo
EDIT: Minha direção principal foi mudar o sinal em cada raw com soma negativa, agora cada raw está completo e a soma de todas as entradas é não negativa (uma vez que a soma de todos os raws agora é não negativa)
Respostas
Se alguma linha ou coluna tiver uma soma negativa, escolha uma e inverta os sinais.
Repita o processo.
Após cada transição, a soma de todas as entradas na matriz é aumentada.
Mas o valor absoluto das entradas permanece inalterado, portanto, há apenas possibilidades finitas para a soma total.
Segue-se que o processo acabará eventualmente.
Basta usar o seguinte algoritmo simples: Em cada turno, inverta os sinais de uma linha ou coluna aleatória com soma negativa e vamos provar que este procedimento termina em movimentos finitos: Observe que usando este algoritmo a soma dos números em todos os o tabuleiro sempre aumentará e como essa soma é limitada de cima e também existem possibilidades finitas para essa soma, nosso algoritmo irá parar em algum lugar e aí está o ponto que a soma de todas as linhas e colunas são não negativas.