Я лишь вижу описание способа уменьшения числа итераций за счёт исключения клеток, откуда маршрут уже был построен
См. рис. 3.
На нем показано, что освободившаяся (белая) клетка не обязательно та, из которой маршрут был построен. Но одна клетка гарантированно станет белой, т.к. число стрелочек ведущих из левого кружочка в правый n*m - 2 (т.к. минимум одну стрелочку мы потратили на зеленый кружок).
Если вы придумали последовательность команд, которая будет освобождать n*m-1 черепах, занимающих все поле, то та же последовательность будет работать и для любой отдельной из черепах.
В интерпретации, где вы управляете сразу n*m-1 черепахами у вас после каждой итерации будет исчезать (выходить из лабиринта) как минимум одна черепаха. Рано или поздно черепахи закончатся.
Этот первый шаг сомнений не вызывает. Если мы выполнили программу "X" верную для клетки А1, но не вышли из лабиринта - то мы теперь точно не находимся в А1.
Это утверждение не верно. Представьте лабиринт , выход в крайней правой клетке. После выполнения right мы освободим черепаху из центра, но черепаха с крайней левой клетки перейдет в центр. Поэтому следующая команда будет снова right.
Как только черепаха наступит на клетку "выход", она обретет свободу, независимо от следующих команд. Поскольку структура лабиринта известна заранее, можно вычислить все маршруты и для каждой клетки S найти клетку T = route(S), в которую он ведет. Обратная связь от черепахи нигде не используется.
Можете представить, что у вас во всех синих клетках одновременно сидят черепахи и вы хотите выпустить их всех. Тогда изначально у вас n*m-1 черепах. После первой итерации как минимум одна черепаха выйдет как только встанет на клетку "выход", количество черепах в лабиринте гарантированно уменьшится.
Огромное спасибо за интересную статью о переезде Yandex Tracker в облако. Рассказ о бесшовном переезде объемных баз данных впечатляет и представляет ценную информацию для тех, кто также стоит перед подобной задачей.
Очень интересно следить за развитием Yandex Tracker, спасибо за статью! ?
На самом деле, особенностью конкретно этой задачи является геометрическая часть. Конкретно условия, что отрезки не пересекаются и никакие три точки не лежат на одной прямой. Данные условия сложно формализовать и описать в терминах SQL, поэтому я думаю, что это просто похожая задача.
См. рис. 3.
На нем показано, что освободившаяся (белая) клетка не обязательно та, из которой маршрут был построен. Но одна клетка гарантированно станет белой, т.к. число стрелочек ведущих из левого кружочка в правый n*m - 2 (т.к. минимум одну стрелочку мы потратили на зеленый кружок).
Если вы придумали последовательность команд, которая будет освобождать n*m-1 черепах, занимающих все поле, то та же последовательность будет работать и для любой отдельной из черепах.
Предполагается честно выполнить набор команд
от каждой синей клетки 
и "вручную" собрать множество новых синих клеток 
У нас уменьшается количество клеток, где может располагаться черепаха, а не сам лабиринт.
Верно, но мы нигде это не используем
В интерпретации, где вы управляете сразу n*m-1 черепахами у вас после каждой итерации будет исчезать (выходить из лабиринта) как минимум одна черепаха. Рано или поздно черепахи закончатся.
Это утверждение не верно. Представьте лабиринт
, выход в крайней правой клетке. После выполнения right мы освободим черепаху из центра, но черепаха с крайней левой клетки перейдет в центр. Поэтому следующая команда будет снова right.
Как только черепаха наступит на клетку "выход", она обретет свободу, независимо от следующих команд. Поскольку структура лабиринта известна заранее, можно вычислить все маршруты и для каждой клетки S найти клетку T = route(S), в которую он ведет. Обратная связь от черепахи нигде не используется.
Можете представить, что у вас во всех синих клетках одновременно сидят черепахи и вы хотите выпустить их всех. Тогда изначально у вас n*m-1 черепах. После первой итерации как минимум одна черепаха выйдет как только встанет на клетку "выход", количество черепах в лабиринте гарантированно уменьшится.
Привет!
Огромное спасибо за интересную статью о переезде Yandex Tracker в облако. Рассказ о бесшовном переезде объемных баз данных впечатляет и представляет ценную информацию для тех, кто также стоит перед подобной задачей.
Очень интересно следить за развитием Yandex Tracker, спасибо за статью! ?
На самом деле, особенностью конкретно этой задачи является геометрическая часть. Конкретно условия, что отрезки не пересекаются и никакие три точки не лежат на одной прямой. Данные условия сложно формализовать и описать в терминах SQL, поэтому я думаю, что это просто похожая задача.
Для меня пересечение отрезков - это пересечение множеств их точек. Оно даже обозначается через тот же символ пересечения:
:)
Еще раз: не увольняют тех кто уехал.
Вы путаете. В яндексе такого нет.