Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Активные темы Темы без ответов
Настройки поиска (Страница 2 из 4)
Страницы Назад 1 2 3 4 Далее
Темы от coder.ua Расширенный поиск
Сообщений найдено [ с 26 по 50 из 77 ]
На такой длине можно попробовать интовый хеш - поподбирать нужную базу хеша придётся тогда, ибо коллизии на интовом хеше - не редкость. Но зато инт гораздо быстрее, раз уж так хочется именно хешом решать эту задачу.
Я так и делаю. Я вычисляю один хеш по модулю 10^6, а второй по 2^32, по первому "вяжу" в связный список, а по второму сравниваю. Вероятность того, что разные строки дадут одинаковые хеши как по первому хешу,так и по второму очень мала. На рандомном тесте работает 3 секунды, хотя максимальная глубина списка - 36,как я уже говорил.
Ради интереса только что сдал с лонг лонговским хешом и ручным хешсетом.
Скажи пожалуйста как ты писал свой ручной хешсет, если не секрет.
А ты можешь решить хешами?
Меня тоже заинтересовала эта задача. Я написал на неё хеш, но он на макс тесте работает 3 секунды, хотя на одну ячейку у меня не больше чем 36 коллизий. Можно конечно пошаманить, но боюсь по памяти не пройдёт.
Странно, что сетом не проходит...
А разве перебирать все подстроки и кидать в хеш-таблицу не успеваем по времени?
Спасибо огромное!Вторая идея кажется более простой, наверное, буду реализовывать её, хотя вторую нужно взять на заметку. Ещё раз спасибо!
Спасибо, но я не пойму зачем нам сумма длин путей до LCA. Возможно таким образом можно найти максимальное ребро на цикле или я что-то неправильно понимаю понимаю?
Я встречал, наверное, всем известную задачу, где нужно найти второй по величине остов. Я знаю лишь один алгоритм для подобной задачи: строим мст, потом поочерёдно добавляем рёбра, не вошедшие в мст и отнимаем от суммы максимальное ребро из полученного цикла и проверяем на оптимальность. Но в задаче, которую я встречал были довольно жёсткие ограничения: V порядка 10000-100000, а E - 500000. Наверное, если есть задача, то существует и решение:) Мне интересно знаете ли Вы алгоритм быстрее, чем тот, который я описал выше?
А как связать списки и битовые маски?
Думаю это не даст ощутимого преимущества,сперва нужно вникнуть в сам алгоритм,а с этим проблемы...:(
Первую можно сделать сканирующей прямой,предварительно отсортировав все окружности по одной из координат.
Для второй,мне кажется, нужно найти пару самых отдалённых друг от друга точек.Расстояние между ними - диаметр окружности , середина отрезка ,который соединяет эти точки, - центр окружности.
Всем привет,хотел разобрать этот алгоритм,но возникли некие трудности. Если кто-то может помочь,то скажите - зачем множество "NOT",описанное в этой статье?http://ru.wikipedia.org/wiki/%D0%90%D0% … 1%88%D0%B0
Каким образом оно помогает?Возможно кто-нибудь знает некоторые фичи этого алгоритма? При каких ограничения он должен работать за адекватное время и т.д.
Заранее спасибо.
думаю,что без бинарного возведения в степень не обойтись,а вот что дальше делать я не знаю ещё.
Для каждого ребра неориентированного графа нужно вывести ориентацию{'>','<','='} чтобы вершины ,которые были изначально в одной компоненте связности были всё-ещё достижимы друг от друга.И при этом нужно максимизировать число ориентированых рёбер {'>','<'} в новом графе.
Дан неориентированный граф(Н,М) Н<=20000 М<=20000.Нужно вывести список рёбер так чтобы у каждого ребра была ориентация U V *(*=">",'<','='),то есть с вершины Ю в В при знаке больше,наоборот при меньше и неориентированное при "=".Нужно максимизировать число ориентированных рёбер в ответе.Мне кажется,что здесь можно юзнуть ксс,но дальше идею развить не могу.
Заранее спасибо 
Re: Hash (3 ответов, оставленных в Algo)
Вообще часто используется,относительно легко пишется,подходит наверное к любой задаче на поиск.Другое дело,что иногда нужно много памяти,иногда не хочешь рисковать с частными случаями.А вообще советую в Кормене прочитать,там всё хорошо расписано.
Спс,там оказался граф не связный,правда теперь у меня РЕ почему-то,но всё-равно спасибо!
Сразу думал,что тут множество фундаментальных циклов,но получил ВА 
Есть какие-то идеи?
http://acm.timus.ru/problem.aspx?space=1&num=1077
Большое спасибо!
Спасибо,но с математическим английским у меня проблемы...
Я это и имел ввиду.Так как её реализовать,и в чём суть декомпозиции?
Слышал,что это полезная вещь)Если кто знает,то раскройте идею структуры и ,в частности как с помощью неё восстановить путь в графе между двумя вершинами.Буду очень благодарен.
Спасибо
С истоком согласен.А вот если после конденсации останется граф:
1->2
1->3
Тогда стока вообще не существует,но у 2 и 3 степень входа -0.
бтв в задаче гарантировано что исток и сток существуют,но перебирать все компоненты со степенью входа равной 0 мне кажется неразумным.
Исток-из него достижимы все вершины.(необязательно напрямую)
Сток-он достижим из всех вершин.(необязательно напрямую)
Дан орграф.Нужно найти вершину сток и вершину исток в нём.Ограничения большие, то есть нужно уложиться в 1-2 обхода.
P.S мне кажется что здесь конденсация 
Сообщений найдено [ с 26 по 50 из 77 ]
Страницы Назад 1 2 3 4 Далее