pro.algorithms
Хорошо, выбрали те строку который есть одна 1 значений.
Удалим этот строку и столбцу.
И дальше будет та же самая схема?
9 ответов
Да, повторяем схему пока можем. К чему приходим?
Khurshid
Автор вопроса
N <= 50
Ага, что можем сделать с такой матрицей?
Khurshid
Автор вопроса
Ага, что можем сделать с такой матрицей?
Метод Гаусс O(N^3). Но , у задаче осталось не рассмотренный случай: Как эффективно то удалим и как ищем тот строку с единсвенном 1 после серий удалений элементов?
Метод Гаусс O(N^3). Но , у задаче осталось не рас...
Ну, у тебя есть списки единиц по строками
Ну, у тебя есть списки единиц по строками
Нужно только сразу все одиночные единицы вычеркнуть за раз и понять в какой степени должна быть -1 как множитель
Khurshid
Автор вопроса
Khurshid
Автор вопроса
Нужно только сразу все одиночные единицы вычеркнут...
Реализовал , отправлял на проверку - получал сигфаулт на assert(remain_n <= 50) после того как перечитал условие, узнал там кол.во рёбр <= n + 50, там требует детерминант матрица смежности графа, построил матрица смежности, оказывается там кол.во 1 два раза больше чем я предполагал, потому что для каждого рёбр два 1 попадается в матрица смежности. Может в этом случае можно придумат ещё что нибудь? То есть, оказывается M <= 2 * ( N+ 50) . M - number of 1.
Похожие вопросы
Обсуждают сегодня