mq
Чтобы хоть примерно понять, какой размер ответа будет на выходе
Size: a a a
2020 March 04
mq
Ну мне хотя бы примерно
mq
Типа линейно, квадрат или че
I
Ну, я не всегда смогу это сделать. Если у меня n = 100, d = 42, я не смогу это сделать, например
Приоритет - главная и побочная диагональ
I
Остальные рандомишь
mq
Ща, я могу попробовать вбросить идею, как я пытался про нее думать.
mq
Можно думать про матрицу как про матрицу смежности некоторого графа
mq
Тогда в A^2 a_{ij} != 0 <=> в графе есть путь длины 2 между i, j
mq
Ну и как-то свелось к проведению ребер в графе хз может быть это проще
mq
ну вот это максимум, на что мне хватило идей
mq
скорей всего не решается
короче видимо таки квадрат
mq
ну не, на самом деле 2d-1 ребер использовано, потому что они ориентированные, но асимптотика та же
EZ
Есть нулевая матрица А порядка n. Как оптимально расставить d ненулей в ней, чтобы максимизировать количество ненулей в матрице A^2?
Заполнять первый столбец и строку?
mq
Заполнять первый столбец и строку?
ахахах, да
mq
Кстати, это почти матрица смежности того графа
mq
Если единицу удалю, ею и будет
PS
Заполнять первый столбец и строку?
Ну сначала логичнее главную диагональ заполнять
i
Почему не второстипеннуб?
PS
Почему не второстипеннуб?
Можно и её
EZ
Ну сначала логичнее главную диагональ заполнять
Для каждого элемента первого столбца получаешь количество ненулевых в первой строке