1

(1 ответов, оставленных в Offtopic)

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

2

(1 ответов, оставленных в Feedback)

Thanks!

3

(2 ответов, оставленных в Offtopic)

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

4

(3 ответов, оставленных в Problems)

a.a.maleev пишет:

Помогите, пожалуйста, с задачкой:

На вход подается поток из N чисел (каждое можно считать только один раз). Известно, что среди них есть суперэлемент, который встречается не менее, чем N/2 раз. Найти этот элемент, использовав O(1) памяти.

Может быть, не "не менее", а "больше"? Иначе задача может иметь не единственное решение.

И если действительно "больше", то решать можно так: просто для каждого бита посчитать, сколько раз в
том бите стоит 0 среди N чисел, а сколько - 1, и выбрать самое популярное значение. Т.е. надо будет K ячеек памяти (где K - число бит во входных числах), т.е. O(1), если это заранее известная константа.

5

(3 ответов, оставленных в Problems)

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.

6

(2 ответов, оставленных в Problems)

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

7

(3 ответов, оставленных в Problems)

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

8

(2 ответов, оставленных в Problems)

Решение видится таким: давайте хранить текст в "сжатом" виде, т.е. в виде списка пар (буква, количество). Тогда, чтобы выполнить операцию I, надо найти пару, в середину которой будут вставляться новые буквы, разбить эту пару на две и вставить между ними добавляемые буквы. При таких ограничениях (всё до 1000) ничего более сложного не требуется, задача на реализацию.

9

(4 ответов, оставленных в Problems)

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.

10

(4 ответов, оставленных в Problems)

Why do you need adjacency matrix: it'll occupy 10000x10000 = 100M values? Use adjacency lists instead, their total size will be exactly 2*m.

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

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

Of the current methods, the O(n^2/ log n) algorithm of Masek and Paterson [28] is theoretically the fastest known.

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

12

(1 ответов, оставленных в Feedback)

Thank you!

DP is such a huge theme, that I'm not dare enough to start describing it smile

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

14

(7 ответов, оставленных в Problems)

Надо рассмотреть игру с одной кучкой: здесь применима обычная теория Шпрага-Гранди, поэтому можно запрограммировать (или посчитать на бумажке) значения функции Гранди для, скажем, первых 100 размеров. Уверен, в них найдётся какая-нибудь закономерность, что позволит получить решение за O(n).

15

(7 ответов, оставленных в Problems)

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

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

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

16

(6 ответов, оставленных в Problems)

Делаем двоичный поиск.

Изначально мы только знаем, что ответ где-то между 0 и 4.
Возьмём середину этого отрезка: X=2. Тогда получим, что можно получить 1/2+4/2+2/2=3 свечи, что меньше N=4. Следовательно, дальше надо пробовать только более короткие свечи, т.е. теперь интервал поиска - это [0..2].

Снова возьмём середину: X=1. Получим 1/1+4/1+2/1=7 свечей, что больше N=4.
Следовательно, можно пробовать свечи и большей, чем 1, длины. Поэтому новый интервал поиска - это [1..2].

Возьмём X=1.5, посчитаем, и т.д.

Через достаточно большое количество шагов (скажем, 100) мы достаточно близко сойдёмся к искомому ответу 1.333333333.

17

(6 ответов, оставленных в Problems)

Двоичный поиск

Т.е. мы двоичным поиском побираем такое максимальное X, при котором ещё можно получить N свечей.

18

(6 ответов, оставленных в Problems)

Двоичный поиск: будем искать двоичным поиском искомую длину. Тогда задача сводится к такой: по данной длине (обозначим её через X) проверить, можно ли получить >=N свечей этой длины. Для этого считаем сумму величин Li/X (округленных вниз) - это и есть максимальное количество свечей, которое можно получить с длиной X.

19

(15 ответов, оставленных в Problems)

Ну да, сделать какой-то флаг "величины path_exists_i" посчитаны, и если этот флаг стоит - то ничего для этого узла делать больше не надо. Это и называется "ленивым динамическим программированием" - когда мы вычисляем какие-то величины при первом требовании.

20

(15 ответов, оставленных в Problems)

Ну суффиксный автомат ацикличен, поэтому при подсчёте path_exists_i для текущего состояния мы можем считать, что для всех состояний, в которые есть рёбра из текущего состояния, всё уже посчитано. Поэтому мы можем просто брать ответы для них, а глубже уже не заходить.

21

(15 ответов, оставленных в Problems)

Нет-нет-нет, не надо никаких обратных суффиксных ссылок smile
Мы просто просматриваем рёбра, выходящие из каждого состояния.
Скажем, чтобы найти наличие пути из состояния v = 0, мы просматриваем рёбра, исходящие из состояния v = 0 в другие состояния, и использовать ответы, уже посчитанные для них.

22

(15 ответов, оставленных в Problems)

Ещё раз, мы склеиваем три строки через три разделителя, строим по получившейся строке суффиксный автомат. Далее для каждого состояния автомата обходом в глубину (или динамикой с меморизацией, как угодно называть) мы находим три булевских величины: path_exists_1, path_exists_2, path_exists_3, где path_exists_i означает "из текущей вершины есть путь, заканчивающийся символом, равным разделителю номер i, и при этом не содержащий других разделителей".

После этого ответом на задачу будет просто состояние v, для которого все три величины равны true (точнее, искомая подстрока будет длиннейшим путём из истока в это состояние v).

23

(3 ответов, оставленных в Problems)

wtq4er пишет:

>нужно явно хранить для каждой вершины номер её компоненты связности
не совсем понятно, что представляет из себя "номер компоненты связности", как "компоненты связности" вообще нумеруются. можно второй абзац подробнее объяснить?

Изначально мы считаем, что рёбер нет, т.е. граф состоит просто из N вершин. Каждая вершина - в отдельной компоненте связности, т.е. component[ i ] = i (что означает "вершина номер i находится в компоненте с номером i"). Также для каждой компоненты давайте хранить, какие вершины в неё входят - это некий массив списков vertices, где изначально vertices[ i ] = [ i ] (что означает "i-ая компонента содержит единственную вершину i").

Теперь будем добавлять в граф по одному ребру, в порядке убывания их весов. Пусть текущее ребро - это ребро между вершинами x и y. Пусть cx = component[x], cy = component[y]. Тогда, если cx = cy, то это ребро ни на что не влияет. Если же cx != cy, то надо записать ответ для всех пар вершин вида vertices[cx][ i ] и vertices[cy][ j ]. Затем эти две компоненты cx и cy надо соединить в одну. Для этого мы проходимся по списку vertices[cy] и присваиваем для них component = cx; затем мы в конец списка vertices[cx] добавляем весь список vertices[cy].

24

(2 ответов, оставленных в Feedback)

Исправил.

Спасибо всем за то, что оперативно писали о проблемах.

Вероятно, заражение произошло так: некий вирус попал ко мне на домашнюю машину, украл FTP-пароль и автоматически заразил все JavaScript-скрипты на сайте.

25

(2 ответов, оставленных в Algo)

Всех путей - очень много, точнее, их количество неполиномиально. Поэтому применять здесь bfs/dfs бессмысленно, нужен обычный рекурсивный перебор. Впрочем, его легко получить из алгоритма dfs, убрав использование отметок посещённости вершин (т.е. теперь мы будем пытаться заходить во все вершины, а не только непосещённые).