Задана таблица размера N*M, в каждой клетке которой записана цифра 1 или 0. На каждом шаге Ви можете выбрать одну клетку и заменить значения во всех клетках того же ряда или того же столбца на противоположное. Найти минимальное количество шагов необходимых, чтобы преобразовать все клетки данной таблицы в 0. Количество рядов и столбцов — парные числа.
Например, если выбрали клетку (2,2):
1 1 1
0 1 1
0 0 1
-->
1 0 1
1 0 0
0 1 1
Пример входных данных
Пример 1
2 2
1 0
1 0
Пример выходных данных
Пример 1
2

Пример входных данных
Пример 2
4 4
0 0 1 0
0 1 0 1
1 1 1 0
0 0 1 0

Пример выходных данных
Пример 2
9

Пожалуйста подскажите идею алгоритма или пример решения похожей задачи. google — не помог.

Здравствуйте, Аноним, Вы писали:

А>Задана таблица размера N*M, в каждой клетке которой записана цифра 1 или 0. На каждом шаге Ви можете выбрать одну клетку и заменить значения во всех клетках того же ряда или того же столбца на противоположное. Найти минимальное количество шагов необходимых, чтобы преобразовать все клетки данной таблицы в 0. Количество рядов и столбцов — парные числа.

Что значит "парные числа"?

Кстати, за сколько шагов можно обнулить матрицу

попроще:
0 1 0
1 1 0

посложнее:
1 0 1 0
0 1 1 0
1 1 1 0

?

Здравствуйте, Аноним, Вы писали:

А>Пожалуйста подскажите идею алгоритма или пример решения похожей задачи. google — не помог.

Жестокое решение выглядит так.

Рассмотрим матрицу J (just) с единственной единичкой — для определённости, в верхнем левом углу.
Найдём, какие ходы нужно сделать, чтобы обнулить такую матрицу.
Построим матрицу G (go), где эти ходы будут отмечены единицами.

Рассмотрим матрицу K с единственной единичкой в позиции (x,y). Она получается из матрицы J оператором прокручивания K = rot(x,y,J).
Очевидно, что матрица ходов H, обнуляющая матрицу K, получается этим же оператором из G: H = rot(x,y,G).

Если исходная матрица M (matrix — К.О.) является суперпозицией однопиксельных матриц: M = rot(x1,y1,J) + rot(x2,y2,J) + ... + rot(xn,yn,J),
то матрица решения S (solution) является суперпозицией соответствующих матриц ходов: S = rot(x1,y1,G) + rot(x2,y2,G) + ... + rot(xn,yn,G)
где + это xor (потому что ход, сделанный дважды, отменяет себя).

Или, то же самое,
M = SUM{x,y} M[x,y]*rot(x,y,J)
S = SUM{x,y} M[x,y]*rot(x,y,G)

Кому хочется, можно выразить оператор прокручивания через матричные операции (разложив его на rotx и roty, для начала) и до конца переписать решение в матричном виде над булевым кольцом (* = and, + = xor).

Дальше осталось сделать две вещи:
— придумать, как выглядит матрица G
— просуммировать единички в матрице S

Здравствуйте, Аноним, Вы писали:

А>Количество рядов и столбцов — парные числа.
Чётные что-ли?

Тогда пробежаться по всем позициям и посчитать бит чётности для чисел, стоящих в этой строке и столбце соответственно. Сумма этих бит и будет ответом. Очевидно, решается за линейное время от числа элементов в матрице.

Здравствуйте, Кодт, Вы писали:

К>Кстати, за сколько шагов можно обнулить матрицу
К>

К>попроще:
К>0 1 0
К>1 1 0

К>посложнее:
К>1 0 1 0
К>0 1 1 0
К>1 1 1 0
К>

К>?
Нельзя обнулить ни одну, ни другую.

Здравствуйте, watchmaker, Вы писали:

W>Нельзя обнулить ни одну, ни другую.

