Настройки поиска (Страница 1 из 15)

Постановка задачи непонятная. Так как не сказано, что пути должны быть простыми, то ответ всегда будет либо ноль, либо бесконечность.

Можете ли вы привести ссылку на проблемсет, откуда взята эта задача, чтобы исключить возможность, что мы случайно вмешаемся в ход какого-нибудь соревнования?

Если не хочется суффиксным массивом, то альтернативно можно попробовать z-функцией, ведь она позволяет за O(1) сравнивать строку s[0..] со строкой s[i..] (поскольку z-функция сообщает нам позицию первого расхождения в этих двух строках).

Здравствуйте, попробуйте написать на codeforces.ru, там аудитория большая.
Но если кратко - то во главу угла надо ставить практику. Сейчас доступен огромный набор задач с разборами решения, и это (по крайней мере, из нашего опыта) - оптимальный способ осваивать новые темы.
А учить теорию по книгам - это хотя тоже важно и полезно, но тут надо остерегаться того, чтобы не начать "скакать по верхам". К примеру - до приступания к графам лучше как следует потренироваться на задачах с двумя числами (НОД / НОК / вариации на их тему) и массивами чисел (НОД / НОК / поиск повторяющегося числа / поиск отсутствующего числа / и т.п.). А при изучении теории графов - сначала изучить обходы в глубину и ширину и нарешать много задачек с их помощью, и только потом браться за более сложные темы (как, к примеру, алгоритм Дейкстры).

Здравствуйте. К сожалению, что-то не видно прикрепленного файла.
Называть меня "математиком" - это слишком громко, я всего лишь любитель, знакомый с математикой и алгоритмами в том объёме, в котором это помогает в олимпиадах.
Вопросы практической оптимизации лежат, зачастую, в другой плоскости, чем теоретические исследования: особенности выполнения процессором операций, поведения кеш-памяти и т.п. мало связаны с теоретическими изысканиями. И ответ зачастую зависит от условий, в которых должен применяться алгоритм. Поэтому нельзя заранее сказать, что важнее - экономить время или память.

Find maximum flow in this graph, where additionally N vertices are connected with the source vertex with edges with capacity=1, and M vertices are connected with the sink vertex with edges with capacity=Ki.

Здравствуйте. Боюсь, вы ошиблись форумом - потому что для решения вашей задачи требуются не алгоритмы, а использование конкретных средств вашей среды (WPF). Если не самая высокая производительность вас устроит, то можно просто отрисовывать график заново при каждом масштабировании/перемещении - это был бы самый простой вариант. Другой, более производительный, - нарисовать всё заранее в буфере в памяти, а при перетаскивании мышкой просто копировать нужную область на экран.

You should build a graph with 2 * N vertices: two vertices for each city (encoding which gear-mode is currently selected: for moving up or moving down).

UPD The edges in this new graph will have costs either 0 or 1, depending on whether we have to switch a gear-mode or not.

Большинство таких алгоритмов предназначены для особых случаев, и в общем случае (на произвольных строках и с большим алфавитом) работают не сильно лучше наивного алгоритма за O(n^2).

В статье, на которую ссылается Википедия ("A Survey of Longest Common Subsequence Algorithms" - Bergroth, Hakonen, Raita, 2000), написано:

В общем, как мне кажется, с точки зрения олимпиад изучение таких алгоритмов никакого профита не даст (хотя в каких-то отдельных ограниченных случаях - например, когда известно, что LCS имеет небольшую длину, - эти алгоритмы могут работать гораздо быстрее).

Исправил. Кстати, такие вещи удобнее постить в виде комментов внизу статьи

climbit
Эм, вообще-то у вас получилась циклическая динамика: из состояния можно прийти в себя же. Поэтому метод динамического программирования здесь не работает.

BVI94
Для решения избавимся от цикличности в игре. Переформулируя условие, за один ход каждый игрок может либо уменьшить расстояние между фишками (не более чем на K), либо увеличить его (не более чем на K, и не выходя при этом за пределы поля). Таким образом, мы получили игру, похожую на ним с увеличениями. Применяя аналогичные рассуждения, мы получаем, что делать ходы, увеличивающие расстояние между фишками, невыгодно, поэтому их можно не рассматривать.

Таким образом, мы получаем такую игру: есть кучка из N-2 камней (именно таково расстояние между клетками 1 и N), за один ход игрок может взять от 1 до K камней, и кто не может сделать ход - проигрывает. Такая игра решается простой динамикой за O (N * K), однако её решение можно получить и сразу, заметив, что эта игра - фактически k-ним, и ответ определяется просто остатком от деления на K+1.