У нас тут граф с 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.
В последних примерах as необязательный, в этом случае лучше указывать дефолтное значение для T (например, если по умолчанию используется "button", то должно быть T extends ElementType = "button"), чтобы TS мог определять пропы при незаполненном as
Насчет конфликта пропов: можно упороться и сделать проверялку для as. Например, если мы просто не передаем все "свои" пропы в переданный компонент (а только используем сами), то нельзя передать в as такой компонент, у которого хотя бы один из этих пропов обязательный. Примерно так: https://tsplay.dev/N94q1w Соответственно, при добавлении "общих" пропов, например className, их тоже надо будет исключить из проверки
Примеры 2 и 3 - это "mapping type", а не дистрибуция (во втором ещё и лишняя проверка T[K], есть же ограничение на T)
Кстати, в mapping type есть механизм, аналогичный дистрибуции, если итерируемся по ключам "локального типа" в генерике: https://tsplay.dev/mprVMw - здесь мэппинг по отдельности обработал все элементы объединения, причем кортеж сохранил форму, а примитивы не поменялись.
Как отмечает Диков, перед решением задания студенты много времени тратят на перевод условий задачи. Это тормозит процесс обучения. В ПГУ перевели десятки заданий и выпустили два сборника, чтобы учащиеся могли сосредоточиться на самом задании, а не на переводе.
Я может чего не понимаю, но вроде бы можно было ограничиться переводом заданий. Зачем они полезли со словарем в синтаксис?
У нас тут граф с 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.
Редукс существовал задолго до Рюрика, просто ещё не был открыт
Ну, скорее всего, запретят. И заочно арестуют всех участников.
В последних примерах
asнеобязательный, в этом случае лучше указывать дефолтное значение для T (например, если по умолчанию используется "button", то должно бытьT extends ElementType = "button"), чтобы TS мог определять пропы при незаполненномasНасчет конфликта пропов: можно упороться и сделать проверялку для
as. Например, если мы просто не передаем все "свои" пропы в переданный компонент (а только используем сами), то нельзя передать вasтакой компонент, у которого хотя бы один из этих пропов обязательный. Примерно так: https://tsplay.dev/N94q1w Соответственно, при добавлении "общих" пропов, например className, их тоже надо будет исключить из проверкиПоследние более-менее честные выборы в РФ были в декабре 95 года, так что скоро уже 30 лет
Оно ещё и "движение", наверняка направлено на подрыв существующего строя
Примеры 2 и 3 - это "mapping type", а не дистрибуция (во втором ещё и лишняя проверка T[K], есть же ограничение на T)
Кстати, в mapping type есть механизм, аналогичный дистрибуции, если итерируемся по ключам "локального типа" в генерике: https://tsplay.dev/mprVMw - здесь мэппинг по отдельности обработал все элементы объединения, причем кортеж сохранил форму, а примитивы не поменялись.
Я может чего не понимаю, но вроде бы можно было ограничиться переводом заданий. Зачем они полезли со словарем в синтаксис?
То, что найдено как "typescript", добавляется автоматом к js?