Ну блин, кто тебя просил спойлерить?

Здравствуйте, watchmaker, Вы писали:

А>>Количество рядов и столбцов — парные числа.
W>Чётные что-ли?

Скорее, — одинаковой чётности.

W>Тогда пробежаться по всем позициям и посчитать бит чётности для чисел, стоящих в этой строке и столбце соответственно. Сумма этих бит и будет ответом. Очевидно, решается за линейное время от числа элементов в матрице.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, watchmaker, Вы писали:

А>>>Количество рядов и столбцов — парные числа.
W>>Чётные что-ли?

К>Скорее, — одинаковой чётности.

Да тут как-то непонятно условие сформулировано. Я сделал предположение исходя из того, что решение должно существовать для любой любой матрицы допустимого размера. Ну а сюда подходят матрицы вида 2n×2m и не подходят матрицы вида (2n+1)×(2m+1) (кроме 1×1, конечно), поэтому числа и чётные.

А>Пожалуйста подскажите идею алгоритма или пример решения похожей задачи. google — не помог.

Тот же алгоритм что и для сборки куба Рубика.

Здравствуйте, watchmaker, Вы писали:

W>Да тут как-то непонятно условие сформулировано. Я сделал предположение исходя из того, что решение должно существовать для любой любой матрицы допустимого размера. Ну а сюда подходят матрицы вида 2n×2m и не подходят матрицы вида (2n+1)×(2m+1) (кроме 1×1, конечно), поэтому числа и чётные.

Для чётно-чётной матрицы решение есть всегда, и ты его назвал.
А вот интересно было бы и найти решения для других матриц, — в тех случаях, когда решения существуют; ну и признак существования решения.

Здравствуйте, Кодт, Вы писали:

К> признак существования решения.
Да аналогично всё дело в чётности. Вот сразу критерий:
Решения не существует, если в булевой матрице A_n×m нечётное число столбцов и при умножении её на вектор I_m×1 = (1, 1, …1) в получившемся векторе AI есть элементы с разной чётностью.
Аналогично для строк строк матрицы.
Если ни одна из проверок не сообщила о несуществовании решения, то решение существует.

Здравствуйте, watchmaker, Вы писали:

W>Решения не существует, если в булевой матрице A_n×m нечётное число столбцов и при умножении её на вектор I_m×1 = (1, 1, …1) в получившемся векторе AI есть элементы с разной чётностью.
W>Аналогично для строк строк матрицы.
W>Если ни одна из проверок не сообщила о несуществовании решения, то решение существует.

Проще сказать, если суммарные чётности отдельных столбцов различаются; аналогично — суммарные чётности строк.

Ну, интуитивно где-то что-то понятно, а развернуть подробнее?
И, если решение существует, то какое оно?

Здравствуйте, Кодт, Вы писали:

К>Рассмотрим матрицу J (just) с единственной единичкой — для определённости, в верхнем левом углу.
К>Найдём, какие ходы нужно сделать, чтобы обнулить такую матрицу.

Нахождение таких ходов выполняется через backtracking?

Здравствуйте, watchmaker, Вы писали:

W>Тогда пробежаться по всем позициям и посчитать бит чётности для чисел, стоящих в этой строке и столбце соответственно. Сумма этих бит и будет ответом. Очевидно, решается за линейное время от числа элементов в матрице.

Попытался вручную посчитать предложенным способом для

Пример входных данных
Пример 2
4 4
0 0 1 0
0 1 0 1
1 1 1 0
0 0 1 0

Пример выходных данных
Пример 2
9

никак не удается получить : 9

Здравствуйте, olimp200, Вы писали:

O>Здравствуйте, watchmaker, Вы писали:

W>>Тогда пробежаться по всем позициям и посчитать бит чётности для чисел, стоящих в этой строке и столбце соответственно. Сумма этих бит и будет ответом. Очевидно, решается за линейное время от числа элементов в матрице.

