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

[nnosipov]

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

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

[Geen]

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

На мой взгляд, она скорее математическая

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

-- 22.04.2020, 19:33 --

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

Но есть и очень интригующая алгоритмическая составляющая.

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

[realeugene]

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

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

Вероятность каждой пары координат в разности будет разной. Все пары координат перебирать нельзя.

[nnosipov]

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

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

А во время уложитесь? Какова сложность Вашего совсем простого алгоритма?

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

[Geen]

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

Какова сложность Вашего совсем простого алгоритма?

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

[nnosipov]

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

Пока я вижу как самое сложное "сортировку" координат - то есть $n\ln n$.

Они уже отсортированы по условию.

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

[Geen]

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

Они уже отсортированы по условию.

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

[upgrade]

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

[nnosipov]

Geen
Я имел в виду вот это:

Цитата:

Вершины многоугольника заданы в порядке обхода против часовой стрелки.

Многоугольник выпуклый, кстати.

[Geen]

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

или ему их ещё предстоит найти.

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

[nnosipov]

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

[Geen]

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

Многоугольник выпуклый, кстати.

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

[kotenok gav]

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

[nnosipov]

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

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

На первый взгляд, довольно безнадежная задача. Не, у нас все по-простому. Я же говорю, хорошая учебная задача.

[Geen]

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

На первый взгляд, довольно безнадежная задача.

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