Немного оффтоп, насчёт примера с бинарным поиском: лучше сделать "upper bound", а потом сравнить найденный элемент с искомым. В цикле не нужна проверка nums[mid] == target. В среднем элемент всё равно будет найден на предпоследней итерации, то есть по факту у вас в цикле просто на одну проверку больше.
Просто верните оффлайновые собесы! Вся нечисть, которая на собесах юзает чатГпт или его кожаный аналог, сразу отвалится. В благословенном 2019 году ездили в офис, и никто не жужжал.
У нас тут граф с N вершинами и O(N) ребрами, представленное решение работает за O(N), даже если его допилить под поиск пути. Более общие алгоритмы для кратчайшего пути смогут дать такую асимптотику?
Парадокс возникает из-за ведущего — он ведёт себя не случайно и использует знание о расположении приза
Львиная доля неправильных ответов - из-за того, что этот момент не проговаривается в условии. То есть обычно просто говорится, что ведущий открыл дверь без приза, а случайно или намеренно он это сделал - непонятно.
У "другого программиста" из статьи не возникло беспокойства по поводу O(N^2) и как следствие повода этот самый ресерч делать. Он запилил простой вариант за 10-15 минут и закрыл таск
У подхода есть и свои минусы. Например, если взять текущую реализацию ProductCardFacc, то при любом ререндере этого компонента создаются новые Image, Title и т.д., то есть все они будут перемонтированы, что мягко говоря не фонтан. Можно уменьшить проблему, если их создавать через useCallback, но даже отдельные перемонтирования при изменении пропса - тоже так себе, например, прощай анимация. Более классический React-way - в компоненте ProductCardFacc просто сложить значения в контексты (или в один контекст, если у вас например mobx), но тогда компоненты можно просто заимпортировать, а в children передавать не функцию, а сразу верстку, и паттерн разваливается на глазах..
Ну основная идея - выключить свет в вагоне, где находимся, потом пройти К вагонов, включая свет, потом отсчитать К вагонов обратно. Свет горит - обошли весь поезд. Если, например, делать такие забеги на 1, 2, 4, 8, ..., то есть удваивать К, то включим свет во всех вагонах за О(N). Потом выключаем свет в стартовом вагоне и идём считаем вагоны до выключенного.
Поезд ведь замкнут в кольцо (первый вагон с последним)? Это довольно известная задача, которую обычно решают за O(N^2) действий. Хотя есть способы и за O(N). N - количество вагонов
каждый из троих думает так: остальные двое сговорились, и сделают так, чтобы я получил как можно меньше, а профит поделят. Так вот - решение должно гарантировать, что даже если это так, то всё равно он получит треть
Согласен
потому что решение таково, что любой договор остальных двух о неравномерности деления даст третьему кусок бОльший, чем одна треть
Вовсе необязательно. Может оказаться, что участники сговора поделили криво, а третий игрок получил ровно 1/3. Главное, что они не могут сговориться так, чтобы ему досталось менее 1/3
у него НЕТ уверенности, что его доля не меньше, чем у кого-то другого
Ему нужна только уверенность, что его доля не меньше 1/3 от всего куска. Распределение оставшихся 2/3 его никак не волнует и никак от него не зависит, потому что сразу после дележки один из тех двоих может просто отдать свою долю другому
А толку? Здесь при любом сговоре оставшийся участник своими усилиями обеспечивает себе 1/3, и никому, кроме себя, потом не сможет предъявить претензии. Это и требуется от решения.
У вас, если второй отдаст первому более 1/3, или третьему покажется, что у первого более 1/3, то третий участник ничего с этим поделать не может и будет недоволен результатом
В вашем варианте возможен сговор между первым и вторым, когда первому достанется кусок более 1/3. Потом второй и третий поделят остаток поровну, а уже после первый и второй тайком поделят поровну свои части и будут иметь более 1/3 на нос.
А вот предложенный автором вариант не допускает сговора, и там без разницы, каким по счету быть.
нет никакой гарантии, что двое других и вправду поделят свои куски на абсолютно равные части
Главное, что эти части будут равные с их точки зрения, то есть никаких претензий они предъявить не смогут
Задача про камеру и лампочку здесь дана в самом базовом варианте. У нее есть разные усложнения. Например, игрокам неизвестно, в каком состоянии лампочка на старте. Тогда все, кроме счётчика, зажигают свет два раза, а счётчик говорит, что все побывали, когда досчитает до 197.
Немного оффтоп, насчёт примера с бинарным поиском: лучше сделать "upper bound", а потом сравнить найденный элемент с искомым. В цикле не нужна проверка
nums[mid] == target. В среднем элемент всё равно будет найден на предпоследней итерации, то есть по факту у вас в цикле просто на одну проверку больше.del
Пример со сварщиком - это же "лайвкодинг" в чистом виде)
у "бомбардиллы-крокодиллы" есть предшественник - https://pastvu.com/p/72944
ещё вспомнился фильм "Хроники мутантов"
Просто верните оффлайновые собесы! Вся нечисть, которая на собесах юзает чатГпт или его кожаный аналог, сразу отвалится. В благословенном 2019 году ездили в офис, и никто не жужжал.
п.1 омерзителен. По мне, так гораздо хуже, чем то, что ИИ устроил в фильмах про Терминатора
У нас тут граф с N вершинами и O(N) ребрами, представленное решение работает за O(N), даже если его допилить под поиск пути. Более общие алгоритмы для кратчайшего пути смогут дать такую асимптотику?
Это хрестоматийная задача, миллион раз обмусоленная и как пример ДП, и как "задача для собесов". Странно было бы, если бы гпт про неё не знал
Львиная доля неправильных ответов - из-за того, что этот момент не проговаривается в условии. То есть обычно просто говорится, что ведущий открыл дверь без приза, а случайно или намеренно он это сделал - непонятно.
У "другого программиста" из статьи не возникло беспокойства по поводу O(N^2) и как следствие повода этот самый ресерч делать. Он запилил простой вариант за 10-15 минут и закрыл таск
У подхода есть и свои минусы. Например, если взять текущую реализацию
ProductCardFacc, то при любом ререндере этого компонента создаются новые Image, Title и т.д., то есть все они будут перемонтированы, что мягко говоря не фонтан. Можно уменьшить проблему, если их создавать через useCallback, но даже отдельные перемонтирования при изменении пропса - тоже так себе, например, прощай анимация. Более классический React-way - в компонентеProductCardFaccпросто сложить значения в контексты (или в один контекст, если у вас например mobx), но тогда компоненты можно просто заимпортировать, а в children передавать не функцию, а сразу верстку, и паттерн разваливается на глазах..Ну основная идея - выключить свет в вагоне, где находимся, потом пройти К вагонов, включая свет, потом отсчитать К вагонов обратно. Свет горит - обошли весь поезд. Если, например, делать такие забеги на 1, 2, 4, 8, ..., то есть удваивать К, то включим свет во всех вагонах за О(N). Потом выключаем свет в стартовом вагоне и идём считаем вагоны до выключенного.
Поезд ведь замкнут в кольцо (первый вагон с последним)? Это довольно известная задача, которую обычно решают за O(N^2) действий. Хотя есть способы и за O(N). N - количество вагонов
Согласен
Вовсе необязательно. Может оказаться, что участники сговора поделили криво, а третий игрок получил ровно 1/3. Главное, что они не могут сговориться так, чтобы ему досталось менее 1/3
Ему нужна только уверенность, что его доля не меньше 1/3 от всего куска. Распределение оставшихся 2/3 его никак не волнует и никак от него не зависит, потому что сразу после дележки один из тех двоих может просто отдать свою долю другому
А толку? Здесь при любом сговоре оставшийся участник своими усилиями обеспечивает себе 1/3, и никому, кроме себя, потом не сможет предъявить претензии. Это и требуется от решения.
У вас, если второй отдаст первому более 1/3, или третьему покажется, что у первого более 1/3, то третий участник ничего с этим поделать не может и будет недоволен результатом
В вашем варианте возможен сговор между первым и вторым, когда первому достанется кусок более 1/3. Потом второй и третий поделят остаток поровну, а уже после первый и второй тайком поделят поровну свои части и будут иметь более 1/3 на нос.
А вот предложенный автором вариант не допускает сговора, и там без разницы, каким по счету быть.
Главное, что эти части будут равные с их точки зрения, то есть никаких претензий они предъявить не смогут
Задача про камеру и лампочку здесь дана в самом базовом варианте. У нее есть разные усложнения. Например, игрокам неизвестно, в каком состоянии лампочка на старте. Тогда все, кроме счётчика, зажигают свет два раза, а счётчик говорит, что все побывали, когда досчитает до 197.
Редукс существовал задолго до Рюрика, просто ещё не был открыт