tgoop.com/bminaiev_blog/91
Last Update:
0-1 matrix
Решал на выходных UniversalCup, расскажу про одну из задач. Если судить по количеству команд, которые ее решили, то она 10-я из 13 по сложности. Хотя на самом деле очень простая.
После несложных манипуляций она сводится к следующей. Есть матрица 1000*1000 из нулей и единиц. К ней применяют операции "инвертировать строку i" или "инвертировать столбец j". Под "инвертировать" имеется в виду, что каждый 0 заменяется на 1, а каждая 1 на 0. После каждой операции надо за О(1) определять, правда ли, что вся матрица состоит только из нулей.
Если вы хотите подумать над задачей, перед тем как читать решение, то сейчас самое время.
Если вы давно читаете мой блог, то наверняка знаете, что я люблю рандомизированные алгоритмы. Сопоставим каждой клетке (i, j) случайное число r[i][j]. Будем поддерживать xor от r[i][j] для всех клеток, в которых стоит единица. Если все клетки нули, то этот xor будет тоже равен нулю. Если же какая-то клетка не ноль, то этот xor будет равен нулю только с вероятностью 2^-64 (если используем 64-битные числа), так что на практике это никогда не случится.
Чтобы применять операции за О(1), можно предподсчитать xor всех r[i][j] для каждой строки i и для каждого столбца j, а потом ксорить текущий ксор всех включенных клеток с предподсчитанным значением.
BY Боря программирует
Share with your friend now:
tgoop.com/bminaiev_blog/91