1

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

Спасибо.

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

Для вычисления позиции числа X в списке сумм можно просто пройтись по всем элементам первого массива и для каждого из них - обозначим его через A\[i\] - с помощью двоичного поиска по второму массиву определить, сколько есть элементов, меньших X-A\[i\]. Сумма этих количеств даст нам искомую позицию X.

Итоговая асимптотика будет N log M log A, где A - величина чисел. Наверняка есть и более быстрые решения - как минимум, от вложенного двоичного поиска можно избавиться методом двух указателей. Но два бин. поиска, кажется, реализовать быстрее всего.

2

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

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

3

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

Для правильного учёта бесконечности, кажется, ничего особого не нужно, кроме аккуратного разбора случаев? Если мы построим текст как s+s (т.е., припишем строку к себе), то если у строки s[0..] и строки s[i..] совпадающая часть доходит до конца текста, то, кажется, верно будет считать их совпадающими на всей бесконечности. Или есть контрпример?

4

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

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

5

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

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

6

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

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

7

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

Thanks!

8

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

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

9

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

a.a.maleev пишет:

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

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

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

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

10

(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.

11

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

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

12

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

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

13

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

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

14

(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.

15

(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 имеет небольшую длину, - эти алгоритмы могут работать гораздо быстрее).

17

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

Thank you!

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

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

19

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

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

20

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

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

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

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

21

(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.

22

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

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

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

23

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

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

24

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

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

25

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

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