zniweczyć matrycy 2D z jakiegoś zestawu operacji

Question

Given an N x M matrix having only positive integer values, we have to nullify the matrix 
i.e make all entries 0. 
We are given two operations 
1) multiply each element of any one column at a time by 2. 
2) Subtract 1 from all elements of any one row at a time 

Find the minimum number of operations required to nullify the matrix. 

myślałem robić coś związanego z LCM ale nie mógł dotrzeć do roztworu

Answer 1

Niech najpierw rozwiązać za 1 wiersz pierwszy i możemy przedłużyć go do wszystkich wierszy. Weźmy przykład losowy:

6 11 5 13 

Celem jest, aby wszystkie elementy jako 1. Najpierw musimy wykonać 5 (najmniejszy element) jako 1. Z tego musimy odjąć 4 (tj odjąć 1 cztery razy). Otrzymaną macierzy jest:

2 7 1 9 

Teraz pomnożyć 1, Z 2 i odjąć wszystkie elementy rzędu od 1:

1 6 1 8 

Następnie pomnożyć 2 1 poprzez 2 i odjąć wszystkie elementy rzędu od 1:

1 5 1 7 

Kontynuując w ten sposób, otrzymujemy numer 1 1 1 1. Teraz odejmujemy 1, aby uzyskać 0 0 0 0.

Następnie przechodzimy do innych rzędów i robimy to samo, jak powyżej. Wiersz, który anulowaliśmy powyżej, to wszystkie zera, więc mnożenie przez 2 podczas manipulowania innymi wierszami nie zmienia już anulowanych wierszy.

Kwestia znalezienia minimalnej liczby operacji zależy również od wybranej przez nas sekwencji wierszy. Myślę, że byłoby to najpierw wybrać wiersz, którego maksimum jest minimalne (między innymi wierszami). Muszę to zweryfikować.