CD
интуитивно хочется построить сжатый trie из чиселок и что-то доказать про такие деревья
Size: a a a
2020 August 23
CD
А вот еще задачка: известно что произведение prod((x^2+ai*x+bi)/(x^2+ci*x+di)) в общем случае можно расписать как сумму членов того же вида. Вопрос, можно ли сделать это быстрее чем за квадрат?
а это не какая-то форма интерполяции?
CD
в С штука в числителе подозрительна похожа на интерполяционный многочлен
CD
А вот еще задачка: известно что произведение prod((x^2+ai*x+bi)/(x^2+ci*x+di)) в общем случае можно расписать как сумму членов того же вида. Вопрос, можно ли сделать это быстрее чем за квадрат?
за каждым Ai в форме \sum Ai/(Bi * z + Ci) стоит значение числителя в точке z=-Сi/Bi
V🇺
а это не какая-то форма интерполяции?
кажется что да
Г
Какие алгоритмы можете посоветовать, пожалуйста, для поиска кратчайшего пути на невзвешанном и неориентированном графе?
Г
О чем стоит почитать, кроме наивного поиска в ширину?
MB
А чем поиск в ширину не устраивает?
/¯
О чем стоит почитать, кроме наивного поиска в ширину?
Поиск в ширину оптимален для этой задачи, что сподвигло к поиску альтернативы?
G
Какие алгоритмы можете посоветовать, пожалуйста, для поиска кратчайшего пути на невзвешанном и неориентированном графе?
ну дейкстру можешь глянуть
Г
А дейкстра разве не для взвешенных графов?
G
А дейкстра разве не для взвешенных графов?
ну пусть дан взвешенный граф, где ребра с весом равным единице
🎄T
ну пусть дан взвешенный граф, где ребра с весом равным единице
Получится же тупо поиск в глубину
G
Получится же тупо поиск в глубину
соглы)
MB
Для невзвешенных графов дейкстра в зависимости от реализации либо по асимптотике проигрывает, либо превращается в тот же bfs но с константой похуже
Г
Мне посоветовали Эдмондс-Карпа, но я не очень его понял, надо разбираться, спасибо
MB
Это который потоки ищет? :)
/¯
Мне посоветовали Эдмондс-Карпа, но я не очень его понял, надо разбираться, спасибо
Это же про поиск максимального потока
G
Мне посоветовали Эдмондс-Карпа, но я не очень его понял, надо разбираться, спасибо
диницу глянь, по лучше будет, кажется
Г
Хорошо, спасибо