2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Опытный робототехник
Сообщение22.04.2020, 20:36 
Заслуженный участник


20/12/10
7882
Geen в сообщении #1457152 писал(а):
Ну не сильно (если односвязанный).
Мне кажется, итоговая формула там сильно испортится. Но я не готов это обсуждать детально.

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 20:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 21:05 


07/08/14
02/06/21
3864

(Оффтоп)

Geen в сообщении #1457140 писал(а):
Не представляю как можно найти точку.

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 21:08 
Заслуженный участник
Аватара пользователя


01/09/13
3013
upgrade в сообщении #1457164 писал(а):
точка может выпадает в узлы сетки

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

-- 22.04.2020, 21:15 --

nnosipov в сообщении #1457153 писал(а):
Мне кажется, итоговая формула там сильно испортится.

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 21:23 


27/08/16
7895
Geen в сообщении #1457165 писал(а):
Так про это в условии не сказано...
Так не интересно.

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 21:26 
Заслуженный участник
Аватара пользователя


01/09/13
3013
realeugene в сообщении #1457176 писал(а):
Geen в сообщении #1457165 писал(а):
Так про это в условии не сказано...
Так не интересно.

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 21:28 


27/08/16
7895
Geen в сообщении #1457180 писал(а):
А иначе возможны случаи, когда точки "не связаны"....
Верно.

-- 22.04.2020, 21:37 --

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 07:42 
Заслуженный участник


20/12/10
7882
kotenok gav в сообщении #1457146 писал(а):
Один алгоритм виден сразу (просто перебираем точки), но он жутко неоптимален, в худшем случае пар точек около $16\times10^36$.
Вчера не успел отреагировать: к сожалению, автор задачи зачем-то написал про линии сетки (а не просто про два направления), в результате чего создается впечатление, что робот может двигаться только по линиям сетки, из одного узла в другой узел. Но это не так, задача не дискретная, а непрерывная. Просто указаны два направления движения.

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

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

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 08:21 


16/08/05
1105
nnosipov в сообщении #1457303 писал(а):
к сожалению, автор задачи зачем-то написал про линии сетки (а не просто про два направления), в результате чего создается впечатление, что робот может двигаться только по линиям сетки, из одного узла в другой узел. Но это не так, задача не дискретная, а непрерывная. Просто указаны два направления движения.

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

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 08:34 
Заслуженный участник


20/12/10
7882
dmd в сообщении #1457306 писал(а):
И в графе "Вывод" таблицы, это точные уже посчитанные значения, которые нужно верифицировать в своей матмодели?
Да. Просто считайте, что речь идет о непрерывной модели, и в этой модели приведенные ответы правильны. Первый пример осиливают даже первокурсники, если им подсказывать (кратных интегралов они еще не изучают).

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 11:15 


27/08/16
7895
nnosipov в сообщении #1457303 писал(а):
У меня были подозрения, что есть какой-то "левый" способ, который менее затратен (какая-нибудь хитрая формула Грина, позволяющая бесплатно все свести к одномерным интегралам).
Интегралы, конечно, четырехкратные, но распадаются до однократных по прямоугольникам и треугольникам. И после осознания, как два соседних криволинейных ломтика объединять в один криволинейный ломтик, всё вроде бы становится тривиально. Единственное, для сохранения точности, возможно, нужно объединять ломтики уравновешенным деревом. Или нет.

-- 23.04.2020, 11:23 --

nnosipov в сообщении #1457303 писал(а):
По-моему, дискретный вариант задачи был бы сложнее (потому что находить суммы и их асимптотику сложнее, чем интегралы).
Сумма с дном от линейной функции внутри, конечно, сложнее для аналитического решения, чем бездонный интеграл.

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 12:06 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 12:44 


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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 13:28 
Заслуженный участник


20/12/10
7882
slavav в сообщении #1457335 писал(а):
Ещё одна вещь: можно независимо интегрировать расстояния по вертикали и по горизонтали. В ответ попадает их сумма. Разделение переменных может упростить формулы.
Да, все так. Поскольку мне хотелось объяснить решение этой задачи студентам, формулы я написал довольно подробно, но, правда, до программирования доводить не стал (как-то все громоздко получается). Важно, что из этих формул вытекала приемлемая оценка сложности. Пример 5 мы со студентами подробно разобрали, все сошлось (ну и в более простых примерах 1-4 тоже). Поначалу был соблазн угадать правильный ответ, но уже постфактум мы поняли, что это безнадежно --- длина периода дроби оказалась трехзначной.

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

 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение23.04.2020, 14:09 


27/08/16
7895
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$.
Остаётся только раскрыть скобки и вынести всё не зависящее от каждой переменной интегрирования из-под соответствующего интеграла.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group