Нарезка одинаковых палочек из разных палочек

10

У вас есть палочек произвольной длины, не обязательно интегральных.n

Отрезая несколько палочек (один разрез режет одну палку, но мы можем резать так часто, как мы хотим), вы хотите получить палочек, которые бы:k<n

  • Все эти палочек имеют одинаковую длину;k
  • Все палок, по крайней мере, такие же, как и все остальные палочки.k

Обратите внимание, что мы получаем палочек после выполнения надрезов.Cn+CC

Какой алгоритм вы бы использовали, чтобы количество необходимых сокращений было минимальным? И что это за номер?

В качестве примера возьмем и любой . Можно использовать следующий алгоритм:n 2k=2n2

  • палочки в порядке убывания длины так, чтобы .L1L2Ln
  • Если то вырежьте палку № 1 на две равные части. Теперь есть две палки длиной , которые по крайней мере равны остальным палкам .л 1 / 2 2 ... пL12L2L1/22n
  • В противном случае ( ) разрезаем палку № 1 до двух неравных кусков размеров и . Теперь есть две палки длиной , которая длиннее, чем а остальные палочки .L 2 L 1 - L 2 L 2 L 1 - L 2 3 nL1<2L2L2L1L2L2L1L23n

В обоих случаях достаточно одного разреза.

Я попытался обобщить это для больших , но, похоже, нужно рассмотреть много случаев. Можете ли вы найти элегантное решение?k

Эрель Сегал-Халеви
источник

Ответы:

6

Первое основное замечание для решения этой проблемы заключается в том, что целесообразность длины резания ,l

Feasible(l)=[i=1nLilk] ,

кусочно-постоянный, левый-непрерывный и не возрастающий по . Поскольку количество необходимых разрезов ведет себя одинаково, поиск оптимальной длиныl

l=max{lFeasible(l)} .

Кроме того, как предложили другие ответы, все скачки скачков имеют вид . Это оставляет нас с дискретной, одномерной задачей поиска, поддающейся бинарному поиску (после сортировки конечного набора кандидатов).Li/j

Кроме того, обратите внимание, что нам нужно учитывать только , которые короче длинного, поскольку это всегда выполнимо.Lik

Тогда различные оценки на приводят к алгоритмам различной эффективности.j

  • 1jk приводит к пространству поиска квадратичного размера (в ),k
  • 1jk/i в уравнении (при условии, что отсортированы по убыванию размера), иLi
  • немного более сложные оценки в линейной.

Используя это, мы можем решить предложенную задачу во времени и пространстве .Θ(n+klogk)Θ(n+k)

Еще одно наблюдение состоит в том, что сумма в увеличивается в на для каждого кандидата «прошедшего», считая дубликаты. Используя это, мы можем использовать выбор ранга вместо бинарного поиска и получить алгоритм, который работает во времени и пространстве , что является оптимальным.Feasiblel1Li/jΘ(n)

Подробнее об этом читайте в нашей статье « Эффективные алгоритмы разделения палочек без зависти с минимальными разрезами» (Reitzig and Wild, 2015).

Рафаэль
источник
Как выясняется, идеи нашего подхода к режущим стержням переносятся на более общую проблему или (пропорциональное) распределение , проблему практической значимости; см. нашу короткую статью об этом .
Рафаэль
4

Как подсказывает @randomA, мы будем действовать в два этапа: сначала мы найдем набор палочек, которые будут разрезаны, а затем сведем к минимуму количество разрезов.

Как и в особом случае в вопросе, мы сортируем / палочки так, чтобы . Это занимает время.L1L2LnO(nlogn)

Как указал @ user1990169, нам никогда не придется вырезать кусок, который .ik

На первом этапе мы используем бинарный поиск, чтобы найти число , , так что стики можно разрезать как минимум на кусков размера (плюс несколько меньших кусочков) , но палочки нельзя разрезать на кусков размером . Это займет времени.s1sk1,,skLs1,,s1kLs1O(klogk)

Если , это значение является оптимальным размером, и мы можем пропустить второй этап.Ls1=Ls

В противном случае мы знаем, что оптимальный размер удовлетворяет а если то получается в результате разрезания хотя бы одной из палочек на куски одинакового размера. Фаза два будет определять :oLs1>oLso>Lsoo

Для каждого стержня , , определите набор подходящих размеров следующим образом: Если разрезание на куски размером превращает стержень в куски (включая более короткий, если он есть), то кандидаты на это stick - это все значения , где и . (См . Ответ @ user1990169, почему это единственные размеры кандидатов.)i1isLsriLijjriLij<Ls1

Поддерживать для каждого размера кандидата, как часто это происходило. Используя сбалансированное дерево поиска, это можно сделать в , поскольку общее количество размеров кандидатов ограничено .O(klogk)iri2k

