Интересно было бы посмотреть на контрпример к алгоритму, в к-ром ищем самую удаленную вершину от рандомной вершины, а потом самую удаленную от найденной.
26 2009-12-21 18:24:16
Re: Поиск самых отдалённых вершин в дереве (30 ответов, оставленных в Problems)
27 2009-11-05 11:55:27
Re: Задача на паросочетание (7 ответов, оставленных в Problems)
Ну может быть 
В любом случае нам надо максимальное независимое множество, а оно как-то там зависит от макс паросочетания 
UPD: вспомнил, максимальное независимое множество является дополнением к минимальному контролирующему/покрывающему множеству.
28 2009-11-04 21:36:31
Re: Задача на паросочетание (7 ответов, оставленных в Problems)
Просто размер максимального паросочетания равен размеру максимального независимого множества.
29 2009-10-08 14:14:00
Re: Timus 1003 (3 ответов, оставленных в Problems)
Если решать непересекающимися множествами, то элементами этих множеств будут куски последовательности от начала до i-ого символа. Для каждого элемента храним четность куска последовательности между ним и его предком. При добавлении запроса, объединяем два соответствующих элемента(если они в разных множествах), иначе проверяем, сходится ли четность если идти по нашему дереву и четность, которую нам сообщили. И не забываем использовать эвристику сжатия путей.
Как-то так;)
30 2009-09-09 12:13:45
Re: Алгоритм Паскаля (13 ответов, оставленных в Algo)
В разные годы в той же роли там еще были алгоритм Кормена, алгоритм Штайна и топологическая сортировка за O(E)/ O(V).
31 2009-09-08 13:53:18
Re: Алгоритм Паскаля (13 ответов, оставленных в Algo)
Ха-ха, на самом деле это специальный пункт(типа детектор) в тематической анкете и такого алгоритма не существует; если человек его отметил, то скорее всего он не очень много знает и отмечает другие пункты просто так, чтобы показать что он типа крут
32 2009-09-07 18:50:52
Re: преобразование Фурье для многочленов (6 ответов, оставленных в Algo)
Хм, я слышал, что можно использовать не 3-разрядную, а где-то 8-разрядную арифметику + 64-битные целые числа; они конечно работают медленнее, чем 32-битные, но при этом и длина числа сокращается почти в 3 раза, т.е. в результате может получиться побыстрее.
33 2009-09-01 19:57:50
Тема: Полезные ссылки (1 ответов, оставленных в Feedback)
Раз этот сайт становится чем-то вроде сборника алгоритмов для начинающих (и не только) олимпиадных программистов, думаю неплохо было бы создать раздел со всякими "полезными ссылками", относящимися к теме сайта, естественно .
Конечно все более-менее знают эти сайты : тимус, топкодер и т. д. , но моя идея в том, чтобы вместе с такими линками выкладывать и какие-то менее известные; например - для того же топкодера существует достаточно много сайтов с разной дополнительной статисткой, один из них https://www.otinn.com/ ; или скажем сайт http://timustests.lx.ro/ суть которого должна быть понятна из названия
P. S. :Кстати говоря, я ищу расписание SRM'ов и других топкодерских событий в формате, пригодном для гугл Календаря - его тоже можно будет разместить в этом списке.
P. P. S. : аналогичную штуку для GCJ я случайно нашел в их твиттере.
34 2009-09-01 19:29:48
Re: Теоретический минимум для нубов. (10 ответов, оставленных в Offtopic)
manof пишет:
4. Граф является деревом если E/2 == V - 1, где E - кол-во ребер, V - кол-во вершин.
Вообще-то просто E = V - 1;
35 2009-08-21 23:21:17
Re: Азы С++ (10 ответов, оставленных в Algo)
Ок, что это такое понятно; интересней то, нужно ли это на практике? Ведь по сути мы обрубаем некоторую часть функциональности этого underlying контейнера(не знаю как по русски), почему бы тогда не просто его использовать. Или в случае скажем stack<int,vector<int> > d можно обратиться к d[3]?
36 2009-08-21 18:14:23
Re: Азы С++ (10 ответов, оставленных в Algo)
У меня вопрос не в тему, но тоже по азам C++:
сегодня обнаружил(точнее прочитал), что stack и queue, а возможно и что-то еще, можно создавать не просто stack<int> и queue<int>, а например stack<int,vector<int> > или queue<int,list<int> >.
Кто-нибудь может мне объяснить отличие этих определений от обыкновенных и зачем это надо?
37 2009-08-21 12:19:59
Re: Timus 1019 (10 ответов, оставленных в Problems)
Если последний пост был обращен ко мне, то действительно, запрос получается не за log, а за константу
38 2009-08-20 21:29:45
Re: Timus 1019 (10 ответов, оставленных в Problems)
Ладно, всем спасибо, решил за log n на каждый запрос; оказалось нужно еще хранить в каждой вершине дерева отрезков её цвет, если он известен и одинаков на всем подотрезке, тогда при перекраске нужно просто проталкивать это значение своим детям, если мы из вершины идем вниз.
Непонятно наверное объяснил, но лучше не смогу:)
39 2009-08-20 19:55:56
Re: Timus 1019 (10 ответов, оставленных в Problems)
да да да, это всё прекрасно, но мне нужно решение за O(n log n)!
Предыдущая идея работала за O(log n) перекраска + O(n) запрос, и т. к. в этой задаче запрос всего 1, то все отлично, НО: интересно, чтобы и то, и то было за O(log n)
40 2009-08-20 19:39:00
Re: Timus 1019 (10 ответов, оставленных в Problems)
Т. е. вы имеете в виду просто красить отрезки, а потом пробежаться по ним и найти самый длинный из них? Блин, почему мне эта идея в голову не пришла 
, спасибо.
Но если у нас есть запросы вида перекраска отрезка и какой самый длинный белый отрезок сейчас, то Ваша идея видимо не катит, т. к. второй запрос за O(n). Хотелось бы оба запроса уметь за O(log n).
41 2009-08-20 19:06:39
Тема: Timus 1019 (10 ответов, оставленных в Problems)
http://acm.timus.ru/problem.aspx?space=1&num=1019
Интересует решение с помощью дерева отрезков;
Вот что-то я не очень понимаю, что именно нужно в нем хранить. Пытался хранить координату начала и длину самого длинного белого кусочка в поддереве, а также длину белых кусочков, примыкающих к краям отрезка, соответствующего , но не пошло. need help одним словом. Не откажусь от кода, только желательно понятного, лучше всего с какими-нибудь комментами.
42 2009-08-14 12:13:43
Тема: Непрерывная задача о рюкзаке (1 ответов, оставленных в Algo)
В Кормене, в главе о жадных алгоритмах есть такое упражнение:
• 16.2-6. Покажите, как решить непрерывную задачу о рюкзаке за время О (n). (во втором русском издании оно находится на странице 458)
Если кто не знает, то суть задачи следующая: есть N кучек золотого песка, i-ая кучка имеет вес Wi и стоимость за всю кучку Ci; также есть рюкзак в который помещается не более W килограммов песка; нужно унести какой-то песок(кучки можно брать не полностью), чтобы его суммарная стоимость была максимальна.
За O(n log n) решение конечно очевидно, а вот за O(n) непонятно; честно говоря вообще сомневаюсь, что это возможно. Есть идеи?