В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1761 membersпожаловаться на группу
2020 October 25

ЕВ

Евгений Вознесенский... in pro.algorithms
В общем, мне эта задача выпала на хакерранке в контесте на 2 часа. Это была 4-я задача из 4-х.
Я её не решил, поэтому и стало интересно, как это решать ...
источник
23:44пожаловаться#1

ЕВ

Евгений Вознесенский... in pro.algorithms
Matwey Kornilov
берешь большой прямоугольник min(x) min(y) max(x) max(y), он описывает все точки.
дальше ищешь как его поделить на два. таких способов будет 2(N-1), из них надо выбрать способ с минимальной суммой площадей.
потом каждый прямоугольник опять делишь пока не кончатся свободные прямоугольники
А почему способов будет 2*(n-1)?
Тип вертикально или горизонтально разбить по одной из точек?
источник
23:46пожаловаться#2

MK

Matwey Kornilov in pro.algorithms
ну можно разбить прямоугольник вертикально или горизонтально
источник
23:46пожаловаться#3

MK

Matwey Kornilov in pro.algorithms
для каждого варианта N-1 способ
источник
23:46пожаловаться#4

MK

Matwey Kornilov in pro.algorithms
или N-2
источник
23:47пожаловаться#5

MK

Matwey Kornilov in pro.algorithms
это зависит от того можешь ли ты одну точку описать прямоугольником нулевой площади?
источник
23:47пожаловаться#6

ЕВ

Евгений Вознесенский... in pro.algorithms
Можешь
источник
23:47пожаловаться#7

MK

Matwey Kornilov in pro.algorithms
или как этот случай описывается
источник
23:47пожаловаться#8

MK

Matwey Kornilov in pro.algorithms
Ну значит N-1
источник
23:47пожаловаться#9

ЕВ

Евгений Вознесенский... in pro.algorithms
Да, но когда прямоугольников будет m. То нам нужно для каждого прямоугольника рассмотреть разбиение, чтобы определить лучшее на текущем шаге?
источник
23:49пожаловаться#10

MK

Matwey Kornilov in pro.algorithms
не, m прямоугольников делается за log(m) шагов
источник
23:50пожаловаться#11

ЕВ

Евгений Вознесенский... in pro.algorithms
Ну например мы нашли оптимальное деление первого прямоугольника на два. Какой мы дальше из них будем делить?
источник
23:50пожаловаться#12

MK

Matwey Kornilov in pro.algorithms
оба
источник
23:51пожаловаться#13

MK

Matwey Kornilov in pro.algorithms
по очереди
источник
23:51пожаловаться#14

ЕВ

Евгений Вознесенский... in pro.algorithms
Ну вот очередь деления не будет ли влиять на ответ?
источник
23:51пожаловаться#15

ЕВ

Евгений Вознесенский... in pro.algorithms
Тип да, мы нашли оптимальное деление для первого прямоугольника из двух полученных и использовали все k прямоугольников. Для второго не осталось, например
источник
23:52пожаловаться#16

ЕВ

Евгений Вознесенский... in pro.algorithms
Насколько я понял, то это будет не рекурсия, а именно bfs? Тип если считать, что прямоугольник i-d получен на шаге d, то в дальнейшем делении будут только прямоугольники i-d+?
источник
23:54пожаловаться#17

MK

Matwey Kornilov in pro.algorithms
Я предлагаю строить бинарное дерево
источник
23:55пожаловаться#18

ЕВ

Евгений Вознесенский... in pro.algorithms
Ну так а строить по уровням?
источник
23:56пожаловаться#19

ЕВ

Евгений Вознесенский... in pro.algorithms
Или в глубину?
источник
23:56пожаловаться#20