Al Zimmermann - Polygonal Areas

[dimkadimon]

Стартовал новый долго жданный конкурс Ал Зиммерманн. На этот раз задача геометрическая и как всегда интересная. Надо найти некоторые полигоны с наибольшей и наименьшей площадью. Полигон состоит из $n$ точек, а его точки живут на $n \times n$ плоскости. Полигон должен иметь 3 условия:

* Все точки имеют разные координаты по вертикали и по горизонтали.
* Все стороны полигона имеют разные наклоны.
* Стороны полигона не могут пересекаться.

Всем удачи! Вот сайт конкурса: http://azspcs.com/Contest/PolygonalAreas

[dmd]

Пока сложнее всего было алгоритмизировать условие непересечения отрезков.

[dimkadimon]

Да это было непросто. Для проверки наклонов у меня неплохой $O(n\log(n))$ метод. Для больших $n$ трудно вообще найти легальное решение...

[Yadryara]

dimkadimon в сообщении #1175827 писал(а):

* Все точки имеют разные координаты по вертикали и по горизонтали.

ПМСМ, неудачный перевод пункта "No two vertices are from the same row or from the same column of the grid."

* Никакие две вершины не лежат в одной и той же строке(столбце) сетки.

[dimkadimon]

Такая интересная задача, а все куда то пропали!

Сегодня узнал одну интересную вещь. Оказывается Ал показывает самую лучшую разницу одного участника в Best Raw Scores. Но при подсчете очков используется Best Conjectural Score - самая лучшая разница учитывая все минимальные и максимальные полигоны. Эти разницы могут быть различны. Можно получить Best Raw Score, но не получить Best Conjectural Score. Именно такая ситуация у меня была для N=17. Я улучшил Best Raw Score от 207.5 до 208, но ни у кого не упали баллы. Теперь я понял в чем дело - я улучшил Best Raw Score, но не улучшил Best Conjectural Score.

Кстати мне кажется минимальная задача сложнее максимальной. В максимальной я вижу узоры которые можно подготовить и применить, а вот в минимальной я такого не наблюдал. Что вы думаете?

[Vovka17]

Странное решение Ала указывать Best Raw Score вместо Best Conjectural Score. Это вообще не имеет никакой пользы.
Понимаю, что ему хотелось сохранить интригу и не показывать минимальные и максимальные значения площадей для каждого задания, но, ведь и Best Conjectural Score никоим образом нам не подскажет нам. Просто разница между самой максимальной площадью и самой минимальной, из всего, что вводили все участники - та разница, которая даст 1,0.
Как по мне, так даже точное знание минимальной и максимальной площадей никак не помогает найти эти полигоны. Но это решение организаторов, какую инфу показывать. Может позже по конкурсу и откроют это для всех. Уже бывало так.

Цитата:

Что вы думаете?

Я думаю, что задача очень-очень сложная. Пока принципиальной разницы в построенных полигонах максимальной и минимальной площади не вижу. Впрочем, пока я мало что смог построить.

[gris]

Я не участник, я только попробовать
Правильно ли я понял, что на одном значении $n$ можно заработать максимально один балл? Правильно ли нарисовал картинку? Правильно ли я думаю, что уже для каждого $n$ получены правильные полигоны, судя по скорам у верхних участников?

(поправил картинку с учётом замечаний)

[Yadryara]

gris в сообщении #1177248 писал(а):

Правильно ли я понял, что на одном значении $n$ можно заработать максимально один балл?

Да. И я его заработал

gris в сообщении #1177248 писал(а):

Правильно ли нарисовал картинку?

Если не считать того, что минимально возможная площадь $1.5$, а не $4$, то правильно.

gris в сообщении #1177248 писал(а):

Правильно ли я думаю, что уже для каждого $n$ получены правильные полигоны, судя по скорам у верхних участников?

Правильные-то получены для каждого $n$, но не факт, что минимально и максимально возможные площади достигнуты для всех $n$.

[dimkadimon]

gris в сообщении #1177248 писал(а):

Правильно ли я понял, что на одном значении $n$ можно заработать максимально один балл? Правильно ли нарисовал картинку? Правильно ли я думаю, что уже для каждого $n$ получены правильные полигоны, судя по скорам у верхних участников?

Вроде все правильно, только последняя точка в максимальном полигоне (3,5), а не (3,1). Должен добавить что нелегальные полигоны при вводе просто дают ошибку и не зачитываются.

-- 15.12.2016, 23:21 --

Vovka17 в сообщении #1177225 писал(а):

Странное решение Ала указывать Best Raw Score вместо Best Conjectural Score. Это вообще не имеет никакой пользы.

Согласен и это меня тоже возмутило, поэтому я написал на форум yahoo. Ну ладно у Ала всегда были свои правила по своим странным причинам. Главное что задачи всегда прекрасные и конкурсанты очень сильные.

-- 15.12.2016, 23:24 --

Vovka17 в сообщении #1177225 писал(а):

Я думаю, что задача очень-очень сложная. Пока принципиальной разницы в построенных полигонах максимальной и минимальной площади не вижу.

Задача действительно сложная так как надо посмотреть $(n!)^2$ вариантов расположения точек. Хотя многие из них будут нелегальны. Найдете несколько хороших максимальных решений и вы увидите некоторые приятные закономерности.

[gris]

Ну я только-только дескрипцию почитал и решил <сначала> попробовать ручками шаловливыми. Меня даже пока больше интересует глобальные стратегии участников. Мне кажется, что сейчас половина участников и не задействует программы, а тоже вручную двигает вершины и пытается увидеть те самые "некоторые приятные закономерности".
Остался вопрос: Если вершина лежит на стороне, считается ли это пересечением?

[dimkadimon]

gris в сообщении #1177295 писал(а):

Остался вопрос: Если вершина лежит на стороне, считается ли это пересечением?

Хороший вопрос, но не знаю ответ. Надо найти пример такого решения и посмотреть как он пройдет проверку на сайте.

[Scryer]

gris в сообщении #1177295 писал(а):

Остался вопрос: Если вершина лежит на стороне, считается ли это пересечением?

It is not allowed. Constraint 3 says "No two sides intersect, except at a shared vertex." A node on a side cannot be a shared vertex, since it would appear twice in the polygon, violating the rule against repeating row or column.

[dimkadimon]

Actually a point can be on the side without violating repeated condition. Eg point (5,5) sitting on edge (1,1)-(10,10).

[Vovka17]

gris, не стоит выкладывать здесь готовые решения, даже если вы пока не участвуете в конкурсе.

gris в сообщении #1177295 писал(а):

Если вершина лежит на стороне, считается ли это пересечением?

Да, это пересечение. Например полигон:

(1,3), (2,2), (3,4), (4,1), (5,5)

Выдаст ошибку: The line from (2,2) to (3,4) intersects the line from (5,5) to (1,3).

dimkadimon в сообщении #1177192 писал(а):

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

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

[dimkadimon]

Vovka17 в сообщении #1177448 писал(а):

А задача максимума - построить фигуру максимально близкую к границам области - "квадрату", с минимальной "вырезкой" игольчатой формы.

Именно поэтому максимальная задача чуть чуть проще на мой взгляд. То есть хорошое максимальное решение для $n$ можно получить из минимального решения для $(n-6)$. Ну в принципе я согласен, они почти одинаковые.

-- 16.12.2016, 20:02 --

Vovka17 в сообщении #1177448 писал(а):

Выдаст ошибку: The line from (2,2) to (3,4) intersects the line from (5,5) to (1,3).

Спасибо. Ну тогда все доказано - такие решения не принимаются.