O>Попытался вручную посчитать предложенным способом
Так показывай, как пытался и что получил.

O>

O>Пример входных данных
O> Пример 2
O> 4 4
O>0 0 1 0
O>0 1 0 1
O>1 1 1 0
O>0 0 1 0

Вот матрица матрица с битами чётности, соответствующая вышеприведённой:

0110
1110
1010
0110

Например, единица во втором столбце и второй строке стоит потому, что в соответствующей области исходной матрицы находится нечётное число единиц

0010      .0..      ....
0101  ->  0101  ->  .1..
1110      .1..      ....
0010      .0..      ....

O>никак не удается получить : 9
Ну определённо получается 9.
Сами ходы тоже легко восстанавливаются — по шагу на каждую позицию с единицей.

Здравствуйте, Кодт, Вы писали:

К>И, если решение существует, то какое оно?
Ставишь в соответствие каждой позиции свою переменную x_i,j.
Составляешь систему линейных уравнений:

для всех i,j.
Тут а_i,j — значение в исходной матрице, разумеется.
Решаешь любым способом, например алгоритмом Гаусса.
Только для матриц размера 2n×2m решение существует и единственно, а для других возможны варианты.
Очевидно, что существование решения проверяется непосредственно. Произвольное решение, в случае существования оного, также получается легко.
А вот с минимизацией числа ходов будут небольшие трудности — это задача 0-1 integer programming — из класса NP-полных.

Здравствуйте, watchmaker, Вы писали:

W>Ставишь в соответствие каждой позиции свою переменную x_i,j.
W>Составляешь систему линейных уравнений:
W>
W>для всех i,j.
W>Тут а_i,j — значение в исходной матрице, разумеется.
W>Решаешь любым способом, например алгоритмом Гаусса.
W>Только для матриц размера 2n×2m решение существует и единственно, а для других возможны варианты.
W>Очевидно, что существование решения проверяется непосредственно. Произвольное решение, в случае существования оного, также получается легко.

А как действия, выполняемые при вычислении битов четности (способ, который указан Вами в последующих сообщениях), связаны с действиями при решении указанной выше системы уравнений. Что означает для системы уравнений найденный (при сложении) бит четности?

Здравствуйте, olimp200, Вы писали:


O>А как действия, выполняемые при вычислении битов четности (способ, который указан Вами в последующих сообщениях), связаны с действиями при решении указанной выше системы уравнений.
Ну если решить систему, то можно заметить, что для матриц размера 2n×2m корни уравнений равны именно битам чётности. Это и есть значения искомых переменных x_i,j в явном виде. Соответственно, и смысловую нагрузку они несут ту же самую — если x_i,j не равен нулю, то нужно сделать ход в позиции (i,j). Всего ходов нужно сделать столько, сколько есть ненулевых x_i,j в решении системы уравнений.

Здравствуйте, watchmaker, Вы писали:

W>Ну если решить систему, то можно заметить, что для матриц размера 2n×2m корни уравнений равны именно битам чётности. Это и есть значения искомых переменных x_i,j в явном виде. Соответственно, и смысловую нагрузку они несут ту же самую — если x_i,j не равен нулю, то нужно сделать ход в позиции (i,j). Всего ходов нужно сделать столько, сколько есть ненулевых x_i,j в решении системы уравнений.

Обычно олимпиадные задачи относятся к какому-либо типу: динамическое программирование (на одномерных или двухмерных таблицах), задачи на графах (поиск в глубину, алгоритм Дейкстры) и т.д. А к какому типу, подтипу, на Ваш взгляд, относится задача, рассматриваемая в этом обсуждении. Способ, предложенный Вами, просто идеально решает эту задачу. Хотелось бы где-то(?) почитать про общий метод решения такого типа задач: почему система уравнений, почему именно такие уравнения и т.д.
Отдельное спасибо за предыдущие ответы.