2014 dxdy logo

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

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




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


20/12/10
8858
В ноябре прошлого года у нас в институте проходила олимпиада по программированию (ICPC NEERC 2019-2020, Восточно-Сибирский регион, Россия, 16 ноября 2019 г.). Одну из задач не смогла решить ни одна команда (Задача E. Опытный робототехник). Она в прилагаемом файле (я решил не портить ее оригинальное условие своим пересказом, и с разрешения модератора помещаю ее как есть). Мне эта задача показалось любопытной, и мы со студентами, причастными к олимпиаде, потратили немало времени на ее обсуждение. Надеюсь, сообществу dxdy она тоже приглянется. На мой взгляд, она скорее математическая и может оказаться хорошей учебной задачей для студентов. Но есть и очень интригующая алгоритмическая составляющая. (Разумеется, на мой неискушенный взгляд --- в олимпиадном программировании я дилетант.)

Те, кому эта тема интересна, могут начать с примеров. Скажем, дать точный ответ в примере 5.


Вложения:
icpc_esib_tasks_2019-5.pdf [184.63 Кб]
Скачиваний: 262
 Профиль  
                  
 
 Re: Опытный робототехник
Сообщение22.04.2020, 19:29 
Заслуженный участник
Аватара пользователя


01/09/13
4318
nnosipov в сообщении #1457104 писал(а):
На мой взгляд, она скорее математическая

Мне кажется, она просто математическая - надо найти мат.ожидание суммы расстояний по $X$ и $Y$.

-- 22.04.2020, 19:33 --

nnosipov в сообщении #1457104 писал(а):
Но есть и очень интригующая алгоритмическая составляющая.

Вроде бы алгоритм выглядит совсем простым...

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


27/08/16
9426
Geen в сообщении #1457127 писал(а):
Вроде бы алгоритм выглядит совсем простым...
Вероятность каждой пары координат в разности будет разной. Все пары координат перебирать нельзя.

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


20/12/10
8858
Geen в сообщении #1457127 писал(а):
Вроде бы алгоритм выглядит совсем простым...
А во время уложитесь? Какова сложность Вашего совсем простого алгоритма?

Да, и какой там ответ в примере 5?

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


01/09/13
4318
nnosipov в сообщении #1457129 писал(а):
Какова сложность Вашего совсем простого алгоритма?

Пока я вижу как самое сложное "сортировку" координат - то есть $n\ln n$.
Но я пока ещё туплю над математикой и не выписал формулу :mrgreen: (может быть в ней будет какая-то сложность)

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


20/12/10
8858
Geen в сообщении #1457131 писал(а):
Пока я вижу как самое сложное "сортировку" координат - то есть $n\ln n$.
Они уже отсортированы по условию.

А формулки --- да, пописать придется. Ну, мне так кажется :-)

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


01/09/13
4318
nnosipov в сообщении #1457134 писал(а):
Они уже отсортированы по условию.

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

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


07/08/14
4231
Не понятно - робот знает куда упали точки или ему их ещё предстоит найти.

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


20/12/10
8858
Geen
Я имел в виду вот это:
Цитата:
Вершины многоугольника заданы в порядке обхода против часовой стрелки.
Многоугольник выпуклый, кстати.

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


01/09/13
4318
upgrade в сообщении #1457138 писал(а):
или ему их ещё предстоит найти.

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

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


20/12/10
8858
upgrade
Почитайте внимательно условие задачи. Собственно, математическая часть задачи уже сформулирована.

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


01/09/13
4318
nnosipov в сообщении #1457139 писал(а):
Многоугольник выпуклый, кстати.

Это само собой, и сильно всё упрощает.
Вот для невыпуклого (а если ещё и не односвязанного) пришлось бы сначала искать кратчайший путь...

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


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

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


20/12/10
8858
Geen в сообщении #1457144 писал(а):
Вот для невыпуклого (а если ещё и не односвязанного) пришлось бы сначала искать кратчайший путь...
На первый взгляд, довольно безнадежная задача. Не, у нас все по-простому. Я же говорю, хорошая учебная задача.

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


01/09/13
4318
nnosipov в сообщении #1457147 писал(а):
На первый взгляд, довольно безнадежная задача.

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

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

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



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

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


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

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