дополним каждый круг до квадрата со стороной степенью двойки с тем же центром, который этот круг содержит. Такие квадраты очень легко паковать

У меня относительно хитро получилось так.

Во-первых, у нас не кружки, а квадраты со стороной 2r и чувачками в центрах. Сразу поставим тех, которые капитально шире наших мат жадно в угол. Во-вторых, поймём, почему набор из квадратов со сторонами x1, x2, ... xn, таких, что сумма их площадей в ДВА раза меньше площади мата, всегда укладывается (а для начальных квадратов это верно). Развернём мат так, чтобы высота была меньше ширины. Пока есть квадраты со стороной минимум в полвысоты, кладём их жадно слева направо. А когда встретился квадрат со стороной l < h/2, откусываем от мата кусок шириной в l и высотой h и рекурсивно пытаемся положить на него как можно больше квадратов.

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

Я тупо градиентно пихал в самую правую верхнюю позицию)

Я просто рандомно кидал круги в порядке убывания радиуса, проверяя пересечения. Плюс, самый большой ставил в (0, 0)

Посортируем круги и будем брать сначала те, что побольше. Поставим самый большой круг R в левый верхний угол. Разрежем квадрат на две полоски ширины R и два "квадрата". Один уже занят кургом. Решим задачу рекурсивно, при этом ширину полосок можно просто уменьшить до 0, А размеры "квадрата" уменьшаются на R+Rmax, где Rmax — радиус самого большого круга на момент запуска функции для этого "квадрата". Доказывать это решение не умею, но оно прошло.

Отсортируем круги по невозрастанию радиусов. Пусть мы расставили первые n кругов, ставим n+1-ый. Увеличим радиусы первых n кругов на радиус n+1-ого, получим фигуру, в которую не может попасть центр n+1-ого круга. Т.к. по условию площадь этой фигуры не превосходит 4/5 площади прямоугольника, n+1-ый круг можно гарантированно поставить куда-то, причем если искать это место рандомом то оно находится в среднем за 5 попыток

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

Я представлял оставшееся поле как набор прямоугольников. Ставил очередной круг в левый верхний угол, а оставшуюся часть разрезал на два прямоугольника: одна — то, что справа, а другая — то, что снизу и снизу справа. Вставлял прямоугольники в начало списка, при поиске брал первый, в который этот круг лезет. И самое главное: круги надо обрабатывать по убыванию радиуса.

Я подозреваю, что это решение можно доказать, аккуратно присваивая неиспользованную площадь кругам, но я этого не делал.

Я решал так:
1. Заменим круги радиуса R на квадраты радиуса 2*R, если мы разместим должным образом эти квадраты, то и круги тоже сможем разместить.
2. Сортируем квадраты по убыванию радиуса.
3. Начинаем с нижнего левого угла укладывать квадраты — первый центром в точку (0, 0), второй — вплотную к нему справа, ордината центра — 0.
4. Делаем так, пока не упремся вправо.
5. Сдвигаем нижнюю границу мата на 2*r[0], r[0] — размер максимального квадрата в нижнем ряду.
6. Повторяем пункты 3-5, пока не закончатся квадраты.

в small зашёл отжиг. На самом деле и в large должен зайти, но почему-то в окончательных результах написали ВА :(

Согласен! "You will slowly and carefully climb up your original vine, so that the new vine you are holding will become horizonta" Как вторая лиана может стать горизонтально в том же 3 тесте если ползти вертикально вверх? В общем ну их в баню с такими условиями, я плюс ко всему ещё в переводчик лазил, а то Индиано-Джонсовских словечек накидали)

А если уже разобрал его, расскажи что там нужно было делать? А то я до конца контеста его не понял.

Более чем уверен, что футболок у них с запасом.

UPD: потому как моему знакомому два года назад с местом, ниже границы на где-то 20 позиций, футболка пришла. И это вряд ли кто выше отказывался :-)

Потому что ctrl+A, ctrl+C, ctrl+V быстрее, чем скопировать и переименовать файл.

Мне также) Только у меня решение неправильное оказалось.

Утверждение: всё хорошо, когда отрезки (x, to[x]) вкладываются. Необходимость очевидна. Достаточность сейчас вытечет из алгоритма.

