Опытный робототехник

[nnosipov]

Geen в сообщении #1457152 писал(а):

Ну не сильно (если односвязанный).

Мне кажется, итоговая формула там сильно испортится. Но я не готов это обсуждать детально.

Так, у нас за полночь, должен свалить на боковую.

[EtCetera]

Если я правильно понимаю, решение заключается в "нарезании" многоугольника на трапециевидные (в общем случае) "ломтики", как если бы это был батон.

[upgrade]

(Оффтоп)

Geen в сообщении #1457140 писал(а):

Не представляю как можно найти точку.

Если робот ходит шагами - по узлам сетки и точка может выпадает в узлы сетки

[Geen]

upgrade в сообщении #1457164 писал(а):

точка может выпадает в узлы сетки

Так про это в условии не сказано...

-- 22.04.2020, 21:15 --

nnosipov в сообщении #1457153 писал(а):

Мне кажется, итоговая формула там сильно испортится.

Кажется, всё равно нужно делать триангуляцию...

[realeugene]

Geen в сообщении #1457165 писал(а):

Так про это в условии не сказано...

Так не интересно.

[Geen]

realeugene в сообщении #1457176 писал(а):

Geen в сообщении #1457165 писал(а):

Так про это в условии не сказано...

Так не интересно.

А иначе возможны случаи, когда точки "не связаны"....

[realeugene]

Geen в сообщении #1457180 писал(а):

А иначе возможны случаи, когда точки "не связаны"....

Верно.

-- 22.04.2020, 21:37 --

Понятно, что задача решаема за линейное по числу вершин границы время.

[nnosipov]

kotenok gav в сообщении #1457146 писал(а):

Один алгоритм виден сразу (просто перебираем точки), но он жутко неоптимален, в худшем случае пар точек около $16\times10^36$.

Вчера не успел отреагировать: к сожалению, автор задачи зачем-то написал про линии сетки (а не просто про два направления), в результате чего создается впечатление, что робот может двигаться только по линиям сетки, из одного узла в другой узел. Но это не так, задача не дискретная, а непрерывная. Просто указаны два направления движения.

По-моему, дискретный вариант задачи был бы сложнее (потому что находить суммы и их асимптотику сложнее, чем интегралы).

-- Чт апр 23, 2020 11:54:28 --

EtCetera в сообщении #1457154 писал(а):

Если я правильно понимаю, решение заключается в "нарезании" многоугольника на трапециевидные (в общем случае) "ломтики", как если бы это был батон.

По крайней мере, мое понимание ровно такое же Увы, авторское решение недоступно, так что сравнить не с чем. У меня были подозрения, что есть какой-то "левый" способ, который менее затратен (какая-нибудь хитрая формула Грина, позволяющая бесплатно все свести к одномерным интегралам). А так да, дальше остается честный счет с единственным нюансом --- уложиться по времени.

[dmd]

nnosipov в сообщении #1457303 писал(а):

к сожалению, автор задачи зачем-то написал про линии сетки (а не просто про два направления), в результате чего создается впечатление, что робот может двигаться только по линиям сетки, из одного узла в другой узел. Но это не так, задача не дискретная, а непрерывная. Просто указаны два направления движения.

Но фраза "Робот на этом поле в каждый момент времени может перемещаться только в одном из четырёх направлений, параллельных линиям сетки." говорит за дискретность задачи.

И в графе "Вывод" таблицы, это точные уже посчитанные значения, которые нужно верифицировать в своей матмодели?

[nnosipov]

dmd в сообщении #1457306 писал(а):

И в графе "Вывод" таблицы, это точные уже посчитанные значения, которые нужно верифицировать в своей матмодели?

Да. Просто считайте, что речь идет о непрерывной модели, и в этой модели приведенные ответы правильны. Первый пример осиливают даже первокурсники, если им подсказывать (кратных интегралов они еще не изучают).

В общем, формулировка задачи не идеальна. (Если, конечно, автор не имел цели намеренно запутать решающих.)

[realeugene]

nnosipov в сообщении #1457303 писал(а):

У меня были подозрения, что есть какой-то "левый" способ, который менее затратен (какая-нибудь хитрая формула Грина, позволяющая бесплатно все свести к одномерным интегралам).

Интегралы, конечно, четырехкратные, но распадаются до однократных по прямоугольникам и треугольникам. И после осознания, как два соседних криволинейных ломтика объединять в один криволинейный ломтик, всё вроде бы становится тривиально. Единственное, для сохранения точности, возможно, нужно объединять ломтики уравновешенным деревом. Или нет.

-- 23.04.2020, 11:23 --

nnosipov в сообщении #1457303 писал(а):

По-моему, дискретный вариант задачи был бы сложнее (потому что находить суммы и их асимптотику сложнее, чем интегралы).

Сумма с дном от линейной функции внутри, конечно, сложнее для аналитического решения, чем бездонный интеграл.

[slavav]

nnosipov, вы правы. Первый пример даёт правильный ответ для непрерывной постановки задачи. Для дискретной постановки ответ отличается.

Ещё одна вещь: можно независимо интегрировать расстояния по вертикали и по горизонтали. В ответ попадает их сумма. Разделение переменных может упростить формулы.

[realeugene]

Добавлю, что криволинейные ломтики нужно объединять друг с другом, конечно же, за $O(1)$

[nnosipov]

slavav в сообщении #1457335 писал(а):

Ещё одна вещь: можно независимо интегрировать расстояния по вертикали и по горизонтали. В ответ попадает их сумма. Разделение переменных может упростить формулы.

Да, все так. Поскольку мне хотелось объяснить решение этой задачи студентам, формулы я написал довольно подробно, но, правда, до программирования доводить не стал (как-то все громоздко получается). Важно, что из этих формул вытекала приемлемая оценка сложности. Пример 5 мы со студентами подробно разобрали, все сошлось (ну и в более простых примерах 1-4 тоже). Поначалу был соблазн угадать правильный ответ, но уже постфактум мы поняли, что это безнадежно --- длина периода дроби оказалась трехзначной.

Не представляю, как все это могла бы проделать даже команда решающих в режиме реальной олимпиады. Но это, наверное, специфика олимпиад по программированию: должна быть очень сложная задача среди основной массы средних/легких.

[realeugene]

nnosipov в сообщении #1457356 писал(а):

как-то все громоздко получается

Ну в результате всё получается совсем несложно. Четыре простых рекуррентных выражения и четыре инициализации рекурсии для простой трапеции. Видимо, эта задача на то, чтобы "подумать" перед тем, как "трясти". Ну и небольшой вспомогательный код вроде разбиения выпуклой фигуры с кусочно-линейной границей на трапеции и переворачивания осей.

-- 23.04.2020, 14:28 --

$$I(l,r)=\int_l^r dx_1 \int_{b(x_1)}^{t(x_1)} dy_1 \int_l^r dx_2 \int_{b(x_2)}^{t(x_2)} dy_2 \left|x_2-x_1\right| =$$

$$=\left(\int_l^m + \int_m^r\right)dx_1 \int_{b(x_1)}^{t(x_1)} dy_1 \left(\int_l^m + \int_m^r\right) dx_2 \int_{b(x_2)}^{t(x_2)} dy_2 \left|\left(x_2-m\right)+\left(m-x_1\right)\right|$$

для $l\le m\le r$.
Остаётся только раскрыть скобки и вынести всё не зависящее от каждой переменной интегрирования из-под соответствующего интеграла.