Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Вы настраиваете предобработку данных для компьютерного зрения. Камера выдаёт бинарный кадр — прямоугольную…

Ниже даю подробное решение задачи с пошаговым объяснением и готовым алгоритмом. Если у вас сейчас есть конкретная матрица, дайте её — я пройдусь по алгоритму и дам точный результат (YES/NO и строки инверсии). Пока что — разбор метода и пример реализации.

Что задача просит сделать

• Есть бинарная матрица A размером Q x N.
• Можно инвертировать любые выбранные строки (перевести 0 в 1 и наоборот) и любые выбранные столбцы.
• Нужно получить однородную матрицу (все 0 или все 1). При этом считаем, что исход мог быть как черным, так и белым, поэтому допускаются оба варианта.
• Если можно, вывести YES и две строки: для строк длиной Q (где 1 означает инвертировать соответствующую строку) и для столбцов длиной N (где 1 означает инвертировать соответствующий столбец). Если невозможно — NO.

Математическая модель

• Пусть r_i — признак инверсии i-й строки (0 или 1), для i = 1..Q.
• Пусть c_j — признак инверсии j-го столбца (0 или 1), для j = 1..N.
• После применения инверсий значение в клетке станет A[i][j] xor r_i xor c_j.
• Требуем, чтобы итоговая матрица была однородной: все элементы равны некоторому k ∈ {0,1}.
• Тогда для фиксированного k получаем матрицу B, определяемую как B[i][j] = A[i][j] xor k. Нужно, чтобы B[i][j] = r_i xor c_j для всех i,j.

Как проверить существование решений

• Пробуем оба варианта k = 0 и k = 1.
• Пусть возьмём k и зададим r_1 = 0 (это без ограничений, выбор эквивалентен, так как можно дописать одно константное flipping-перемещение).
• Тогда c_j = B[1][j] для всех j.
• Теперь для каждой строки i найдём предполагаемое r_i: r_i = B[i][1] xor c_1.
• Проверяем, что для всех j выполняется B[i][j] = r_i xor c_j.
  • Если для какой-то пары (i,j) это условие нарушается, текущий k невозможен.
  • Если для обоих k проверка успешна, задача решена. Можно вернуть r_i и c_j как ответ.
• Если ни для k не удалось — вернуть NO.

Псевдокод решения (Python-подобно)

• Вход: матрица A размера Q x N, элементы 0/1.
• Выход: "NO" или "YES" и две строки r (длина Q) и c (длина N), где '1' означает инверсию.

Формализованный алгоритм

1. Считать Q, N и A[0..Q-1][0..N-1] где A[i][j] ∈ {0,1}.
2. Для k в {0, 1} сделать: a) B[i][j] = A[i][j] xor k b) c[j] = B[0][j] для всех j c) для i от 0 до Q-1: r[i] = B[i][0] xor c[0] для j от 0 до N-1: если B[i][j] != r[i] xor c[j], перейти к следующему k (неудачно) d) если цикл прошёл успешно, вернуть YES, r и c
3. Если ни один k не сработал, вернуть NO.

Пример реализации (Python-подобный код) def solve_matrix(A): Q = len(A) N = len(A[0]) for k in (0, 1): # B = A xor k B = [[A[i][j] ^ k for j in range(N)] for i in range(Q)] c = B[0][:] # c_j = B[0][j] r = [0] * Q ok = True for i in range(Q): r[i] = B[i][0] ^ c[0] for j in range(N): if (r[i] ^ c[j]) != B[i][j]: ok = False break if not ok: break if ok: # Преобразовать r и c в строки '0'/'1' r_str = ''.join('1' if x else '0' for x in r) c_str = ''.join('1' if x else '0' for x in c) return ("YES", r_str, c_str) return ("NO", None, None)

Как трактовать результат

• Если мы получили YES, то:
  • В строке r_str символ i равен '1' если нужно инвертировать i-ю строку.
  • В строке c_str символ j равен '1' если нужно инвертировать j-й столбец.
• В случае NO такая конфигурация инверсий не существует.

Замечания и полезные моменты

• Восстановление возможно не всегда: структура B должна быть суммой по модулю 2 двух векторов r и c.
• Мы проверяем оба варианта k, потому что исходный кадр мог быть либо черным, либо белым, как сказано в задаче.
• Сложность очень маленькая: O(2 * Q * N), где Q,N ≤ 100, что легко в рамках ограничений.

Если хотите, пришлите конкретную матрицу Q x N (строки по порядку без пробелов, как в входе задачи), и я выполню шаги выше и дам точный результат (YES/NO и соответствующие строки инверсий).