Российские студенты победили на чемпионате мира по программировани
Вот условия: http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf
Разбор был в процессе тура на icpclive.com
В этом году достаточно халявный финал, обычно бывает сложнее. Плюс впервые было 13 задач, раньше было меньше.
Вот тут результаты: http://icpc.baylor.edu/scoreboard/
Разбор был в процессе тура на icpclive.com
В этом году достаточно халявный финал, обычно бывает сложнее. Плюс впервые было 13 задач, раньше было меньше.
Вот тут результаты: http://icpc.baylor.edu/scoreboard/
мгушники тоже неплохо выступили
кто их тренирует нынче?
кто их тренирует нынче?
МГУшников никто не тренирует, по сути.
На мехмате орг.вопросами занимается Антон Панкратев (он же директор московского четвертьфинала), на ВМК пока еще Андрей Шестимеров, не знаю что будет в следующем году с ВМК. Нынешняя команда формально относилась к мехмату. В следующем году есть две сильные команды, одна формально с ВМК, другая с мехмата и обе примерно одинаковой силы. Так что будет веселый замес МГУшных команд на полуфинале.
Молодежи хорошей в МГУ поступает мало, потому что Вышка и СПбАУ гораздо эффективнее пиаряться.
На мехмате орг.вопросами занимается Антон Панкратев (он же директор московского четвертьфинала), на ВМК пока еще Андрей Шестимеров, не знаю что будет в следующем году с ВМК. Нынешняя команда формально относилась к мехмату. В следующем году есть две сильные команды, одна формально с ВМК, другая с мехмата и обе примерно одинаковой силы. Так что будет веселый замес МГУшных команд на полуфинале.
Молодежи хорошей в МГУ поступает мало, потому что Вышка и СПбАУ гораздо эффективнее пиаряться.
А они там оба были. Вот кстати интервью Петра. Говорит что в гугле таких задач нет, поэтому чтобы развиваться продолжает принимать участие в соревнованиях.
Смотреть с 5:38:22
А если по второму потоку открыть на 3:38:20 можно услышать как матеряться физтехи))
Смотреть с 5:38:22
А если по второму потоку открыть на 3:38:20 можно услышать как матеряться физтехи))
В этом году достаточно халявный финалПролистал задачки.... не пойму, в чем сложность задачи на набор текста на клавиатуре? строишь граф из каждого узла и бинго! - кратчайший путь найден. тут же вообще думать не надо. Не подскажешь, что я упустил?
upd: а, ну, да, сам понял... повторяющиеся буквы, разные маршруты. Ну, все равно графы и в лоб решение
Попробуй жадно написать слово TRAP с такой клавиатурой (начинаешь сверху слева):
RRRRRRRRR
ARTTTTRAP
A--------A-
A--------A-
AAAAAAAA
RRRRRRRRR
ARTTTTRAP
A--------A-
A--------A-
AAAAAAAA
жадноне знаю, что значит "жадно", но проблем не увидел...
1 начальный узел (ребята, поехали!), 1 конечный(ребята поехали!(тм)) по пути помним "вес" тропинок между узлами. Ну, да лана, забей, поиграюсь, как время будет, сам
По какому принципу ты выбираешь следующую букву?
не пойму, в чем сложность задачиВо-первых, ты не школьник (например, я теперь могу даже с мат. олимпиады задачи многие быстро решить, хотя в школе не мог), во-вторых, олимпиады по программированию сложные в том смысле, что надо качественно и очень быстро запрогать правильный алгоритм, а сама проблема не шибко сложная.
Во-первых, ты не школьникОлимпиада студенческая, а не школьная.
олимпиады по программированию сложные в том смысле, что надо качественно и очень быстро запрогать правильный алгоритм, а сама проблема не шибко сложная.ну так алгоритм ещё придумать надо...
ну так алгоритм ещё придумать надо...Там не такие прям алгоритмы, что надо придумать метод мегасортировки или как решать задачу оптимизации. Если алгоритм слишком сложный - это уже чистая математика.
Посмотри на команду из МГУ, например. Три мехматянина, среди них у одного было две золотых медали по математике на школьном межнаре.
И что в этом хорошего. Надо понимать, что программирование в реальной жизни скорее антиматематично.
По какому принципу ты выбираешь следующую букву?я еще не начал решать их... и вообще, сматываю на шашлыки прямо сейчас
Но решить очень хочу сам и без подсказок. Осенью чемп от мэил-ру, наконец, хочу полноценно поучаствовать, а не в последние два дня до закрытия песочницы, так что слегка размять ум не помешает
Что до задачи, то пока просто наметки в уме. Надо за комп сесть
Букву выбирать буду по принципу "все на поле". (Не критиковать! решать еще не взялся.) Просто то, что сходу видится: если слово "бобёр", то от старта буду бежать ко всем буквам "б" и самая ближайшая, не обязательно будет в финальной последовательности. Тропинки можно хранить где угодно. Короче, граф - он и в африке граф.
Не знаю, в общем, надо решать.
Ну а на олимпиадах по программированию высокого уровня математично.
Посмотри на команду из МГУ, например. Три мехматянина, среди них у одного было две золотых медали по математике на школьном межнаре.Справедливости ради, Глеб Евстропов с ВМК. У него и у Миши Пядеркина есть медальки IOI, у Вити Омельяненко - IMO. Витя раньше прогать не особо умел, но прокачался очень сильно за время учебы в универе (под давлением сокомандников).
Иметь хорошего математика в команде очень полезно, обычно на туре есть 1-2 задачи где нужно знать какой-нибудь олимпиадно-математичный факт или просто применить что-нибудь эдакое. Иногда бывает тактика, что вообще пишет 1 человек в команде, при этом условия он даже не читает. А оставшиеся двое просто говорят, что писать.
в чем сложность задачи на набор текста на клавиатуре?Сложность в том, что в этом графе огромное количество вершин, а проверочные данные содержат все худшие случаи для всех решений в лоб. BFS не потянет по памяти. DFS не потянет по времени работы, которое ограничено 4 сек. Алгоритм Dijkstra сам по себе не подходит, надо искать способ построения эвристики для A*, и то не факт, что получится. Здесь нужен граф, который построен не в лоб.
Но решить очень хочу сам и без подсказок. Осенью чемп от мэил-ру, наконец, хочу полноценно поучаствовать, а не в последние два дня до закрытия песочницы, так что слегка размять ум не помешает
Осенью у мейла AI cup, это все-таки из другой категории. Там больше чем поиск пути в графе из стандартных алгоритмов ничего, вроде бы, и не нужно. Да и времени вагон.
Если хочется for fun поучаствовать в спортивном программировании, то лучше писать туры на codeforces, там весело.
Ну и студенты чтобы подготовиться к этим соревнованиям проводят по две пятичасовые тренировки в неделю в течение нескольких лет плюс еще лично качаются. Китайцы еще больше. Так что лучше участвовать в соревнованиях, где задачи больше похожи на реальные. Например, 20 июня будет Internet Problem Solving Contest с довольно забавными задачами. А в течение года проходят еще Marathon 24 и Challenge 24, где могут участвовать не только студенты и задачи там бывают прикольные. Например, подсчитать количество взорвавшихся попкорнин по аудизаписи.
Еще завтра с 13:00 до 15:00 Мск будет последний отбор Russian Code Cup, можно успеть. Там топ-200 из следующего этапа будут давать футболочки с деревом Фенвика.
Разбор задачи про клавиатуру на видео в 4:02, если что.
Справедливости ради, Глеб Евстропов с ВМК.да, ошибся.
Сложность в том, что в этом графе огромное количество вершин, а проверочные данные содержат все худшие случаи для всех решений в лоб. BFS не потянет по памяти. DFS не потянет по времени работы, которое ограничено 4 сек. Алгоритм Dijkstra сам по себе не подходит, надо искать способ построения эвристики для A*, и то не факт, что получится. Здесь нужен граф, который построен не в лоб.Зачем граф? Для пар символов нужно знать только расстояние из одного до каждой точки другого. Это меньше 900 пар. По парам (которые дают дельты) уже элементарно высчитать общее минимальное расстояние нужным образом.
Для пар символов нужно знать только расстояние из каждой точки одного до каждой точки другого.Ты утверждаешь, что это не граф?
Нет, потому что эту карту можно хранить в виде матрицы для всех пар от одного символа. Да и нужна она для ускорения. А так можно все посчитать на исходном массиве и его копии.
Нет, потому что эту карту можно хранить в виде матрицы для всех пар от одного символа.То есть граф, представленный в каком-то другом виде - это уже не граф?
Слушай, у тебя по делу есть, что сказать или предпочитаешь как препод на экзамене к терминам доебываться? Графом можно назвать все что угодно, поэтому когда объект имеет более конкретное и компактное представление, я считаю нужным называть его иначе. В данном случае, объект задачи - двумерная прямоугольная сетка на которую наложена некоторая карта. Этот шаблон мега часто используется в задачах и основной метод работы с ним - рекурсивное вычисление волны от какого-нибудь источника. В отличие от абстрактного графа, сразу понятно сколько надо времени, памяти, какие топологические свойства имеются и т.д.
Слушай, у тебя по делу есть, что сказать или предпочитаешь как препод на экзамене к терминам доебываться?Начнём с того, что я не доёбывался. Я написал, что нужен граф, построенный не в лоб. А ты доебался до термина "граф".
Я просто не хочу использовать термин для более абстрактной модели представления данных, когда есть более простая. В этом разница между математикой и программированием - выбор модели (пусть они даже эквивалентны) радикально может поменять сложность алгоритма и время выполнения.
Я тоже утверждаю, что это не граф ;-)
Ну т.е. представить клавиатуру как граф конечно можно, но совершенно бесполезно: мы не можем решить задачу жадно, т.е. предугадать какая из кнопок с одной и той же буквой нам нужна, не видя все остальные.
Что нам нужно сделать:
1. Сделать коллекцию буква -> координаты всех экземпляров этой буквы. Всего потребуется до 50*50 = 2500 записей.
2. Для слова решать задачу динамикой от позиции в слове: на каждом шаге у нас есть минимальное количество шагов, которое позволяет написать слово до предыдущей позиции (до каждого из экземпляров предыдущей буквы). Следующий шаг вычисляем так: для каждого экземпляра буквы берём минимум по переходам из всех предыдущих допустимых положений. Т.е. каждый шаг мы делаем не больше 2500*2500 = 6250000 подсчётов.
3. Ответом будет минимум из последнего шага динамики. Слово длины до 10000, т.е. общее количество действий порядка 62500000000 = 62.5 * 10^9.
Это примерно вмещается в ограничения задачи (4 секунды), но может суток выпадать на худших случаях (не знаю на чем они тестят). Если выпадает, то имеет смысл добавить оптимизацию для худшего случая, когда есть только одна/несколько букв. Думаю тут можно учесть свойство, что все одинаковые буквы соединены и перессчитывать расстояние не от каждой предыдущей, а от части.
Да, по поводу графов: они не нужны, это точки на плоскости, расстояние = сумме разностей координат по модулю.
Ну т.е. представить клавиатуру как граф конечно можно, но совершенно бесполезно: мы не можем решить задачу жадно, т.е. предугадать какая из кнопок с одной и той же буквой нам нужна, не видя все остальные.
Что нам нужно сделать:
1. Сделать коллекцию буква -> координаты всех экземпляров этой буквы. Всего потребуется до 50*50 = 2500 записей.
2. Для слова решать задачу динамикой от позиции в слове: на каждом шаге у нас есть минимальное количество шагов, которое позволяет написать слово до предыдущей позиции (до каждого из экземпляров предыдущей буквы). Следующий шаг вычисляем так: для каждого экземпляра буквы берём минимум по переходам из всех предыдущих допустимых положений. Т.е. каждый шаг мы делаем не больше 2500*2500 = 6250000 подсчётов.
3. Ответом будет минимум из последнего шага динамики. Слово длины до 10000, т.е. общее количество действий порядка 62500000000 = 62.5 * 10^9.
Это примерно вмещается в ограничения задачи (4 секунды), но может суток выпадать на худших случаях (не знаю на чем они тестят). Если выпадает, то имеет смысл добавить оптимизацию для худшего случая, когда есть только одна/несколько букв. Думаю тут можно учесть свойство, что все одинаковые буквы соединены и перессчитывать расстояние не от каждой предыдущей, а от части.
Да, по поводу графов: они не нужны, это точки на плоскости, расстояние = сумме разностей координат по модулю.
Откуда у тебя 900 пар?
Ну граф - это пароход и человек структура данных и способ представления. В данный момент он нам не нужен, т.к. нам не нужен его матаппарат: нас не волнует через какие мы вершины проходим и мы и без графа знаем минимальную длину между конкре ными вершинами.
т.е. общее количество действий порядка 62500000000Сколько у тебя выполняется пустой цикл такого размера, и на чём ты его тестируешь?
Да, по поводу графов: они не нужны, это точки на плоскости, расстояние = сумме разностей координат по модулю.Расстояние от первого 0 до 1 вот тут равно 1, а разница координат по модулю равна 10:
00000000001
Кажется, должно делаться динамикой, если для начального куска длины k хранить длину минимального пути для всевозможных пар "начальный узел пути — конечный узел пути".
По поводу расстояния ты прав, чуток по-другому значит считать нужно. Впрочем это всё можно легко предрассчитать.
Цикл такого размера без тела оптимизируется и будет неинтересно ;-) если считать, что у нас процессор в 2GHz и сравнение выполняется за единицу, то получим 30 секунд вместо 4х, что реально оптимизировать (вырожденный случай с одной буквой не интересен, для двух букв уже получаем 1250 * 1250 в качестве худшего случая).
Цикл такого размера без тела оптимизируется и будет неинтересно ;-) если считать, что у нас процессор в 2GHz и сравнение выполняется за единицу, то получим 30 секунд вместо 4х, что реально оптимизировать (вырожденный случай с одной буквой не интересен, для двух букв уже получаем 1250 * 1250 в качестве худшего случая).
Кажется, должно делаться динамикой, если для начального куска длины k хранить длину минимального пути для всевозможных пар "начальный узел решётки — конечный узел решётки".Сложность в том, что пар может быть порядка N^2; а длина слова 10^5
Не сами пары, а их длину, подсчитанную динамикой: на каждом шаге не более n = 50* 50 пар (начальная точка закреплена)
По поводу расстояния ты прав, чуток по-другому значит считать нужно. Впрочем это всё можно легко предрассчитать."Чуток" - это на графе?
Цикл такого размера без тела оптимизируется и будет неинтересно ;-) если считать, что у нас процессор в 2GHz и сравнение выполняется за единицу, то получим 60 секунд вместо 4х, что реально оптимизировать (вырожденный случай с одной буквой не интересен, для двух букв уже получаем 1250 * 1250 в качестве худшего случая).Добавь туда тело и посмотри. На C++ в релизе я получил ~100кк циклов в секунду с одним if внутри.
Не сами пары, а их длину, подсчитанную динамикой: на каждом шаге не более n = 50* 50 пар (начальная точка закреплена)Тогда да, я тоже решаю в этом направлении. Но сначала предрассчитываю минимальную длину между всеми парами символов. Но написал это в лоб, и в 15 примере не умещаюсь по времени.
"Чуток" - это на графе?нет. Граф не учитывает направление движения для проскакивания (ну или напиши как ты его сделаешь). Вот тем временем ещё один пример для TRAP:
TOLKR
RRRRR
RZXPA
Граф не учитывает направление движения для проскакивания (ну или напиши как ты его сделаешь).Я для разминки решил эту задачу в лоб через BFS. Все ответы верные, но такой подход не умещается по памяти и времени работы на 14, 15 и 16 примерах. Клавиатура и текст представляют из себя циклический направленный граф, из каждой вершины можно перейти максимум в 5 направлений.
Вот тем временем ещё один пример для TRAPТвои примеры без *, а по условию она обязательна. Если заменить X на *, то ответ будет 12.
Добавь туда тело и посмотри. На C++ в релизе я получил ~100кк циклов в секунду с одним if внутри.я с телефона. 100kk - это как-то маловато, но, как ты сам понимаешь, if выполняется дольше всего, его процессор не распараллелит.
Ок, а какой будет граф у тебя для такой клавиатуры?
я с телефона. 100kk - это как-то маловато, но, как ты сам понимаешь, if выполняется дольше всего, его процессор не распараллелит.Мне кажется, что O(K*N^2) никак не засунуть в 4 секунды. Как ты понимаешь, здесь код посложнее одного if. Тем более, если писать не на Си++
Ок, а какой будет граф у тебя для такой клавиатуры?Для твоего примера из TRAP? Я не знаю, какой он будет визуально. Думаю, что достаточно большой и вряд ли планарный, чтобы нарисовать на форуме. Но это не лишает нас возможности применить BFS.
Алгоритм - предполагая, что для буквы М посчитан минимальный путь для всех символов, для следующей буквы посчитать тоже самое методом волны, затем повторить для следующей и т.д. Каждый шаг K^2 операций, всего нужно N шагов - т.е. сложность K^2*N.
В принципе, вместо того, чтобы считать на каждом шаге в лоб, можно предрассчитать для всех пар в задаче дельту перехода. Это потребует памяти что-то типа 50*50*25, времени K^3, но потом время каждого шага существенно уменьшится. Сложно сказать насколько, но если есть все буквы и они равной величины, то в десяток - два раз наверно.
В общем, эта оптимизация и есть геморрой для олимпиадников, состязание на скорость.
В принципе, вместо того, чтобы считать на каждом шаге в лоб, можно предрассчитать для всех пар в задаче дельту перехода. Это потребует памяти что-то типа 50*50*25, времени K^3, но потом время каждого шага существенно уменьшится. Сложно сказать насколько, но если есть все буквы и они равной величины, то в десяток - два раз наверно.
В общем, эта оптимизация и есть геморрой для олимпиадников, состязание на скорость.
Вот мои мысли по оптимизации:
1. Хранить отсортированную матрицу смежности от каждой буквы до всех экземпляров следующей буквы.
2. На каждом шаге сортировать экземпляры предыдущей буквы по расстоянию до неё из старта.
Так мы сможем не проверять от каждой к каждой, а прерваться быстрее.
1. Хранить отсортированную матрицу смежности от каждой буквы до всех экземпляров следующей буквы.
2. На каждом шаге сортировать экземпляры предыдущей буквы по расстоянию до неё из старта.
Так мы сможем не проверять от каждой к каждой, а прерваться быстрее.
Здесь не нужен перебор. Это легко понять, если вспомнить, что сам путь не нужен, а нужно только минимальное расстояние.
Под методом волны ты понимаешь это?
У нас нет непроходимых участков и курсор проскальзывает.
У нас нет непроходимых участков и курсор проскальзывает.
Посмотри пожалуйста внимательное, что я перебираю.
Под методом волны ты понимаешь это?Когда состояние вершины меняет под влиянием соседних вершин и есть некая граница на это состояние. Например минимальное расстояние до некоторой точки. Проскальзывание меняет только смежность, но не несет принципиальных проблем.
Зачем граф?Знание о графовой природе задачи дает возможность использовать алгоритмы для графов.
Это граф с хорошими свойствами:
- планарный
- всюду плотный
- образует пространство с Манхэттенским расстоянием:
r(.., A, ..) = r(.., A) + r(A, ..)
r(path) = rx(path)+ry(path)
ri(A, B) = Bi - Ai, i: x,y
ri(A, B, C) = ri(A, C), для Ai < Bi < Ci (и аналогично для смены '<' на '>')
ri(A, B, C) = ri(A, C) + 2*ri(B, A) для Bi < Ai < Ci
ri(A, B, C) = ri(A, C) + 2*ri(C, B) для Ai < Ci < Bi
Свойства задачи:
R - лучшее расстояние
большая буква - координаты известны, маленькая - не известны
V - кол-во вариантов (мощность множества)
O - оценка производительности
R('CONTEST') = R(C, o, n, t, e, s, t)
R(.., b, ..) = min(R(.., Bi, ..))
R(A, B) = r(A, B)
R(path) = min(перебор(r(path)))
O(R(p1 .. pn)) = V(p1)*..*V(pn)
ps
Не закончил, переключился на другую задачу. Дальше собирался расписать свойства оптимального перебора.
Цель: записать все знания о задаче и об алгоритме её решения в формализованном сжатом виде.
Над-цель: автоматическая генерация кода для оптимального перебора на основе формализованного представления о задаче
Мета-цель: научиться записывать знания о свойствах оптимального перебора в формализованном виде
Мета-цель(2): научиться записывать сжатый формализованный вид, который:
- читабелен для человека: максимально компактный, опущено множество деталей, который восстановимы из контекста
- достраивается до полного формализованного представления автоматическим образом
Присоединяйтесь!
Дико извиняюсь за спойлер с решением, но вас уже читать больно.
Что касается производительности системы, то есть стандартный тест для проверки скорости тестирующей машины - алгоритм Флойда на int'ах. На финале влезло 1650^3 за 2 секунды, т.е. производительность около 2*10^9 элементарных операций в секунду. Примерно как везде, никаких чудес.
Что касается производительности системы, то есть стандартный тест для проверки скорости тестирующей машины - алгоритм Флойда на int'ах. На финале влезло 1650^3 за 2 секунды, т.е. производительность около 2*10^9 элементарных операций в секунду. Примерно как везде, никаких чудес.
Алгоритм - предполагая, что для буквы М посчитан минимальный путь для всех символов, для следующей буквы посчитать тоже самое методом волны, затем повторить для следующей и т.д. Каждый шаг K^2 операций, всего нужно N шагов - т.е. сложность K^2*N.Если применить волну в лоб (как BFS), то это никак не уместится в 4 секунды. Может быть так, что волна от вершины с меньшим весом придёт в вершину, в которую мы уже пришли с большим весом.
Пришло решение применить идею Dijkstra для обновления расстояний. Это может сократить сложность где-то до 10.000 * 2500 * log 100.000, что реально вместить в 4 сек.
посчитать тоже самое методом волныwave = перебор-графа-в-ширину
O(wave(двумерный-пространственный-граф)) = O(r-min^2), где r-min - это ответ задачи (расстояние наименьшего пути))
недо-худший случай:
строка вида AZ..AZ, где A и Z расположены на противоположных углах
O(wave, худший случай) = r-min(худший_случай)^2=(100* 10000)^2 = (10^2*10^4)^2 = 10^12
Дико извиняюсь за спойлер с решением, но вас уже читать больно.Злодей, ты написал его ровно в тот момент, когда я набивал свой пост.
Я даже не успел написать код.за спойлер с решениемЕсть ли более производительное решение?
Из очевидного только дооптимизировать Дейкстру в этом частном случае до O(N), что вполне реально. Можно смотреть в гугле в сторну "Dijkstra Buckets". Кажется, что быстрее O(NM) нельзя сделать даже в теории, но формально доказывать это сходу я не умею.
Если применить волну в лоб (как BFS), то это никак не уместится в 4 секунды. Может быть так, что волна от вершины с меньшим весом придёт в вершину, в которую мы уже пришли с большим весом.Ну и че, понятно, что первый с ходу алгоритм будет не самым оптимальным, но как раз в этом и состоит олимпиадное задротство, чтобы знать на зубок все вариации. Вон гу написал, что делать надо как я и писал выше, только использовать оптимизированный алгоритм.
Ну и че, понятно, что первый с ходу алгоритм будет не самым оптимальным, но как раз в этом и состоит олимпиадное задротство, чтобы знать на зубок все вариации. Вон гу написал, что делать надо как я и писал выше, только использовать оптимизированный алгоритм.Конечно, это понятно, поэтому мы здесь и обсуждали варианты разных решений. В твоём примере ничего не было о применении структур типа heap, а это ключевая идея решения.
Я одновременно с Gu написал свой пост про применение идеи Dijkstra. Если бы не его спойлер, то подкрепил бы эту идею кодом. В итоге задачка всё-таки решилась на графе стандартным алгоритмом.
Вообще, изначально вопрос был о сложности задач. Я не увидел ничего, что бы его подтвердило. Ну да, нужно извращаться, чтобы задача решилась не за 8 секунд, а за четыре и нужно быстро это закодировать, но это не сравнимо с математикой, например, где задача либо решается, либо, что вероятнее, не решается вообще никак.
Вообще, изначально вопрос был о сложности задач. Я не увидел ничего, что бы его подтвердило.У меня решение этой задачи вместе с написанием кода заняло около 6 часов. Мысль про возможность использования heap пришла уже сегодня. При этом я всё время сидел на форуме и не заметил ни одного решения, которое бы уложилось в 4 секунды.
Ну да, нужно извращаться, чтобы задача решилась не за 8 секунд, а за четыре
Разница простого BFS и Dijkstra в коэффициенте *10.000 или *log10.000, ни о каких 8 секундах на полное решение тут речи быть не могло. Сложность задачи в том, что тестовые примеры содержат данные, которые приводят именно к полному выгребанию алгоритмической сложности.
Попробуй жадно написать слово TRAP с такой клавиатурой (начинаешь сверху слева):Может, он не жадно, а кратчайшим путем из всех начальных вершин во все конечные?
Вот тут результаты: http://icpc.baylor.edu/scoreboard/
А что значат верхние и нижние цифры в ячейках?
А что значат верхние и нижние цифры в ячейках?Предположение: кол-во попыток и время (через сколько от начала прислали работающее решение)
Жалко, что нет метрики по бенчмаркам (у кого решение быстрее/меньше памяти жрет).
Я туплю или ты хочешь запускать дейкстру каждый ход?
Тогда сформулировано плохо, было ощущение, что ищется просто ближайшая буква. Учитывая, что автор сам исправился - так и было.
Я туплю или ты хочешь запускать дейкстру каждый ход?От вершин с текущей буквой одновременно ко всем со следующей. На первом шаге просто складывай их в heap с текущим насчитанным весом.
А в чём преимущество перед тем, чтобы просто посчитать это заранее?
А в чём преимущество перед тем, чтобы просто посчитать это заранее?Посчитать кратчайший путь от каждой к каждой по нужным парам? Это слишком долго. Здесь же получается 10.000 * 10.000 * log 1.250 или что-то в этом роде.
Посчитать кратчайший путь от каждой к каждой по нужным парам? Это слишком долго.От одной ко всем = от одной к одной по макс трудозатратам, так что.
От одной ко всем = от одной к одной по макс трудозатратам, так что.После вычисления путей всё равно искать оптимальный обход.
Это слишком долго.это не может быть дольше, т.к. тебе всё равно придётся его считать.
это не может быть дольше, т.к. тебе всё равно придётся его считать.Сам по себе подсчёт ничего не даст, после него нужны ещё вычисления той же сложности. Он не нужен.
Большей ;-)
Сам предрассчет даст то, что ты сможешь сосредоточиться на оптимизации действительно важной вещи, а не будешь тратить время на него. + программа станет проще так что у тебя будет меньше багов.
Сам предрассчет даст то, что ты сможешь сосредоточиться на оптимизации действительно важной вещи, а не будешь тратить время на него. + программа станет проще так что у тебя будет меньше багов.
Фокус в том, что мы можем запускать Дейкстру сразу от многих вершин, а не от каждой отдельно.Можешь расскрыть мысль, как это сделать не меняя ассимптотику?
Во время начальной инициализации запиши нули сразу в несколько вершин и все. Это эквивалентно тому, что ты добавил фиктивную начальную вершину и соединил ее дугами нулевого веса с нужным тебе множеством вершин, а затем сделал один шаг алгоритма.
Сам предрассчет даст то, что ты сможешь сосредоточиться на оптимизации действительно важной вещи, а не будешь тратить время на него. + программа станет проще так что у тебя будет меньше багов.Наверное, я не понимаю, о каком предрасчёте ты ведёшь речь. Всё, что приходит мне в голову, только усложняет код и повышает оценку по времени. Ты лучше напиши алгоритм решения.
Кстати, для незнающих теорию: а как ведет себя Дийкстра, когда есть нулевые ребра?
Абсолютно нормально. Главное чтобы отрицательных не было.
Во время начальной инициализации запиши нули сразу в несколько вершин и все. Это эквивалентно тому, что ты добавил фиктивную начальную вершину и соединил ее дугами нулевого веса с нужным тебе множеством вершин, а затем сделал один шаг алгоритма.
В этой задаче не нули, а длины путей до этих ячеек из предыдущего шага, но абстракция с фиктивной вершиной хорошая.
Оставить комментарий
markyzz
А что там за задачи были, кто-нить знает?