Задача

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

Критерий качества

Оценка решения, успешно выполненного и уложившегося в ограничения по ресурсам, складывается из следующих факторов:

  • прибыльность размещенных продуктов;
  • разнообразие категорий размещённых продуктов;
  • brand integrity — продукты, расположенные в большой группе продуктов того же бренда (независимо от их категорий), приносят бонусные очки.

Призы

Призовой фонд задачи - 400 000 ₽! Команда-победитель получит 150 000 ₽, второе место - 100 000 ₽, третье 50 000₽, а четвертое и пятое места - по 25 000 ₽.
Плюс номинация за лучшее выложенное в опенсорс решение в 50 000₽.
Разрешены команды до 4 человек, со всего мира. В каждой из задач Retail Hero можно участвовать в разных составах команд.

 Правила соревнования

Условие задачи

Нам доступно n продуктов, пронумерованных от 1 до n. Каждый продукт относится к одной из k категорий и к одному из m брендов, а также обладает собственным показателем прибыльности c. Продукты одной и той же категории могут относиться к разным брендам, и один и тот же бренд может иметь продукты из разных категорий.

Продукты нужно расставить на продуктовом стенде. Представим стенд в виде прямоугольника с h рядами-полками, каждый из которых содержит w позиций. Любой продукт можно разместить на любую из позиций на любой полке. Каждый продукт занимает ровно одну позицию, и каждая позиция может содержать не более одного продукта.
Разрешается не размещать некоторые продукты, а также оставлять некоторые позиции на полках пустыми.

Для визуального удобства расстановка должна удовлетворять следующему требованию. Рассмотрим любую категорию t, в которой выставлен хотя бы один продукт. Тогда позиции, занимаемые продуктами категории t, должны образовывать сплошной прямоугольник. Формально, пронумеруем полки от 1 до h сверху вниз, аналогично пронумеруем позиции от 1 до w слева направо. Пусть al и ar — наименьший и наибольший номер полки, на которых есть хотя бы один продукт категории t, и bl и br — наименьший и наибольший номер позиции среди выставленных продуктов категории t. Тогда для любого номера полки a и любой позиции b, таких что al ≤ a ≤ ar и bl ≤ b ≤ br позиция b на полке a должна содержать продукт категории t.

Пример:

Пусть h = w = 4, и k = 3. Рассмотрим следующую расстановку (здесь цифры означают позиции, занятые продуктами соответствующей категории, точки означают пустые позиции):

  11.4
112.
..2.
..2.

pic 1

Это расстановка корректна, так как позиции продуктов категорий 1, 2, 4 образуют прямоугольники, продукты категории 3 отсутствуют. Другой пример:

  1111
1231
1241
1111

pic 2

Данная расстановка некорректна, так как продукты категории 1 не занимают сплошной прямоугольник.

Архив с материалами

Формат входных данных

В первой строке через пробел записано шесть целых чисел n,k,m,h,w,D0:

  • 1 ≤ n ≤ 5000;
  • 1 ≤ k,m ≤ 50;
  • 1 ≤ h ≤ 10;
  • 1 ≤ w ≤ 100;
  • 1 ≤ D0 ≤ 106.

Следующие n строк описывают параметры продуктов. В i-й из этих строк записано три целых числа ti,bi,ci (1 ≤ ti ≤ k, 1 ≤ bi ≤ m, 1 ≤ ci ≤ 1000) - категория, бренд и базовая прибыльность продукта соответственно.

Формат выходных данных

Выведите h строк, в каждой из которых через пробел записано w целых чисел. j-е число в i-й строке должно быть равно 0, если j-я позиция на i-й полке пуста, иначе это число должно быть равно номеру продукта в данной позиции.

Алгоритм генерации тестов

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

  • h,w,n,k,m,D0;
  • частотности категорий pi и частотности брендов qi (сумма pi и сумма qi равны 1);
  • базовая прибыльность категорий Ai и брендов Bi.

Для каждого из брендов случайно выбирается от 1 до 10 различных категорий продуктов, которые производит этот бренд (количество может быть выбрано вручную).

Далее независимо генерируются n продуктов по следующему алгоритму:

  1. Случайно и независимо выбрать категорию t и бренд b согласно распределениям, заданным числами pi и qi.
  2. Если бренд b не производит категорию t, вернуться к шагу 1.
  3. Назначить базовую прибыльность продукта, равную c = round(ξ(At + Bb)), где ξ - случайное вещественное число из диапазона [0.5, 1], round — операция математического округления.

Система оценки

Ваше решение будет запущено на всех тестах в наборе. Общая оценка решения равна сумме оценок для каждого теста в наборе.

Оценка решения C для одного теста вычисляется по следующей формуле. Если ваша программа не смогла успешно завершиться в отведённое время, либо ваше решение некорректно, то C = 0. Оценка корректного решения равна:

В этой формуле используются следующие обозначения:

  • D0 - заданный коэффициент бонуса за разнообразие категорий;
  • qj - количество размещённых продуктов категории j;
  • Ii = 1, если продукт i был размещён, и 0 в противном случае;
  • ci - заданная базовая прибыльность продукта i;
  • Ai - максимальное количество позиций в сплошном прямоугольнике, занятом продуктами одного бренда и содержащем позицию продукта i.

Пример оценки решения

Пусть h = w = 4, n = 9, k = m = 3, D0 = 50, и параметры продуктов заданы следующими массивами:

  • категории t = [1,1,1,1,2,2,2,3,3];
  • бренды b = [1,1,2,3,1,1,3,2,2]
  • базовая прибыльность c = [2, 3, 5, 10, 4, 3, 9, 6, 7]

Рассмотрим следующий способ размещения (цифры означают номер размещённого продукта):

  .567
.12.
.438
...9

Категории, бренды и значения Ai распределены следующим образом:

  .222   .113   .441   
.11.   .11.   .44.   
.113   .322   .122   
...3   ...2   ...2   

pic 3

Значения qj равны следующему: q1 = 4, q2 = 3, q3 = 2. Тогда бонус за разнообразие равен D ≈ 64.328, суммарная эффективная прибыльность равна E = 91 и общая оценка равна C = D + E ≈ 155.328.

Формат решений

В проверяющую систему необходимо отправить файл с кодом решения. Расширение загруженного файла влияет на то, как будет происходить запуск.

Есть два варианта:

1. Решение в одном модуле (как на ACM ICPC). Допускаются языки программирования Python 3, Java, C++. Модуль предварительно компилируется в бинарный исполняемый файл, затем запускается на тестах. Файл решения должен иметь соответствующее расширение: .py, .java или .cpp.

2. Архив с кодом. Необходимо отправить ZIP-архив, содержащий набор файлов, необходимых для запуска решения. В корне архива необходимо поместить файл metadata.json с информацией о том, как запустить решение:

{
"image": "datasouls/python",
"entry_point": "python solution.py"
}

Здесь image — поле с названием docker-образа, в котором будет запускаться решение (допускается использование публичных Docker-образов из DockerHub), entry_point — команда, при помощи которой запускается решение. Текущей директорией во время запуска решения будет являться путь, по которому находится файл metadata.json.

Решения запускаются в изолированном окружении при помощи Docker. Время и ресурсы во время тестирования ограничены.

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

Технические ограничения

Решение запускается в следующих условиях:

  • решению доступны ресурсы: 1 Гб оперативной памяти, 4 vCPU;
  • решение не имеет доступа к интернету;
  • время на отработку одного теста 15 секунд;
  • максимальный размер упакованного и распакованного архива с решением: 256 Мб.