Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Сообщения от Acmefan
Как называются графы которые имеют не один вес ребра, а два (например время проезда и цена).
И где можно почитать про алгоритмы на таких видах графов? (т.е. где надо искать ответы оптимизированные по двум параметрам. Например, что б сумма параметров была наименьшая)
Во-первых, O(N^2*M) это лишь порядок количества операций, т.е. там N^2*M*C, где C может быть <1.
Во-вторых, столько операций выполняется в худшем случае, в среднем же алгоритм работает быстро.
Вот ссылка на статью, где описан худший случай для алгоритма Диница: http://deepblue.lib.umich.edu/bitstream … 000617.pdf.
Ну я прекрасно понимаю что такое асимптотика. И прикинуть приблизительно время программы можно.
Например такой цикл
long long N,r,i;
cin>>N;
for(i=1;i<=N;i++) r=r+i;
отработал на моем ноутбуке, при N=10^9 - 10 секунд, при N = 2*10^9 - 21 секунду.
Если сравнить с временем АС = 0.3 то это раз в 70-100 медленнее.
Сомневаюсь что дело тут в константе C может быть <1 
Тут либо быстродействие проверяющей машины на несколько порядков выше
Либо не оптимальные тесты
Вспоминается, в одном из петрозаводсков авторское решение искало Диницем поток среди 50000 вершин...
Ну если там были единичные пропускные способности ребер, то O(sqrt(n)*m) может и вполне разумно, при неогромных m...
Кстати, а можно где то достать архивы петрозаводских сборов? (лекции, задачи, тесты, авторские решения)
Почитал на сайте статью про алгоритм Диница нахождения макс потока.
Закодил.
Решил поискатькуда можно его заакцептить.
нашел задачку с ограничением 10 на число вершин
http://informatics.mccme.ru/moodle/mod/ … p?id=262#1
Здал успешно.
Смотрю дальше, и офигеваю. Задача с ограничениями на 500 вершин и 10000 ребер
http://informatics.mccme.ru/moodle/mod/ … rid=2784#1
Прикидываю, что если алгоритм Диница работает за O(n^2*m) то это будет порядка 2,5 миллиарда операций.
Смотрю ограничения времени - 2 секунды. думаю попробую...
И результат 0.3 секунды АС на самом большом тесте.
Это недостаток тестов, или быстродействие проверяющей машины???
Кто знает задачи на Тимусе или других архива на факторизацию числа быстрее чем sqrt(N) киньте пожалуйста ссылочки.
А также по вашему мнению, что выгоднее всего писать во время контеста. Полларда или что иное?
В дереве все рёбра должны идти сверху вниз, т.е. от отцов к сыновьям.
Что имеется ввиду сверху вниз?
Ведь мы как дерево не построй, оно всегда будет сверху вниз , если мы возьмем за верх любую вершину.
Есть ссылка на задачу? Или это чисто теоретический вопрос?
На каждую из задач, которые тебя интересуют, довольно легко написать решение за Н*Н, генератор, тестилку. Так что ты можешь их тестировать самостоятельно, при этом, получая тесты, на которых твои решения валяться.
Спасибо, Капитан очевидность
Я спрашивал не как искать глюки в своих программах, изобретая велосипеды, а спрашивал где почитать и посмотреть велосипеды, которые изобретались не одним человеком и не один десяток лет
Вот ты напишешь сейчас определение факта пересечения двух окружностей из заданного набора за N*logN ??
Генератор и тестилку я тебе предоставлю Но думаю єто мало поможет, без четкого алгоритма.
Вон в "Препарата. Шеймос..." там одним предложением обмолвились, что мол мы за N*logN можем определить факт пересечения двух отрезков из набора, в одномерном случае, и значит задачу про круги тоже можем решить.
И сколько тесты не составляй, но без осознания алгоритма ты не напишешь рабочую прогу...
ааааа, так тебе алгоритмы нужны?:)
Ближайшая пара точек хорошо описана на этом же сайте, даже я её здесь понял.
Ну понял я ее в других местах, еще до этого сайта.
Но подозреваю, что в деталях реализации кроется куча подводных камней. Так что лишнего посмотреть непомешает.
Пересечение двух отрезков делается сканлайном, не очень сложно, советую почитать в Кормене.
Так это на пальцах я и так знаю. А пощупать пример, который коректно работает при вертикальных, куче пересечений в однйо точке и т.д.... Пока не пощупал...
Идея такая же, как и с отрезками.
Препарата и Шамос в своей книжке так же срезались
Каких-то быстрых алгоритмов для нахождения расстояния я не встречал, но наверное, они существуют. А вообще можно за Н*М делать: просто искать расстояние от каждого отрезка первого полигона до каждой точки второго.
Ну полюбому можно, поскольку у нас многоугольник выпуклый. Поэтому как минимум бинпоиск напрашивается
Ну короче вопрос про линки остается открытым
Спасибо за линк!
В разделе геометрия
http://informatics.mccme.ru/moodle/cour … .php?id=22
из описаний алгоритмов там только есть статьи Андреевой (при чем толковые и легко написанные)
остальное все просто задачки.
И, к сожалению, ни одного из перечисленного мной алгоритма там нету в описании 
Можно ли найти подматрицу с максимальной суммой элементов в заданной матрице меньше чем за O(N^3) ?
На информатикс.
А адрес ?
а то я уже разные информатиксы набирал, и не нашел
Где в инете можно найти толковую подборку по геометрическим алгоритмам (возможно с примерами реализаций).
интересуют:
нахождение ближайшей пары точек
установление факта пересечения двух из множества отрезков
установление факта пересечения двух из множества кругов
расстояние между выпуклыми многоугольниками
определение точки в выпуклом многоугольнике (за logN)
і т.д.
Ну да.
В этом результате, кажется, нет ничего удивительного - с предпосчетом n log n (sparse-table) отвечать на такие запросы за O(1) вообще легко.
Ну да, и с предпосчетом n^2 (stupid-table ) отвечать за О(1) еще легче
Это же более мощный метод, и у него предпосчет за n.
Да, вот это и заинтересовало (препроцессинг за линейное время). Но, подозреваю, что эта метода применима в жизни, но не применима на контестах. Так как писать ее относительно трудоемко.
Где можно достать архивы олимпиад с разборами задач? Может у когото есть на винте или ссылки, прошу поделиться.
А то онлайн архивы задач это хорошо, но там ты лишь видишь прошло ли твое решения, а про авторское можешь только догадывать.
У меня, например, хеши ТЛяться:) Возможно они кривые, но всё же...
Способы интересны. Но каждой грядке - свой инструмент.
Думаю, всё же хеши с хешсетами сложнее запихать, чем "чистый" квадрат бора
Сложнее в плане времени выполнения, или времени написания?
Т.е. если и хеши и такой бор имеют одинаковую асимптотику, то на контесте нужно минимизировать время написания.
И мне кажется, что хеши пишутся намного быстрее бора.
Но есть гораздо более простой который основан на dsu, и отвечает на запросы lca в оффлайне.
Как непосредственно применить dsu к задаче rmq, без сведения к lca, не знаю.
Я правильно понял, что в нашей дискуссии есть мысль, что на запросы min(L,R) в оффлайне можно (хоть и через большой геморрой с сведением к lca) отвечать за О(1) ???
Ссылка не стоит, но вот есть статья по этому поводу:
http://e-maxx.ru/algo/rmq_linear
Не нашел там ни слова про disjoint set
Тут проскочила интересная фраза.
http://e-maxx.ru/algo/dsu
Эффективная реализация для задачи минимума в автономном режиме
(т.е. нужно реализовать структуру данных, которая позволяет добавлять элементы из множества {1,..,N} и извлекать минимум; задача автономна в том смысле, что вся последовательность запросов известна к началу выполнения алгоритма)
Подозреваю она из Кормена, но уже мозги вспухли от идей, как применить DSU к поиску минимума, при чем за &O(1)
И вообще если такое возможно, тогда возможна сортировка за линейное время (что как известно в общем случае не возможно)
А, ну кстати по решению с бором - не всё так плохо, можно строить сжатый бор - за квадрат его строить не так уж и сложно
а смысл тогда, если хешами тоже за квадрат решаем с меньшим напрягом
Как за O(N+M) найти в графе все вершины которые принадлежат хотя бы одному циклу в неориентированном графе?
А что здесь особенного?Насколько я понял, это стандартный связный список.
Ну да, стандартный.
Но вот реализация понравилась.
to KADR:
Прикольная модификация списка ребер.
Сразу возникает жадный вопрос. Где такое вычитал? Может там еще че интересное накопаю
На этом форуме один добрый юзер выложил архив 2010 ЛКШ
http://e-maxx.ru/forum/viewtopic.php?id=267
там в один из дней эта задача есть. Правда там ограничения написаны 2000. но формулировка идентичная. И название идентичное.
В архиве в папке B есть задача bacon.7z там есть тесты, и миникаменты от жури.
В них немногозначно написано
"для каждой подстроки подсчитать ее хеш-функцию".
Значит копаем мы в правильном направлении
Кстати, где можно достать архивы ЛКШ других годов?
А покажи кусок кода в котором ты вычисляешь все хеши.
Подозреваю что там у тебя O(N^3)
1) Если это задача с олимпиады, то ограничения какие? (на количество вершин, количество ребер, и вес ребер)
Ну а если просто себе придумал задачку, тогда тут сложнее дело обстоит
2) Путь любой вообще? Или между двумя заданными вершинами?
Кстати сразу паралельно возникла еще одна похожая задача.
Тоже есть граф такой же самый, но надо построить каркас с максимальным значением на ребрах не больше Ma и Mb.
НУ тупое решение этих двух задач такое:
Всех возможных наборов a - b столько сколько ребер. Т.е. M^2
Для всех возможных M^2 вариантов, выкидываем ребра из графа и пытаемся на нем найти в нем ответ, за N^2
сложность в результате O(M^2 * N^2) что обычно не очень гут
Можно ускорить выкидывая для каждого фиксированого А бинарным поиском выкидывать В.
Тогда вариантов будет M*logM и каждый решать за N^2
Результат O(N^2 * M*logN) но подозреваю что это тоже не очень гут
Но меньшей оценки пока не придумал.
А вообще задачка интересная...
Даны радиусы двух кругов и расстояние между ними.
Как оптимально вычислить плозадь пересечения этих кругов?
Можно ли это сделать оперируя только радиусами и расстоянием? не вычисляя точки пересечения окружностей?
MAXimal :: φορυμ » Сообщения от Acmefan