Пусть даны слова OPACKADOS и MABUDYDCMAB
1) Первым делом находим общие буквы в обоих словах. Как это сделать (через хэш, массив или полным поиском) — не принципиально. Общие буквы у них — ACD.
2) Для обоих слов создаем урезанные варианты (оставляем только общие буквы), и при этом запоминаем соответствие. Получаются слова ACAD и ADDCA, и соответствие [3,4,6,7] и [2,5,7,8,10].
3) Создаем массив размером произведения длин сокращенных слов, в нашем случае 4 * 5.
Выбираем слово ACAD проходим по нему с конца (начиная с буквы D). Для каждой такой буквы из первого слова проходим по второму в обратном порядке, и ищем совпадающие буквы. Когда буквы совпали, делаем проход по первому слову в правильном порядке, начиная с буквы справа от текущей (слева от D в нашем примере ничего нет, поэтому ничего не делаем) и смотрим что стоит в массиве для этой буквы и её положения. Находим максимальное значение, прибавляем к нем 1 и сохраняем в массиве в текущем положении и для всех леволежащих, пока не найдем число большее. И того у нас получается тройной цикл (по первому слову-по второму слову-по первому слову).
В чем смысл массива — значение в ячейке x,y говорит нам о максимальной подпоследовательности которая бы начиналась с x-места первом слове, y-места второго слова.
Чтобы было понятно приведу результаты обработки ACAD и ADDCA.
A [3 1 1 1 1]
C [2 2 2 2 0]
A [2 2 1 1 1]
D [1 1 1 0 0]
максимальное значение — 3. Теперь мы имеем в наличии длину искомой последовательности, и букву (положение) в первом слове, с которой она начинается.
4) Используя всё это и массив находим узлы (положение букв в обоих словах) за 1 проход.
В нашем случае A(1,1) C(2,4) A(3,5).
5) Возвращаемся к исходным словам, переводим по таблице соответствия наши узлы.
OPACKADOS и MABUDYDCMAB => A(3,2) C(4,8) A(6,10). После чего разбиваем наши слова на участки (между узлов, узлы не входят ). Берем первый участок первого слова, прибавляем первый участов второго слова и прибавляем сам узел, и так далее…
OP — M — A…
Вычислительная сложность что-то типа между O(n*n+m*n) в случае, если каждая буква встречается не чаще 1 раза и O(n*n*m) в случае, если все буквы одинаковы. Т.е. сложность между квадратичной и кубической.
Варианта с «все самые быстрые лошади не в первой пятерке» отрабатывается корректно. Лидер первой пятерки попадает автоматом в топ после 6-го забега. А далее в 7 забеге участвуют 2 другие лошади из первой пятерки. Они в этом забеге соревнуются с лидерами второй и третей пятерки + второй лошади второй пятерки. Если они выигрывают (приходят первой и второй) 7 забег, то они и попадают в топ.
Все варианты решения тут уверяют ю что мы можем сказать лошадь 3 из забега 1 точно хуже лошади 1 из забега 2 или 3, потому что нет секундомера, поэтому мы не можем сравнивать лидеров независимы забегов, или я не прав?
Не можем, однозначно не можем, но мы можем их прогнать вместе в 7-м забеге и узнать точно нужные места. Заметьте, что мы оставляем 3 лошади из первой пятерки, 2 лошади из второй, и 1 лошадь из третьей. Всего 6 штук, но одна из них гарантированно лидер.
В 6-м забеге мы сравнили лидеров пятёрок. Пятерки (или оставшиеся тройки), лидеры которых пришли 4-й и 5-й вприницпе не могут рассчитывать на призовые места, так как лидеры этих пятерок уже проиграли 3-м другим лидерам, а внутри тех пятерок ситуация ещё хуже.
Итого остается при беглом рассмотрении всего 9 лошадок (по 3 лошади из 3-х пятёрок). При более подробном рассмотрении, оказывается, что лошадь, которая пришла в прошлый раз первой — лучшая среди всех. И её можно исключать сразу, а далее нужно просто понять кто займет 2 и 3 место. Из оставшихся 8-ми лошадок можно выкинуть ещё 3. Остается как раз 5 для выявления серебра и бронзы.
В последней задачи деление второго массива на части ничего не дает по сравнению с последовательным проходов, вам все равно в худшем случае надо будет проверить все элементы. Вероятность досрочного нахождения элементы такая же. Кроме того, вы меняете данные в массивах (портите их), а не факт что это разрешено. Для правильной работы вам придется сделать копии массивов, а это ДОПОЛНИТЕЛЬНАЯ ПАМЯТЬ.
Задача с конями решается быстрее.
Из условий задачи ясно, что 1-я строка будет полностью входить в результирующую строку.
Давайте уточним, что обработка слов ABCE и ACDE должна на выходе дать единственно возможный вариант ABCDE. Во всяком случае я понимаю условие задачи именно так.
Задача с массивами: там можно обойтись без произведения, просто посчитать сумму чисел в массиве, и сумму КВАДРАТОВ чисел в массиве. Это также приводит к квадратичному уравнения. Но избавляет от необходимости отдельной проверки на нули. По сути — это обработка в 1 проход, с использованием всего 2-х переменных. Короче решения я представить не могу.
Задача с подмножествами. Здесь очевидно, нужно работать с укороченными строками, выбросив те буквы из первого слова, которые не входят во второе, и буквы из второго слова, которых нет в первом. Остатки от 2-х слов уже пытаемся перебором «перемешать» в строку минимальной длины. А уже потом (и это тривиально) добавить выкинутые буквы. В худшем варианте (когда буквы нельзя выкинуть) сложность остается той же, но зато существенно сокращает сложность, когда у обоих слов всего 1 буква общая.
На последний (7-й) забег неопределенность остается только у 5-ти лошадей. Из первой пятёрки лидер = 100% лучший среди всех, его в расчет не берем. Остается 2 и 3 место из первой пятёрки, 1 и 2 место из второй пятерки, и только первое место из 3-й пятёрки. И это ровно на 1 забег.
Ваше решение 1-задачи вызывает больше вопросов, чем дает ответы. Во-первых, поиск максимальной подпоследовательности — это не тривиальная задача. Даже найдя её, нужно ещё правильно расставить значения по бокам. В -третьих, что будет, если одна и та же максимальная подпоследовательность будет встречаться во втором слове несколько раз?
По описанному вами невозможно определить даже алгоритмическую сложность.
Ваше решение как минимум неполное, как максимум неверное. Неполнота не дают мне возможность построить контрпример.
1) Подобная задача у нас была ещё в школе, классе примерно 8-м. И даже тогда она легко решалась.
2) Первое решение — это разбить всех на 5-ки. Пустить 5 забегов (узнать места внутри пятерки). Выбираем 5 лидеров. Затем пока не наберем нужное количество поступаем так: устраиваем забег, выбираем первую лошадь, и на её место ставим следующую лошадь из её пятерки. Всего 8 забегов. Причем это общий подход, на любое количество лошадей.
А второе решение (7 забегов) пришло, когда а нарисовал на листке положение лошадей после 6-го забега и вычеркнул тех, кто не может претендовать на тройку.
3) Вот это уже сложная задача, решение приличное я не нашел. Она одна стоит больше всех остальных вместе взятых. Даже не утерпел и посмотрел решение Nick_mentat, но к нему у меня много вопросов.
4) Тут 2 варианта. Если разрешено использовать дополнительные ячейки, тогда нужно приводить путем умножение на 10^n к "одной весовой категории", сохранить для каждого числа получившиеся значение, которые уже и сравниваются. При этом, в случае равенства, нужно сравнивать исходные числа (чтобы упорядочить 10 и 100). Этот вариант более быстрый, за счет того, что операция приведение (а она не дешевая) выполняется 1 раз.
Второй вариант — это написание КОМПОРАТОРА, который принимает на вход 2 числа, и сравнивает их. А дальше можно вызывать стандартную функцию сортировки. Это не требует лишней памяти, но требует приведения чисел каждый раз при сравнении.
5) Самый простой способ — это вычислить сумму чисел обоих массивов и произведение чисел (на 0 не умножаем) обоих массивов. Тогда мы получим произведение и сумму искомых чисел. Эти 2 уравнения приводятся к полиному второй степени, и элементарно находятся. Но тут несколько моментов. Первоначально нужно посчитать количество нулей в обоих массивах, если оно разное, то находить произведение смысла нет. С суммой тоже вопросов нет, достаточно взять тип целого, который больше используемых чисел. Например если массивы заполнены 32-битными значениями, то использовать надо 64-битное. С умножением сложнее, умножение пару сотен чисел переполняет даже самые большие типы целого. Значит для умножения нужно использовать числа с плавающей точкой. Да, там будет потеря точности, но старшие биты должны вытянуть (обеспечить) правильное значение.
Насчет задачи 3). Лучшее, что я придумал — это полный перебор, когда первое слово перемешивается со вторым (с сохранением последовательности внутри), для каждого варианта ищем букву из первого слова, которая оказалась равна рядом стоящей букве из второго слова (т.е. эту букву можно выкинуть). Считаем количество таких букв, запоминаем комбинацию, когда их число максимально. Такой алгоритм дает гарантированный результат, но имеет очень плохую алгоритмическую сложность, что-то вроде O(n^m).
Уводите разговор не туда. Ваш рисунок в ОЧЕРЕДНОЙ РАЗ показывает, что по горизонтальным осям он равномерен (масса каждого слоя пропорционально площади), а вот по высоте нет. Замечу, что и на этой картинке разрезы сделаны ВЕРТИКАЛЬНО, что лишний раз должно заставить вас задуматься.
Вы не правы сразу во многих вещах. Любая задача — это абстракция, и решать задачу нужно внутри этой же абстракции. Те же яйца, бросаемые с небоскреба. Ведь яйцо может упасть с 10-го этажа на песок и не разбиться, а может и с 9-го на бетон и разбиться.
Во скажите, вы часто режете торты горизонтальным разрезом? Вот вы свой торт в новом году попробуйте так разрезать, боюсь вас не поймут. В «объективной реальности» торты режут именно вертикальными разрезами, и я вам даже намекну, что это не просто так.
И ни кубики (кубик 3хмерная фигура) магги, ни гуманитарность, ни ваши «Ха-ха» здесь совершенно не причем.
Даже если есть опыт решения, то не всегда понятно что делать? Не всегда догадываешься, что вообще яйца можно бросать с этажей (и какие действия вообще можно делать). Мне кажется, что правильней показать человеку вариант полного перебора, и попросить его оптимизировать решение.
В случае, если правильный этаж попадает в первую половину (первое яйцо сразу разбивается), то вторым яйцом придется проходить аж половину пути. Т.е. при полном значении 100 этажей, 49 этаж будет найден за 50! попыток. Это не то что не оптимальное, это одно из худших решений. Хуже только полный перебор.
Какой блин бинарный поиск? При дихотомическом делении у вас на любом шаге может быть либо больше, либо меньше, либо равно. А в данной задаче у вас «меньше» ДОЛЖНО выпадать не больше 2-х раз, причем второй раз на последней попытке.
Вас не смущает, что по вашему алгоритму этаж 63 будет найден за 7+30=37 попыток? «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
Извините, что цепляюсь, но… В задаче сказано про прямоугольный торт, и прямоугольный вырез. Именно прямоугольник, а не параллелепипед. Поэтому задача исключительно двухмерная. Если торт распределен неравномерно по ширине-длине, то задача впринципе некорректна. Поэтому такое равномерное распределение обязано быть. А вот насчет гарантии равномерного распределения по высоте нет ну никак, тем более, что в обычных тортах это распределение более чем неравномерное.
Всё, дошло. Вместо того, чтобы проверять массив на нули каждый раз, мы можем вести счетчик нулевых (или не нулевых) элементов, фиксируя каждое изменение массива.
Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
1) Первым делом находим общие буквы в обоих словах. Как это сделать (через хэш, массив или полным поиском) — не принципиально. Общие буквы у них — ACD.
2) Для обоих слов создаем урезанные варианты (оставляем только общие буквы), и при этом запоминаем соответствие. Получаются слова ACAD и ADDCA, и соответствие [3,4,6,7] и [2,5,7,8,10].
3) Создаем массив размером произведения длин сокращенных слов, в нашем случае 4 * 5.
Выбираем слово ACAD проходим по нему с конца (начиная с буквы D). Для каждой такой буквы из первого слова проходим по второму в обратном порядке, и ищем совпадающие буквы. Когда буквы совпали, делаем проход по первому слову в правильном порядке, начиная с буквы справа от текущей (слева от D в нашем примере ничего нет, поэтому ничего не делаем) и смотрим что стоит в массиве для этой буквы и её положения. Находим максимальное значение, прибавляем к нем 1 и сохраняем в массиве в текущем положении и для всех леволежащих, пока не найдем число большее. И того у нас получается тройной цикл (по первому слову-по второму слову-по первому слову).
В чем смысл массива — значение в ячейке x,y говорит нам о максимальной подпоследовательности которая бы начиналась с x-места первом слове, y-места второго слова.
Чтобы было понятно приведу результаты обработки ACAD и ADDCA.
A [3 1 1 1 1]
C [2 2 2 2 0]
A [2 2 1 1 1]
D [1 1 1 0 0]
максимальное значение — 3. Теперь мы имеем в наличии длину искомой последовательности, и букву (положение) в первом слове, с которой она начинается.
4) Используя всё это и массив находим узлы (положение букв в обоих словах) за 1 проход.
В нашем случае A(1,1) C(2,4) A(3,5).
5) Возвращаемся к исходным словам, переводим по таблице соответствия наши узлы.
OPACKADOS и MABUDYDCMAB => A(3,2) C(4,8) A(6,10). После чего разбиваем наши слова на участки (между узлов, узлы не входят ). Берем первый участок первого слова, прибавляем первый участов второго слова и прибавляем сам узел, и так далее…
OP — M — A…
Вычислительная сложность что-то типа между O(n*n+m*n) в случае, если каждая буква встречается не чаще 1 раза и O(n*n*m) в случае, если все буквы одинаковы. Т.е. сложность между квадратичной и кубической.
Ура товарищи!!!
Не можем, однозначно не можем, но мы можем их прогнать вместе в 7-м забеге и узнать точно нужные места. Заметьте, что мы оставляем 3 лошади из первой пятерки, 2 лошади из второй, и 1 лошадь из третьей. Всего 6 штук, но одна из них гарантированно лидер.
Итого остается при беглом рассмотрении всего 9 лошадок (по 3 лошади из 3-х пятёрок). При более подробном рассмотрении, оказывается, что лошадь, которая пришла в прошлый раз первой — лучшая среди всех. И её можно исключать сразу, а далее нужно просто понять кто займет 2 и 3 место. Из оставшихся 8-ми лошадок можно выкинуть ещё 3. Остается как раз 5 для выявления серебра и бронзы.
Задача с конями решается быстрее.
Давайте уточним, что обработка слов ABCE и ACDE должна на выходе дать единственно возможный вариант ABCDE. Во всяком случае я понимаю условие задачи именно так.
Задача с подмножествами. Здесь очевидно, нужно работать с укороченными строками, выбросив те буквы из первого слова, которые не входят во второе, и буквы из второго слова, которых нет в первом. Остатки от 2-х слов уже пытаемся перебором «перемешать» в строку минимальной длины. А уже потом (и это тривиально) добавить выкинутые буквы. В худшем варианте (когда буквы нельзя выкинуть) сложность остается той же, но зато существенно сокращает сложность, когда у обоих слов всего 1 буква общая.
Ваше решение 1-задачи вызывает больше вопросов, чем дает ответы. Во-первых, поиск максимальной подпоследовательности — это не тривиальная задача. Даже найдя её, нужно ещё правильно расставить значения по бокам. В -третьих, что будет, если одна и та же максимальная подпоследовательность будет встречаться во втором слове несколько раз?
По описанному вами невозможно определить даже алгоритмическую сложность.
Ваше решение как минимум неполное, как максимум неверное. Неполнота не дают мне возможность построить контрпример.
Мои решения.
1) Подобная задача у нас была ещё в школе, классе примерно 8-м. И даже тогда она легко решалась.
2) Первое решение — это разбить всех на 5-ки. Пустить 5 забегов (узнать места внутри пятерки). Выбираем 5 лидеров. Затем пока не наберем нужное количество поступаем так: устраиваем забег, выбираем первую лошадь, и на её место ставим следующую лошадь из её пятерки. Всего 8 забегов. Причем это общий подход, на любое количество лошадей.
А второе решение (7 забегов) пришло, когда а нарисовал на листке положение лошадей после 6-го забега и вычеркнул тех, кто не может претендовать на тройку.
3) Вот это уже сложная задача, решение приличное я не нашел. Она одна стоит больше всех остальных вместе взятых. Даже не утерпел и посмотрел решение Nick_mentat, но к нему у меня много вопросов.
4) Тут 2 варианта. Если разрешено использовать дополнительные ячейки, тогда нужно приводить путем умножение на 10^n к "одной весовой категории", сохранить для каждого числа получившиеся значение, которые уже и сравниваются. При этом, в случае равенства, нужно сравнивать исходные числа (чтобы упорядочить 10 и 100). Этот вариант более быстрый, за счет того, что операция приведение (а она не дешевая) выполняется 1 раз.
Второй вариант — это написание КОМПОРАТОРА, который принимает на вход 2 числа, и сравнивает их. А дальше можно вызывать стандартную функцию сортировки. Это не требует лишней памяти, но требует приведения чисел каждый раз при сравнении.
5) Самый простой способ — это вычислить сумму чисел обоих массивов и произведение чисел (на 0 не умножаем) обоих массивов. Тогда мы получим произведение и сумму искомых чисел. Эти 2 уравнения приводятся к полиному второй степени, и элементарно находятся. Но тут несколько моментов. Первоначально нужно посчитать количество нулей в обоих массивах, если оно разное, то находить произведение смысла нет. С суммой тоже вопросов нет, достаточно взять тип целого, который больше используемых чисел. Например если массивы заполнены 32-битными значениями, то использовать надо 64-битное. С умножением сложнее, умножение пару сотен чисел переполняет даже самые большие типы целого. Значит для умножения нужно использовать числа с плавающей точкой. Да, там будет потеря точности, но старшие биты должны вытянуть (обеспечить) правильное значение.
Насчет задачи 3). Лучшее, что я придумал — это полный перебор, когда первое слово перемешивается со вторым (с сохранением последовательности внутри), для каждого варианта ищем букву из первого слова, которая оказалась равна рядом стоящей букве из второго слова (т.е. эту букву можно выкинуть). Считаем количество таких букв, запоминаем комбинацию, когда их число максимально. Такой алгоритм дает гарантированный результат, но имеет очень плохую алгоритмическую сложность, что-то вроде O(n^m).
Во скажите, вы часто режете торты горизонтальным разрезом? Вот вы свой торт в новом году попробуйте так разрезать, боюсь вас не поймут. В «объективной реальности» торты режут именно вертикальными разрезами, и я вам даже намекну, что это не просто так.
И ни кубики (кубик 3хмерная фигура) магги, ни гуманитарность, ни ваши «Ха-ха» здесь совершенно не причем.
Это мой вариант. Он имеет сложность O(m). Код конечно можно причесать, выделить повторяющиеся участки…
Задача с анаграммами. Вы уверены, что ваш алгоритм работает правильно?
Мне кажется, что он не сможет найти слово АБАБВ в слове ААБАБВГД.
«За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.