Timur_Sitdikov's blog

By Timur_Sitdikov, history, 2 months ago, In English,

The contest on timus is over. How to solve D and J?

Read more »

 
 
 
 
  • Vote: I like it
  • +21
  • Vote: I do not like it

By Timur_Sitdikov, history, 4 years ago, In Russian,

Есть множество из n прямоугольников размера wi x hi. Требуется разместить их в минимальном количестве прямоугольников фиксированного размера W x H так, чтобы прямоугольники из исходного множества не накладывались друг на друга. В итоговом размещении прямоугольники могут быть как угодно повернуты, главное — чтобы они не накладывались друг на друга.

Размеры прямоугольников, вообще говоря, могут быть вещественными числами, но можно рассматривать и целочисленный вариант задачи. Также для простоты можно рассмотреть случай, когда допустимы только те размещения, в которых стороны размещаемых прямоугольников параллельны сторонам прямоугольников — контейнеров.

Источник — задача из жизни соответствующего содержания. Есть множество прямоугольных панелей стандартного размера, из них вырезаются нестандартные прямоугольные детали произвольных размеров. Известно, какие детали нужно получить, ну и требуется затратить на это минимальное количество исходных стандартных панелей.

Интуиция и знакомство с отдаленно похожей задачей на тимусе намекает, что данная задача NP-трудная. Поэтому был бы рад услышать любую идею и о приближенном алгоритме. Сам навскидку придумал пару эвристик, но что-то они не выглядят достаточно эффективными.

Заранее спасибо всем!

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By Timur_Sitdikov, 6 years ago, In Russian,

Основной сайт тренировок: http://neerc.ifmo.ru/trains/information/index.html Сегодня проходит очередная тренировка IFMO Training 20, я в упор не вижу, где найти задачи тренировки. Может ли кто-нибудь подсказать ссылку на условия задач?

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By Timur_Sitdikov, 8 years ago, In Russian,
Есть ли где-нибудь ссылка на подобное? Особенно интересуют сборы 2010 и 2011 годов. Заранее спасибо.

Read more »

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it