Будем рекурсивно придумывать высоты горам с a-ой по b-ую с условием, что тангенс угла наклона между b и a равен k и все остальные горы на этом отрезке строго ниже отрезка ab. Берём последовательность гор x1 = a + 1, x2 = to[x1], x3 = to[x2], ... , xk = b и кладём их все на прямую с тангенсом k + 1. А содержимое отрезков [x1, x2], [x2, x3], ... покрываем рекурсивно, но уже с тангенсом угла k + 1. Более-менее очевидно, что это даст нам то, что нужно — из внутренности отрезка ab ничего не увидеть, потому что снаружи отрезка ab тангенс угла наклона меньше.

Нам потребуется не более чем 1 + 2 + 3 + ... + n места, то есть порядка n^2. Как-то так.

Я делала такую магию. Построим функциональный граф (из каждой вершины дуга в наибольший видимый из нее пик). Сначала юзаем последнюю вершину и ставим ей очень большую высоту. Потом начиная с первой непоюзанной вершины строим цепочку, заканчивающуюся в какой-нибудь поюзанной. Юзаем вершины получившейся цепочки и расставляем для них высоты так, чтобы они были на одной прямой. Затем обрабатываем следующую цепочку и т.д. Для каждой следующей цепочки увеличиваем наклон. Решение за квадрат. Если порисовать — понятно, почему работает.

UPD. Решение фактически как у Zlobober, только без рекурсии. Случай Impossible удобно отсекать в самом конце проверкой за квадрат.

Идём с конца и поддерживаем список гор, которые ещё могут быть видны как самые высокие. Вначале в этом списке только последняя гора. Если очередная гора видит гору не из списка, то impossible, иначе удаляем из списка все горы перед той, которую видит текущая, после чего вставляем текущую в начало списка. Чтобы получить высоты, рассмотрим дерево, в котором родителем каждой горы является гора, которую она видит. Будем обходить дерево (вначале заходим в вершину, потом в каждое поддерево по возрастанию номера) и присваивать каждой вершине угловые коэффициенты луча на самую высокую гору по возрастанию (например, последовательные целые числа).

Мне тоже кажется, что написать обход графа состояний (или перебор) + простую динамику стоит больше, чем 8 баллов.

Ага, я накодил А и потом сел за D. В итоге, у меня даже D small не прошел. Сел дебажить и опомнился только за час до конца. Хорошо, хоть забил на нее и стал делать B и C.

Там проходит простое моделирование. Пусть изначально состояние — множество клеток, из которых достижима пещера. Ограничения позволяют сгенерировать все состояния (множества), достижимые из исходного путем применения команд для всех клеток множества сразу. Их можно прямо хранить как векторы в сете. Ответ Lucky, если достижимо состояние из одной клетки-пещеры.

Надеюсь, что не как в прошлом году, когда 2е от 67го отличалось только временем...

Ещё разбалловка странная. Посмотрев на разбалловку В (за large гораздо больше чем за small), поверил, что на В.large всякие халявы не прокатывают. Зря.

Как тонко границы проходят... украинцы на 51-м и на 101-м местах :)

I did it to, and I got 2 WA because of it... And then 1 more WA because of mistake in reversing.

Yes!!) I thought that I am the only one) It cost me 2 tries...

I did :) But I've found it before downloading large test

Ya, 2 incorrect submissions for me, too :(

I did! 3 penalties + 20 minutes wasted because of that! Would have been in top-500 otherwise :(

I remembered to reverse before printing the output but I forgot to sort before processing :D

Probably no one knows how to solve it properly so they tried some heuristics which didn't work.

А что именно содержит этот вердикт? Может он ещё показывает и вердикты для .large по ходу контеста? :)

А можно поподробнее про ведикт, для тех кто command line tool не юзал?

Скажем так. Правда ли, что в веб-интерфейсе точно никаких подробностией кроме Incorrect не увидишь?

Вердикт Incorrect? Отработать успевает? Если оба да, то бага в реализации скорее всего.
Дай код поглядеть)

Backtracking works. I try 20 different locations then go back to the previous circle.

As stated in the analysis, we always have at least 20% chance to succeed. So the probability to fail x times is 0.8^x, which decreases rapidly. I also tried a solution without backtracking and it worked very fast. It means we only need to repeat the randomize progress until finding a consistent point. (you may take a look at tourist's code)

Look here.