2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 7  След.
 
 Al Zimmermann - Polygonal Areas
Сообщение11.12.2016, 01:24 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение11.12.2016, 22:48 


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение12.12.2016, 00:10 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение12.12.2016, 06:43 
Аватара пользователя


29/04/13
2843
dimkadimon в сообщении #1175827 писал(а):
* Все точки имеют разные координаты по вертикали и по горизонтали.

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

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 15:04 
Аватара пользователя


01/06/12
755
Adelaide, Australia
Такая интересная задача, а все куда то пропали!

Сегодня узнал одну интересную вещь. Оказывается Ал показывает самую лучшую разницу одного участника в 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.

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 16:25 
Аватара пользователя


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

Цитата:
Что вы думаете?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 17:08 
Заслуженный участник
Аватара пользователя


13/08/08
12777
Я не участник, я только попробовать :oops:
Правильно ли я понял, что на одном значении $n$ можно заработать максимально один балл? Правильно ли нарисовал картинку? Правильно ли я думаю, что уже для каждого $n$ получены правильные полигоны, судя по скорам у верхних участников?
Изображение
(поправил картинку с учётом замечаний)

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 17:26 
Аватара пользователя


29/04/13
2843
gris в сообщении #1177248 писал(а):
Правильно ли я понял, что на одном значении $n$ можно заработать максимально один балл?

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

gris в сообщении #1177248 писал(а):
Правильно ли нарисовал картинку?

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

gris в сообщении #1177248 писал(а):
Правильно ли я думаю, что уже для каждого $n$ получены правильные полигоны, судя по скорам у верхних участников?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 17:32 
Аватара пользователя


01/06/12
755
Adelaide, Australia
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$ вариантов расположения точек. Хотя многие из них будут нелегальны. Найдете несколько хороших максимальных решений и вы увидите некоторые приятные закономерности.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение15.12.2016, 19:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.12.2016, 01:43 
Аватара пользователя


01/06/12
755
Adelaide, Australia
gris в сообщении #1177295 писал(а):
Остался вопрос: Если вершина лежит на стороне, считается ли это пересечением?

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.12.2016, 01:56 
Аватара пользователя


09/06/12
25
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.12.2016, 04:47 
Аватара пользователя


01/06/12
755
Adelaide, Australia
Actually a point can be on the side without violating repeated condition. Eg point (5,5) sitting on edge (1,1)-(10,10).

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.12.2016, 08:57 
Аватара пользователя


10/11/12
119
Бобруйск
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 писал(а):
Кстати мне кажется минимальная задача сложнее максимальной. В максимальной я вижу узоры которые можно подготовить и применить, а вот в минимальной я такого не наблюдал.

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение16.12.2016, 14:12 
Аватара пользователя


01/06/12
755
Adelaide, Australia
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).

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

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

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



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

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


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

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