Проверка за сервером
Вы отдали перемножение двух матриц на сторонний сервер, и он вернул результат. Сервер иногда ошибается — портит одно-два числа, и злонамеренно: так, чтобы ошибку не выдали ни суммы строк, ни суммы столбцов. Пересчитывать произведение заново слишком долго. Проверьте, верен ли результат.
Вход
В первой строке n (1 ≤ n ≤ 300). Дальше три матрицы n × n — A, B и C, каждая — n строк по n целых чисел. Элементы A и B — от 0 до 100, элементы C — от −109 до 109.
Выход
YES, если A·B = C, иначе NO.
Пересчёт по определению — 2,7·107 умножений при n = 300 — в Python не уложится в лимит.
Примеры
Пример 1
2 1 2 3 4 5 6 7 8 19 22 43 50
YES
Пример 2
2 1 2 3 4 5 6 7 8 20 21 43 50
NO
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Пересчитать A·B — n³ умножений. А сколько стоит умножить матрицу на вектор? Если AB = C, то для любого вектора r верно A(Br) = Cr. Какой вектор взять?
2Подсказка 2
Вектор из одних единиц сравнивает суммы строк, и сервер этим пользуется: портит две клетки одной строки на +e и −e. Любой заранее выбранный вектор можно обмануть так же. А случайный?
3Идея
Проверка Фрейвалдса: случайный вектор r из нулей и единиц, сравниваем A(Br) с Cr — три умножения матрицы на вектор, 3n² операций. Если AB = C, равенство выполнено всегда. Если нет, то, как доказано в статье, проверка обманывается с вероятностью не больше ½ — какой бы ни была порча: для ненулевого элемента dij разности D = AB − C из двух значений rj не больше одного обнуляет (Dr)i. Повторив проверку 30 раз с независимыми векторами, ошибёмся с вероятностью не больше 2−30 ≈ 10−9.
Сервер не знает наших случайных чисел, поэтому никакая хитрая порча ему не поможет. Против вектора из единиц хватает пары +e, −e в одной строке (второй пример), а против проверки и строк, и столбцов — «прямоугольника» +e, −e, −e, +e в двух строках и двух столбцах (седьмой тест).
4Разбор
Прочитать три матрицы; 30 раз: случайный r, вектор Br, затем для каждой строки сравнить Ai·(Br) и Ci·r; при первом расхождении — NO. Если все проверки прошли — YES. В Python скалярные произведения быстрее всего считать как sum(map(mul, row, vector)).
Третий и четвёртый тесты — граф ссылок трёх учебников этого сайта: A = B — матрица ссылок 202 страниц, а C = A·A — число путей из двух щелчков между ними; в четвёртом одно из этих чисел увеличено, а соседнее в той же строке уменьшено.
4+Решение
5Сложность
O(kn²) при k = 30 проверках, против O(n³) пересчёта.
6Типичные ошибки
- Суммы строк или столбцов. Это проверка с одним фиксированным вектором, и её обманывают пары ошибок с разными знаками.
- Одна случайная проверка. Она пропускает ошибку с вероятностью до ½; на десяти тестах с ошибками это почти наверняка провал.
- Пересчёт произведения. Верно, но 2,7·107 умножений — это десятки секунд в Python.