Комментарии 78
В 3й задаче некорректный перевод — там только один массив. Кроме того, как я понимаю, нужно найти неразрывный подмассив, а не подмножество, как указано в заголовке.
Вопрос 1. — Прямоугольный торт
Прямоугольный кусок отрезали от края торта (как нормальные люди), или в произвольном месте(как я)?
Прямоугольный кусок отрезали от края торта (как нормальные люди), или в произвольном месте(как я)?
Честно говоря, ожидал больше от задач.
1 вопрос — задача о бутерброде. Численно решить легко. В общем виде тоже знакомая (там 2 прямоугольника было и надо было через центры проводить).
2 вопрос — классика. Понятно что 2 яйцо кидаем по 1 этажу вверх. Ответы и дальше не пишу (под спойлер загнать не могу).
1 задача — скользящее окно. Сложность O(n+m) дополнительная память O(n)
2 задача — ориентированный граф, кратчайший путь и всё просто.
3 задача — шаблонная задача в 1 проход по массиву.
1 вопрос — задача о бутерброде. Численно решить легко. В общем виде тоже знакомая (там 2 прямоугольника было и надо было через центры проводить).
2 вопрос — классика. Понятно что 2 яйцо кидаем по 1 этажу вверх. Ответы и дальше не пишу (под спойлер загнать не могу).
1 задача — скользящее окно. Сложность O(n+m) дополнительная память O(n)
2 задача — ориентированный граф, кратчайший путь и всё просто.
3 задача — шаблонная задача в 1 проход по массиву.
Можете подавать резюме в Google :)
1 вопрос — в комментарии выше предложили усложнение.
2 вопрос — перебором с первого этажа? А первое яйцо тогда зачем?
Задачи — я думаю, интервьюеры будут смотреть на лаконичность/оригинальность решения в том числе.
1 вопрос — в комментарии выше предложили усложнение.
2 вопрос — перебором с первого этажа? А первое яйцо тогда зачем?
Задачи — я думаю, интервьюеры будут смотреть на лаконичность/оригинальность решения в том числе.
Могу сказать, что вторая задача далеко не так проста как кажется. Цель задачи — «За какое минимальное количество попыток Вы сможете это определить?». Как я понял ваш алгоритм, вы предлагаете бросать яйцо через этаж, то есть кинули яйцо на n'ом этаже, и если оно не разбилось, идете на n + 2 этаж. А если разбилось, спускаетесь на n-1 этаж, и проверяете, если не разбилось, то последний этаж n, если разбилось, то n-2. Если максимальный этаж, с которого яйцо не разобьется это 100, то вам потребуется 51 попыток. Вы через один этаж поднимаетесь до 100 этажа — это 50 попыток, плюс вернетесь на этаж ниже и сбросите яйцо, на 99 этаже, что бы убедиться, что максимальный этаж это не 90. Итого 51 попытка. То есть ответ на вопрос этой задачи, используя ваш алгоритм это — 51. Но на самом деле есть другой алгоритм, который позволяет за максимум 14 ходов узнать на каком этаже разобьется яйцо)
Речь, конечно же, о втором вопросе, а не о второй задаче.
Само упоминание цифры 14 — уже спойлер. Найти оптимальную стратегию не так сложно, и я думаю, что уважаемый ptyrss её знает. Потому как второе яйцо действительно кидается по одному этажу, не смотря на то, что стратегия первого сложнее. А вот доказать оптимальность и придти именно к 14, имхо, сложнее. Мне давали эту задачку, правда не в гугле, и к оптимуму пришлось придти перебором, хотя конечно же можно проще.
НЛО прилетело и опубликовало эту надпись здесь
Ответы
Вопрос 1 — разрезать надо по толщине, поскольку «одинаковые» здесь не означает «по площади»
Вопрос 2 — недавно пробегала, вроде 14. Нужно кидать первое яйцо так, чтобы если оно разбивается в этом броске, оставшихся бросков хватит, чтобы проверить все этажи подряд между текущим и этажом, с которого бросали яйцо предыдущий раз (и оно не разбилось).
Задача 1 — нужно использовать скользящее окно (подстроку) в строке 2 длиной в строку 1, и считать количество конкретных символов в ней. Как совпадет с количествами для строки 1, возвращаем true, иначе false.
Задача 2 — вроде как обычный поиск на графе, только граф надо собрать правильно. Т.е. вершины будут пары станция-автобус, станция-null будут выходы, дальше орграф строим из любой (х, а) в (у, а) дистанция 0, если а не ноль, из (х, а) в (х,0) дистанция 1, из (х,0) в (х, а) дистанция 0, если а не ноль. Дальше ищем кратчайший путь от (х,0) в (у,0). Вообще эта задача на оптимизацию, и вот это решение довольно тупое — просит О(m*n) памяти, может, можно и покороче.
Задача 3 — эту у нас на олимпиаде в 1996м решали, по программированию, кстати. Я тогда был дуб, но решение запомнил — считаем скользящую сумму, пока больше нуля, и отслеживаем максимум, как меньше нуля стала, обнуляем и переносим начало. Решение получается в один проход по массиву чисел.
Вопрос 2 — недавно пробегала, вроде 14. Нужно кидать первое яйцо так, чтобы если оно разбивается в этом броске, оставшихся бросков хватит, чтобы проверить все этажи подряд между текущим и этажом, с которого бросали яйцо предыдущий раз (и оно не разбилось).
Задача 1 — нужно использовать скользящее окно (подстроку) в строке 2 длиной в строку 1, и считать количество конкретных символов в ней. Как совпадет с количествами для строки 1, возвращаем true, иначе false.
Задача 2 — вроде как обычный поиск на графе, только граф надо собрать правильно. Т.е. вершины будут пары станция-автобус, станция-null будут выходы, дальше орграф строим из любой (х, а) в (у, а) дистанция 0, если а не ноль, из (х, а) в (х,0) дистанция 1, из (х,0) в (х, а) дистанция 0, если а не ноль. Дальше ищем кратчайший путь от (х,0) в (у,0). Вообще эта задача на оптимизацию, и вот это решение довольно тупое — просит О(m*n) памяти, может, можно и покороче.
Задача 3 — эту у нас на олимпиаде в 1996м решали, по программированию, кстати. Я тогда был дуб, но решение запомнил — считаем скользящую сумму, пока больше нуля, и отслеживаем максимум, как меньше нуля стала, обнуляем и переносим начало. Решение получается в один проход по массиву чисел.
В торте ничего считать не нужно.
Нужно резать горизонтально пополам…
Нужно резать горизонтально пополам…
Ага, а если торт внизу тестовые коржи, а сверху крем? Тогда что? Одному корешки, а другому горшки?
А если сверху пряничный домик с куполами и лебеди?
А если на торте вишенки стоят, их тоже поровну делить, причем их было 20, а в вырезанный прямоугольник попало три? Нет в задаче — нет в «а если».
Извините, что цепляюсь, но… В задаче сказано про прямоугольный торт, и прямоугольный вырез. Именно прямоугольник, а не параллелепипед. Поэтому задача исключительно двухмерная. Если торт распределен неравномерно по ширине-длине, то задача впринципе некорректна. Поэтому такое равномерное распределение обязано быть. А вот насчет гарантии равномерного распределения по высоте нет ну никак, тем более, что в обычных тортах это распределение более чем неравномерное.
Вы специалист по обычным тортам?
Я вот люблю обычный торт-Наполеон.
… и как раз НЕ обычные торты — неоднородны.
Я вот люблю обычный торт-Наполеон.
… и как раз НЕ обычные торты — неоднородны.
Торт на фото как раз неоднородный — верхний слой толще, чем любые внутренние слои того же цвета.
Если вы еще не поняли — в природе не существует однородных тортов.
Задачка в принципе поставлена некорректно для нестандартного мышления.
Задачка в принципе поставлена некорректно для нестандартного мышления.
Уверены, что некорректно? В задаче сказано «торт прямоугольный», то есть, двумерный.
Вы видели когда нибудь нечто подобное — двумерный торт?
Если объект двумерный — то есть абстракция — то его неприемлемо обзывать трехмерным объектом, каким есть торт…
Даже у листа бумаги есть толщина. А тем более у торта.
Только извращенцы думают об двумерной абстракции и обзывают ее тортом…
Задачка о двумерном торте, который всегда трехмерный — однозначно не для логического, а для творческого мышления.
Если объект двумерный — то есть абстракция — то его неприемлемо обзывать трехмерным объектом, каким есть торт…
Даже у листа бумаги есть толщина. А тем более у торта.
Только извращенцы думают об двумерной абстракции и обзывают ее тортом…
Задачка о двумерном торте, который всегда трехмерный — однозначно не для логического, а для творческого мышления.
В задаче русским по белому сказано, что торт прямоугольный, то есть, двумерный.
А-ха-ха…
Вам гуманитариям объясняли слово синоним, нет в вашем гуманитарном училище?
Тем более не объясняли термин «проекция объемного тела».
Прямоугольный уж точно не синоним двумерный… :)
Вот интересно — реальный торт — он какой в трехмерном случае?
Параллелепипедный?
А кубики магги — они ведь не кубики тоже, хотя в двумерной проекции прямоугольники.
Вам гуманитариям объясняли слово синоним, нет в вашем гуманитарном училище?
Тем более не объясняли термин «проекция объемного тела».
Прямоугольный уж точно не синоним двумерный… :)
Вот интересно — реальный торт — он какой в трехмерном случае?
Параллелепипедный?
А кубики магги — они ведь не кубики тоже, хотя в двумерной проекции прямоугольники.
А-ха-ха.
Мы, технари, знаем, что если написано конкретное слово, то синонимы искать незачем. Прямоугольник — двумерная фигура. Из фразы «Прямоугольный торт» однозначно следует двумерность торта.
Мы, технари, знаем, что если написано конкретное слово, то синонимы искать незачем. Прямоугольник — двумерная фигура. Из фразы «Прямоугольный торт» однозначно следует двумерность торта.
Двумерный — это абстракция, а торт — это объективная реальность.
Желаю вам в Новом Году отрезать и скушать двумерный торт…
На здоровье… :)
Но будьте осторожны — питаясь абстрактными вещами можно умереть с голоду. :)
Желаю вам в Новом Году отрезать и скушать двумерный торт…
На здоровье… :)
Но будьте осторожны — питаясь абстрактными вещами можно умереть с голоду. :)
Конечно, абстракция. Уже данная нам в условии задачи. А еще в условии задачи, например, слова по-русски написаны, что позволяет предположить, что ответ по-китайски не примут.
Странно, что приходится это кому-то объяснять.
Странно, что приходится это кому-то объяснять.
Вы не правы сразу во многих вещах. Любая задача — это абстракция, и решать задачу нужно внутри этой же абстракции. Те же яйца, бросаемые с небоскреба. Ведь яйцо может упасть с 10-го этажа на песок и не разбиться, а может и с 9-го на бетон и разбиться.
Во скажите, вы часто режете торты горизонтальным разрезом? Вот вы свой торт в новом году попробуйте так разрезать, боюсь вас не поймут. В «объективной реальности» торты режут именно вертикальными разрезами, и я вам даже намекну, что это не просто так.
И ни кубики (кубик 3хмерная фигура) магги, ни гуманитарность, ни ваши «Ха-ха» здесь совершенно не причем.
Во скажите, вы часто режете торты горизонтальным разрезом? Вот вы свой торт в новом году попробуйте так разрезать, боюсь вас не поймут. В «объективной реальности» торты режут именно вертикальными разрезами, и я вам даже намекну, что это не просто так.
И ни кубики (кубик 3хмерная фигура) магги, ни гуманитарность, ни ваши «Ха-ха» здесь совершенно не причем.
Вот смотри — тебе абстрактный 21-слойный торт…
Каждый из супертонких слоев все равно обладает ТОЛЩИНОЙ.
Попробуй порежь ТОЛЬКО верхний слой дабы решить задачу.
Боюсь только теоретически это ты и сможешь.
… а вот практически — нет.
Странно мне другое — люди подобной задачей вроде желают найти творческих умных людей…
… а на самом деле находят решателей абстрактных задач ради абстрактной цели. :)
Каждый из супертонких слоев все равно обладает ТОЛЩИНОЙ.
Попробуй порежь ТОЛЬКО верхний слой дабы решить задачу.
Боюсь только теоретически это ты и сможешь.
… а вот практически — нет.
Странно мне другое — люди подобной задачей вроде желают найти творческих умных людей…
… а на самом деле находят решателей абстрактных задач ради абстрактной цели. :)
Уводите разговор не туда. Ваш рисунок в ОЧЕРЕДНОЙ РАЗ показывает, что по горизонтальным осям он равномерен (масса каждого слоя пропорционально площади), а вот по высоте нет. Замечу, что и на этой картинке разрезы сделаны ВЕРТИКАЛЬНО, что лишний раз должно заставить вас задуматься.
kardan2, novrm,alexeykuzmin0, товарищи, двумерный ли торт или объёмный — можно выяснить на конкретном собеседовании, задав уточняющий вопрос интервьюеру.
Решение с центрами прямоугольников / центрами масс является верным, но предложение резать горизонтально довольно любопытное, мне как-то в голову не пришло :)
С наступающим :)
Решение с центрами прямоугольников / центрами масс является верным, но предложение резать горизонтально довольно любопытное, мне как-то в голову не пришло :)
С наступающим :)
Разговор как раз туда.
Замените словосочетание «прямоугольный торт» на «прямоугольная рыба» или «прямоугольный компот»…
Что изменится?
В вашем смысле — ничего — ибо для вас прямоугольный — значит двумерный, будь то торт, рыба или компот…
Я же утверждаю — слово ТОРТ в этой задаче или совсем НЕ УМЕСТНО или привнесено специально для полета творческой мысли.
Замените словосочетание «прямоугольный торт» на «прямоугольная рыба» или «прямоугольный компот»…
Что изменится?
В вашем смысле — ничего — ибо для вас прямоугольный — значит двумерный, будь то торт, рыба или компот…
Я же утверждаю — слово ТОРТ в этой задаче или совсем НЕ УМЕСТНО или привнесено специально для полета творческой мысли.
Вы уж извините, но либо я не понял первый вопрос, либо он тривиальнее.
Зачем какие-то там находить линии и прочее: просто поставьте торт ребром и разрежьте его пополам. Вот и всё:) По-другому объясняя: сделайте разрез в горизонтальной плоскости торта. Не имеет значение что там и как вырезали — куски будут одинаковы.
Как решить второй вопрос «правильно» я не знаю, но знаю, что яйца разбиваются, если их просто так уронить, с рук, не надо высчитывать этажи))
Зачем какие-то там находить линии и прочее: просто поставьте торт ребром и разрежьте его пополам. Вот и всё:) По-другому объясняя: сделайте разрез в горизонтальной плоскости торта. Не имеет значение что там и как вырезали — куски будут одинаковы.
Как решить второй вопрос «правильно» я не знаю, но знаю, что яйца разбиваются, если их просто так уронить, с рук, не надо высчитывать этажи))
Ваши задачи решаются за три минуты.
1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.
Задачи:
1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.
1) Есть изначальный прямоугольник, и есть вырезанный прямоугольник. Разрез нужно провести через центры обоих. Причем положение вырезанного куска не важно, если он полностью содержится в первоначальном прямоугольнике.
2) Задача с яйцами стандартна. В общем случае нужно разбить весь диапазон этажей N на карманы (M), так чтобы М*М=N. Если яиц у нас три, тогда M*M*M=N. В нашем случае N=100, значит M=10. Первым делом проверяем 10 этаж, если яйцо не разбилось, тогда 20, если не разбилось, тогда 30… Т.е. первое яйцо тратим на выявление правильного десятка. А уже вторым яйцом узнаем конкретный этаж внутри этого десятка. Итого за 20 бросков мы гарантировано узнаем нужный этаж. Но этот алгоритм можно оптимизировать, если разбить этажи так, чтобы в первый карман попало больше этажей, чем в последний. Например так: 15-14-13-12-11-9-8-7-6-5. Тогда мы гарантировано узнаем нужный этаж за 16 бросков.
Задачи:
1) Переводим символы в числа. Т.е. А-1, B-2, C-3…
Создаем массив длинной равный количеству букв в алфавите. Записываем в него по индексу букв из первого слова количества раз, которое оно там встречается. Если букв нет, ставим 0. За первый проход по второму слову метим позиции, которые содержат буквы, которых нет в нашем первом слове(в первом примере это буква О). Этим бы быстро исключили заведомо неправильные проверки. По оставшимся позициям делаем так: предварительно создаем ещё один массив такой же длины(1 раз). Обнуляем его. И считаем сколько раз каждая буква попалась. Сверяем его с эталонным массивом (по имеющимся буквам). Если получили совпадение, то оно и есть искомый результат. Сложность O(n*m), где n-длина первого слова, m- длина второго слова. Зачему, что если требуется применить поиск несколько раз к разным словам и разным эталонам, то выделенные массивы нужно всего ли обнулять, т.е. сэкономить на процессе выделении памяти.
2) Я здесь вижу немного измененный волновой алгоритм поиска пути в лабиринте. Создаем массив с длиной равной количеству остановок. Забиваем их все очень большим числом. Начальную ячейку (стартовую остановку) делаем равной нулю. Теперь в цикле проигрываем каждый из автобусов. Автобус стартует с первой остановки, запоминая число в ней (K). Если на следующей остановке хранимое число больше, чем K +1, то ложим в него значение k+1.
Если же это число меньше чем K, то заменяем запомненное число вместо K. И так до бесконечности, тока ячейка массива финальной остановки не станет равной какому-то числу меньшему изначального. Значение этого числа и будет равно количеству автобусов. Для надежности (может быть найден не самый оптимальный путь), надо прогнать цикл ещё количество раз, которое равно количеству автобусов.
Хотя только счас дошло, что это не гарантирует оптимальности в случае, когда приходится пересаживаться между одними и теме же автобусами. Но можно обрабатывать только те ячейки, число в которых не больше чем номер цикла (итерации). Мне кажется, что находить оптимальный алгоритм есть смысл зная количество остановок, количество автобусов, среднее число остановок и разряженность остановок (сколько автобусов проходит через одну остановку). Алгоритмы, которые работают хорошо на плотных массивах могут работать не оптимально на разряженных.
Также надо ставить флаг, что за каждый цикл было изменена хоть 1 ячейка. Если флаг не сработал, то задача не имеет решения.
3) За один проход. Достаточно знать максимальную сумму массива, которых заканчивался предыдущей (при проходе) ячейкой. Если она больше 0, то плюсуем её со значением текущей ячейки массива, иначе оставляем только текущее значение. Решение очевидно.
Вопрос 2. Можно за меньшее число бросаний.
Задача 1. Можно сделать за O(n + m).
Задача 2. У вас сложность O(n * m), а можно сделать за O(n + m).
Ключевая идея
Обозначим dp(i, j) ответ на вопрос «какое минимальное количество бросаний требуется для здания высотой i этажей и j яиц?» Очевидно, что dp(i, 1) == i (если яйцо одно, нет выбора, кроме как кидать с каждого этажа). Точно так же dp(0, i) == 0 (если этажей нет, то яйцо не бьется ни с какого этажа).
А дальше переход: dp(i, j) = 1 + min_k{max[dp(k-1, j-1), dp(i-k, j)]}. Почему именно так? Ну, во-первых, нам нужно будет кинуть яйцо 1 раз. Мы будем кидать его с этажа k, и это k выберем таким образом, чтобы максимальное число бросаний, которые нам оставались бы в будущем, было бы минимальным. А сколько бросаний нам останется сделать в будущем? Если яйцо разбилось при падении с этажа k, то у нас осталось для проверки k-1 этаж и j-1 яйцо. А если нет, то, соответственно, i-k этажей и j яиц. Ну и, поскольку нам может не повезти, берем максимум.
Вся задача заключается в подсчете dp(100, 2).
А дальше переход: dp(i, j) = 1 + min_k{max[dp(k-1, j-1), dp(i-k, j)]}. Почему именно так? Ну, во-первых, нам нужно будет кинуть яйцо 1 раз. Мы будем кидать его с этажа k, и это k выберем таким образом, чтобы максимальное число бросаний, которые нам оставались бы в будущем, было бы минимальным. А сколько бросаний нам останется сделать в будущем? Если яйцо разбилось при падении с этажа k, то у нас осталось для проверки k-1 этаж и j-1 яйцо. А если нет, то, соответственно, i-k этажей и j яиц. Ну и, поскольку нам может не повезти, берем максимум.
Вся задача заключается в подсчете dp(100, 2).
Задача 1. Можно сделать за O(n + m).
Ключевая идея
Незачем проверять массив каждй раз честно. Вместо того, чтобы хранить в ячейке количество вхождений буквы в подстроку, лучше хранить разность между этим количеством и количеством вхождений в искомый паттерн. Тогда «нашлось» — это массив из всех нулей.
В отдельной переменной храним количество ненулевых элементов массива. При сдвиге подстроки у нас изменяется только 2 ячейки массива — изменяем их и обновляем эту переменную.
Ну или можно вообще не париться и хешами насчитать за ту же сложность. Правда, тогда будет вероятность коллизии.
В отдельной переменной храним количество ненулевых элементов массива. При сдвиге подстроки у нас изменяется только 2 ячейки массива — изменяем их и обновляем эту переменную.
Ну или можно вообще не париться и хешами насчитать за ту же сложность. Правда, тогда будет вероятность коллизии.
Задача 2. У вас сложность O(n * m), а можно сделать за O(n + m).
Ключевая идея
Использовать BFS0-1 вместо алгоритма Форда-Беллмана, описанного в вашем решении. Вершины графа — маршруты, ребра — пересечения маршрутов. Изначально инициализируем 0 все маршруты, которые включают в себя начальную остановку. Ответ — минимум из расстояний до всех маршрутов, включающих в себя конечную остановку.
Задача 1.
Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
И где здесь O(n + m)? Тут явная O(n * m).
И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.
Задача с яйцами ваше решение почти не убежало от моего.
Итак, нам нужно проверить вхождение слова «АБ» в слове из 10 букв. Для этого нам придется сделать цикл из (10-2) итераций, и в каждом проверить на нулевые значения 2 ячейки(потому что первое слово состоит из 2-х букв). Всего 8*2 действий. Теперь нужно найти скажем слово «АБВГ». Оно потребует (10-4) итерации, в каждой из которых нужно проверить 4 элемента массива. Всего действий 6*4=24.
Теперь ищем слово из 4-х букв в слове из 20 букв, т.е. увеличивает в 2 раза оба слова. В результате получаем (20-4)*4 = 64 проверки, а это увеличение в 4 раза, а не в 2!
И где здесь O(n + m)? Тут явная O(n * m).
И именно из-за этого я не стал дальше оптимизировать свой алгоритм, хотя приведение к нулю — просто само бросается в глаза.
Задача с яйцами ваше решение почти не убежало от моего.
Всё, дошло. Вместо того, чтобы проверять массив на нули каждый раз, мы можем вести счетчик нулевых (или не нулевых) элементов, фиксируя каждое изменение массива.
Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
Итого, нам нужно сделать n операций для первоначального заполнения отрицательными значениями первого слова, затем посчитать n первых букв во втором слове (первое положение окна), а дальше сделать (m-n-1) сдвигов окна убирая из массива старую букву и прибавляя новую букву. Итого n+n+2*(m-n-1)=2m-2 действий. Но тогда почему O(m+n), а не O(m)? По моим выкладкам получается, что от длины первого слова ничего не зависит.
Насчет задачи с автобусами. По всей видимости я не правильно понял условия: если автобус двигается abcd, то он идет из a в b, из b в c, из с в d, а после d он уже никуда не идет. Т.е. его движение однонаправлено. Т.е. он может из a приехать в d, но не может из d приехать в a. Наверное меня сбил с толку пример, где все движение показано в одном направлении. И в таком случае это совсем иная задача.
БАЯН! задачу 2 еще в институте разбирали в рамках темы «АЦП половинного деления-последовательного приближения».
Решение в лоб — последовательное приближение, но тут надо использовать комбинированный метод.
Сначала нужно идти половинным приближением (1,2,4,8,16,32,64, бац!), когда первое яйцо разобьется, откатить на предыдущий цикл и продолжить последовательным приближением (33,34,35...)
итого при разбитии яйца на N этаже
методом последовательного приближения = N попыток
методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))
Вопрос в задаче, как и в большинстве подобных задач, поставлен некорректно. Отвечая формально на вопрос «За какое минимальное количество попыток Вы сможете это определить?» можно смело отвечать «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Решение в лоб — последовательное приближение, но тут надо использовать комбинированный метод.
Сначала нужно идти половинным приближением (1,2,4,8,16,32,64, бац!), когда первое яйцо разобьется, откатить на предыдущий цикл и продолжить последовательным приближением (33,34,35...)
итого при разбитии яйца на N этаже
методом последовательного приближения = N попыток
методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))
Вопрос в задаче, как и в большинстве подобных задач, поставлен некорректно. Отвечая формально на вопрос «За какое минимальное количество попыток Вы сможете это определить?» можно смело отвечать «За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
методом половинного последовательного приближения = floor(log2(N))+(N-2^(floor(log2(N))))При N=100 по этой формуле получается 42 попытки, при оптимальном решении в 14.
Вас не смущает, что по вашему алгоритму этаж 63 будет найден за 7+30=37 попыток?
«За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
«За одну попытку! Кинули со первого этажа оно и разбилось.» Может это трудности перевода?
Имеется ввиду за какое минимальное количество попыток вы найдете гарантированно ответ. Т.е. рассматривается наихудший вариант при известном количестве этажей. Рациональней оставлять большие промежутки как раз в начале (нижние этаже), а вот на верхних наоборот уплотнять.
В случае же бесконечного количества этаже, мне кажется что надо делать шаг не 2^n, а n^2.
Вопрос #2 — баян, решается либо с помощью динамического программирования, либо аналитически. Разбиралась на типичном программисте, а так же в видео уроках Игоря Клейнера (уроки по динамическому программированию и интеревью для программистов).
С яйцами решить «бинарным поиском» не лучший вариант?
Можно сделать лучше.
И последний, это алгоритм кадана или что-то есть лучше?
Какой блин бинарный поиск? При дихотомическом делении у вас на любом шаге может быть либо больше, либо меньше, либо равно. А в данной задаче у вас «меньше» ДОЛЖНО выпадать не больше 2-х раз, причем второй раз на последней попытке.
Скорее всего автор имел в виду имея 1 яйцо максимально приблизить к промежутку этажей (т.е. бросаем с этажа N/2, если разбилось, то искомый этаж находится в промежутке от 1 до N/2-1, если нет — то в промежутке от N/2+1 до N, далее рекурсивно), в котором имеется такой, начиная с которого яйца начинают разбиваться. Дальше имея оставшееся яйцо найти сам этаж последовательным перебором. Это неоптимальное решение, но одно из первых наивных, которые обычно приходят в голову.
В случае, если правильный этаж попадает в первую половину (первое яйцо сразу разбивается), то вторым яйцом придется проходить аж половину пути. Т.е. при полном значении 100 этажей, 49 этаж будет найден за 50! попыток. Это не то что не оптимальное, это одно из худших решений. Хуже только полный перебор.
Предлагал самый настоящий бинарный, с делением каждый раз на 2 :)
Просто невнимательно прочитал условия задачи и пропустил самое главное — что яиц всего два.
Тут получается первое яйцо кидаем каждые 10 этажей, как разбилось то второе кидаем через этаж с последнего «целого» десятка.
Медленнее бинарного поиска, но целее будут яйца.
Просто невнимательно прочитал условия задачи и пропустил самое главное — что яиц всего два.
Тут получается первое яйцо кидаем каждые 10 этажей, как разбилось то второе кидаем через этаж с последнего «целого» десятка.
Медленнее бинарного поиска, но целее будут яйца.
Задача #3 — одна из классических задач на динамическое программирование. Есть куча способов как ее решить. Например алгоритм Кадана (Kadane's algorithm) или с помощью техники «разделяй и властвуй». На образовательном канале Игоря Клейнера имеется несколько разделов, посвященных динамическому программированию. Там подробно разбирается эта задача, а так же задача про 2 яйца (правда там были даны 2 сферы).
2reci
Задача с анаграммами. Вы уверены, что ваш алгоритм работает правильно?
Мне кажется, что он не сможет найти слово АБАБВ в слове ААБАБВГД.
Задача с анаграммами. Вы уверены, что ваш алгоритм работает правильно?
Мне кажется, что он не сможет найти слово АБАБВ в слове ААБАБВГД.
public static final int ALPHABETSIZE= 256;
public static boolean findSubstrAnagram(String subword, String word){
if(subword.length()>word.length()){
return false;
}
int[] array = new int[ALPHABETSIZE];
int difference =0;
for(int i=0; i<subword.length(); i++){
char c = subword.charAt(i);
if(array[c]==0){
difference ++;
}
array[c]--;
}
for(int i=0; i<subword.length(); i++){
char c = word.charAt(i);
if(array[c]==0){
difference++;
}
if((++array[c])==0){
difference--;
}
}
if(difference==0){
return true;
}
for(int i=subword.length(); i<word.length(); i++){
char c = word.charAt(i);
if(array[c]==0){
difference++;
}
if((++array[c])==0){
difference--;
}
c = word.charAt(i-subword.length());
if(array[c]==0){
difference++;
}
if((--array[c])==0){
difference--;
}
if(difference==0){
return true;
}
}
return false;
}Это мой вариант. Он имеет сложность O(m). Код конечно можно причесать, выделить повторяющиеся участки…
В алгоритме Кадана тоже ошибка.
Где именно? Можете привести пример?
Он не работает если массив целиком состоит из отрицательных чисел, вместо минимального числа он вернет 0.
Если немного изменить код, то должно работать
Тут без проверки на пустой массив, но суть ясна :)
function getMaxSubSum(arr) {
var maxCurrent = maxGlobal = arr[0];
for (var i = 1; i < arr.length; i++) {
maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
maxGlobal = Math.max(maxGlobal, maxCurrent);
}
return maxGlobal;
}
Тут без проверки на пустой массив, но суть ясна :)
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний