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 roztworuzniweczyć matrycy 2D z jakiegoś zestawu operacji
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ć.
To jest fajny pomysł, ale nie jest to odpowiedź, jest to metoda unieważniania matrycy, ale nie wykazałeś jej minimalnej liczby operacji. –
Zostawiłem to jako ćwiczenie dla użytkownika :). – user1168577
Dość interesujący zestaw operacji to twoje; Spodziewałem się dodatkowych mnożenia kolumn po rzędzie. Powodzenia, bracie! (: – Rubens
Jak dobrze znasz pojęcie grupy i dziedzin algebrowych? –