O-нотация - это всего лишь оценка функции сверху. Если среднее время работы avg_time = f(n) = const, то формально avg_time = O(1). Где здесь манипуляция?
В таком случае хеш-таблицы вам тоже должны не нравиться: там время вставки O(1) — это именно среднее время, а не оценка в худшем случае.
Рандом вообще не причем тут, они ведь уже перемешаны по условию
Где такое можно прочитать?)
Наоборот, если мы говорим про олимпиадное программирование, где все тесты запускаются независимо, то опытные составители обязательно подсунут вам тесты, на которых без рандома все будет работать медленно.
Мы точно решаем или неточно.
Мне кажется, вы путаете два разных понятия: приближенные и рандомизированные алгоритмы. Первые - выдают ответ с определенной погрешностью. Вторые - просто используют внутри себя рандом (как например quick sort).
Если массив на вход подается случайный, то метод random ничего нового не привносит. Разумеется, он только замедлит. Однако, на плохих входах будет деградация до O(N).
Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.
Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии.
Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.
Создать список синих клеток (все свободные клетки лабиринта)
Цикл - пока список синих клеток не пуст
Рассчитать путь для синей клетки до выхода
Записать в результирующий список команд
Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.
Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.
Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку, а значит состояние не изменилось, а значит она не перешла в другую клетку, а значит количество вариантов нового расположения осталось неизменным.
Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Объясните другими словами, так как исходя из первого абзаца мы не можем исключить вероятность того, что множества вернулись в исходное состояние, а значит ничего никуда не перешло.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
А здесь я уже запутался. В первом абзаце вы пишете о теоретической возможности не попасть на выход, а в этом абзаце вы уже подразумеваете что строите гарантирующий выход маршрут.
Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.
И что конкретно значат синие и белые клетки? Как именно вы их определяете?
Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.
Белая клетка - это клетка, где гарантированно нет черепахи.
Зеленая клетка - клетка "выход".
По какому принципу вы их уменьшаете на 1 и какой критерий их выбора?
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Это утверждение ложно, не на каждой итерации черепашка будет попадать на клетку "выход". Чем меньше у вас будет черепашек, тем больше будут интервалы между выходами.
Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.
Не понятен смысл этого утверждения, для нас абсолютно не важно что где-то освободится клетка, мы же не в неё идём.
Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.
Тут вас спасло "хотя бы", так как в теории вы можете взять одну единственную черепаху и пока ведёте её к выходу у вас просто весь лабиринт опустеет
Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)
O-нотация - это всего лишь оценка функции сверху. Если среднее время работы avg_time = f(n) = const, то формально avg_time = O(1). Где здесь манипуляция?
В таком случае хеш-таблицы вам тоже должны не нравиться: там время вставки O(1) — это именно среднее время, а не оценка в худшем случае.
Спасибо за комментарий и ссылки на теоремы!
Где такое можно прочитать?)
Наоборот, если мы говорим про олимпиадное программирование, где все тесты запускаются независимо, то опытные составители обязательно подсунут вам тесты, на которых без рандома все будет работать медленно.
Мне кажется, вы путаете два разных понятия: приближенные и рандомизированные алгоритмы. Первые - выдают ответ с определенной погрешностью. Вторые - просто используют внутри себя рандом (как например quick sort).
Шикарное решение, спасибо!
Да, именно так :)
Решение авторов именно такое.
O(1) по памяти, а не по времени.
Если массив на вход подается случайный, то метод
randomничего нового не привносит. Разумеется, он только замедлит. Однако, на плохих входах будет деградация до O(N).Если массив был случайно перемешан, да. Однако, если нам назло подсунули плохой массив, будет O(n), например:
Решение за O(1) по памяти без рандома здесь: https://youtu.be/B-1h5xEjBvk?si=RVxUnYKOJnnx-wZK&t=791
Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии.
Спасибо!
Вполне корректный алгоритм.
А код на питоне вас устроит? :)
Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.
Создать список синих клеток (все свободные клетки лабиринта)
Цикл - пока список синих клеток не пуст
Рассчитать путь для синей клетки до выхода
Записать в результирующий список команд
Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
Вернуться в п.2
Так если задача не причем, почему пишите об этом здесь?
Оптимизация чего? Я как автор статьи не совсем понимаю, о чем вы :)
Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.
Затем, что вы не знаете, где черепаха. Все синие клетки для вас норм.
Кто кого троллит)
Одна итерация - это не одна команда, а последовательность команд, переводящая одну из синих клеток в зеленую.
То, что выбрав любую точку можно дойти до выхода доказывать как раз не нужно, т.к. это следует из словосочетания "связный лабиринт" :)
Этого может не произойти, если черепаха сидит не в выбранной вами клетке. Она может сидеть в любой синей, мы же не знаем в какой из них :)
Одна клетка обязательно перейдет в зеленую. Остальные - как повезет. Если ваша черепаха в той выбранной синей, то она точно выйдет.
Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.
Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.
Белая клетка - это клетка, где гарантированно нет черепахи.
Зеленая клетка - клетка "выход".
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Отличное наблюдение, все верно! :)
Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.
Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.
Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)