Теперь размер кандидата, который встречается чаще всего и приводит к правильному сокращению, является тем, который дает нам оптимальное решение. Кроме того, если какой-либо размер кандидата приводит к правильному резанию, любой меньший размер также приведет к правильному резанию.

Таким образом, мы снова можем использовать бинарный поиск, чтобы найти наибольшую длину кандидата, которая приводит к действительному сокращению в . Затем мы перебираем набор длин кандидатов до этого порога и находим тот, у которого наибольшее множество среди них в .O(klogk)O(k)

В итоге мы получаем время выполнения в или , если мы игнорируем (или не должны делать) начальную сортировку.O(nlogn)O(klogk)

FrankW
источник
На шаге бинарного поиска, как именно вы проверяете можно ли «нарезать палочки как минимум на кусков размером »? 1,,skLs
Эрл Сегал-Халеви,
Для вычислим . Сумма этих значений - количество штук, которые вы можете получить. 1isLi/Ls
FrankW
«Размер кандидата, который встречался чаще всего ... это тот, который дает нам оптимальное решение» - почему?
Эрель Сегал-Халеви,
Потому что каждый раз, когда это происходит, у нас есть палка, которая дает куски с порезами . tt1
FrankW
1
Общее число разрезов в лучшем случае ( палочки одинаковой длины, все остальные палочки в большей половине тех пор , как они , и, насколько я могу видеть , никогда не будет больше , чем . (Это определенно никогда не будет больше , так как каждый разрез дает палку правильной длины и остатка. Но, кажется, мы всегда можем выбрать размер так, чтобы хотя бы один разрез оставил остаток правильной длины. хотя у меня есть доказательства этому.)k2k2k1k
FrankW
1

После того, как вы заказали палочки в порядке убывания их длины, тогда палка будет обрезана, только если все палки были обрезаны.LiL1,L2,...Li1

Теперь, поскольку , мы не будем делать разрез на палках далее, поскольку у нас всегда может быть палочек длиной .k<nLkkLk

Таким образом, теперь вместо мы имеем дело только с стиками (возможно, добавляя стик в целом), а максимальное количество разрезов, которое потребуется в худшем случае .nk1k=k1

Кроме того, если оптимальное количество порезов , то среди этих палочек должен быть по крайней мере один набор палочек, который должен быть взят целиком из 1 оригинальной палочки<k1k1 (либо по частям, либо по 1 штуке). ни одна часть этой оригинальной флешки не должна быть оставлена ​​«неиспользованной». Это связано с тем, что по принципу голубиного отверстия должен быть как минимум 1 разрез, который должен производить более 1 действующей палки.

Затем вы можете провести два вложенных цикла (оба до ). Внешний цикл должен обозначать номер стержня , все части которого должны быть взяты, а внутренний цикл должен обозначать количество частей изготовленных из этого стержня. Для каждого размера проверьте, можете ли вы получить выполнимые k палок, последовательно разрезая палки и, если можете, то обновите минимальные требуемые порезы, если текущий требуемый номер меньше.kij
LijL1

Общая сложность вышеупомянутого алгоритмаO(nlog(n)+k3)

Абхишек Бансал
источник
1

Идея высокого уровня - бинарный поиск.

Размер каждой из запрошенных k палочек будет, по крайней мере, наименьшей палкой и максимум самой большой. Поэтому мы продолжаем использовать бинарный поиск по размеру средней палки, посмотрим, какое число мы можем получить, если это больше заданного то мы знаем, что нам нужно выбрать новый эталонный размер кандидата. Таким образом, мы переходим к большему или меньшему, используя новый эталонный стик. Мы останавливаемся, когда меньше, чемkkkkk

Как только мы нашли соответствующий эталонный стержень, возникает угловой случай, когда нам нужно будет еще больше уточнить размер. Мы можем отсортировать все нарезанные палочки по количеству надрезов на них и размеру палочки. Выберите тот с наименьшим количеством сокращений и наименьшего размера. Уменьшите количество порезов на этой палочке на 1 и сделайте все вспомогательные палочки такого же размера. Это будет новый эталонный размер, проверьте, может ли этот новый размер привести к приемлемому . Признаюсь, я не знаю, как ограничить время выполнения в этом случае.k

Надеюсь, я смогу увидеть что-то полезное из других ответов.

InformedA
источник
2
Я думаю, что основная идея вашего подхода будет работать. Но ваше описание алгоритма не достаточно ясно, чтобы быть уверенным. Не могли бы вы добавить более подробный псевдокод?
Франк
@FrankW Я не слишком уверен в продолжительности, хотя. Я посмотрю, что есть у других людей, это довольно интересный вопрос.
Информировано