Сегодня в 18:00 по Москве состоится GCJ Round 2. Напоминаю, что это шанс получить крутую футболочку — входите в число лучших 1000 участников и она ваша. 500 лучших участников проходят в Round 3.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Сегодня в 18:00 по Москве состоится GCJ Round 2. Напоминаю, что это шанс получить крутую футболочку — входите в число лучших 1000 участников и она ваша. 500 лучших участников проходят в Round 3.
Название |
---|
Как решалась В?
UPD: Снова я без футболки остался...
дополним каждый круг до квадрата со стороной степенью двойки с тем же центром, который этот круг содержит. Такие квадраты очень легко паковать
на Small можно было упаковать круг в квадрат со стороной 2R и расставлять по периметру.
А можно и не до степени двойки и расставлть жадно, начиная с больших. Но там проще конечно. Там похоже все что угодно надо было написать.
У меня относительно хитро получилось так.
Во-первых, у нас не кружки, а квадраты со стороной 2r и чувачками в центрах. Сразу поставим тех, которые капитально шире наших мат жадно в угол. Во-вторых, поймём, почему набор из квадратов со сторонами x1, x2, ... xn, таких, что сумма их площадей в ДВА раза меньше площади мата, всегда укладывается (а для начальных квадратов это верно). Развернём мат так, чтобы высота была меньше ширины. Пока есть квадраты со стороной минимум в полвысоты, кладём их жадно слева направо. А когда встретился квадрат со стороной l < h/2, откусываем от мата кусок шириной в l и высотой h и рекурсивно пытаемся положить на него как можно больше квадратов.
Идея в том, что мы всегда кладя квадраты, поддерживаем, что остаток мата — прямоугольник, и его площадь в два раза больше суммы площадей всех оставшихся квадратов. Такая рекурсивная процедура это поддерживает, и поэтому она ну вот просто обязана работать из соображений индукции.
Я тупо градиентно пихал в самую правую верхнюю позицию)
Я просто рандомно кидал круги в порядке убывания радиуса, проверяя пересечения. Плюс, самый большой ставил в (0, 0)
Упорядочил квадратики рандомно и кидал их по очереди сверху вниз (аки в тетрисе). X-координату для броска выбирал рандомно 16 раз, самый нижний "пролёт" квадратика утверждал как окончательный. Морально готовился к перезапуску всей схемы "до получения результата", но всё укладывалось с первого раза=)
Посортируем круги и будем брать сначала те, что побольше. Поставим самый большой круг 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 должен зайти, но почему-то в окончательных результах написали ВА :(
В смолл даже рандом заходит, кругов-то мало, максимум около 100 итераций потребуется.
Hу так идея в том, чтобы отжиг и в large зашёл! ;)
Да. Отжиг прекрасно заходит. Просто точности не хватило
Условие А — полное говно. Больше пытался понять, о чём вообще речь.
Согласен! "You will slowly and carefully climb up your original vine, so that the new vine you are holding will become horizonta" Как вторая лиана может стать горизонтально в том же 3 тесте если ползти вертикально вверх? В общем ну их в баню с такими условиями, я плюс ко всему ещё в переводчик лазил, а то Индиано-Джонсовских словечек накидали)
Либо она станет горизонтальной, либо натянется до максимума. В третьем тесте лианы станут буквой V.
а разве ее нельзя дотянуть до горизонтального? просто часть расстояния между корнями лиан будет покрывать вся длинна лианы, которую мы ухватили, а остальную часть — та, на которой мы висим?
Да это лучше. Спасибо. В моём объяснении не хватит разгона долететь до конца.
Можно, но в реальности это потребует бесконечной силы :)
А если уже разобрал его, расскажи что там нужно было делать? А то я до конца контеста его не понял.
Чел вначале держит первую лиану так, чтобы она была натянута, далее он прыгает и может зацепиться за лиану, которую он пролетел.. получится, что у него в руках две лианы, он их натягивает так, что теперь обе они будут горизонтальны, и теперь он может ещё их перебирать в руках так, чтобы они остались горизонтальными и он находился между их корнями. Затем он может опять прыгать. Нужно добраться до бабы, которая в конце, при условии, что можно вот так менять лианы.
Я решал эту задачу перебором от начала и смотрел для следующих лиан смогу ли я на них попасть и какой максимальный радиус я смогу описать всякой лианой (минимальный — 0), до которой достал. Ну и теперь если есть хоть одна лиана, которой мы можем попасть в конец зоны, то YES, иначе NO.
Спасибо.
Мне особо понравилось то, что герой может лазить по верёвке во время полёта, причём с невероятной скоростью. Т.е. на тест типа
ответ: YES.
И ещё пишут: "you are not a fictional hero". Ну какая нах тут правдоподобность?
Забавно, что 1004 человека набрало >= 21 балла. Интересно, выделит ли Google 4 дополнительные футболки? :)
Более чем уверен, что футболок у них с запасом.
UPD: потому как моему знакомому два года назад с местом, ниже границы на где-то 20 позиций, футболка пришла. И это вряд ли кто выше отказывался :-)
Не хватило несколько секунд на B-small — скачать файл, скопировать, переименовать, запустить прогу...
Обидно :(
Потому что ctrl+A, ctrl+C, ctrl+V быстрее, чем скопировать и переименовать файл.
gcj.py download B small 0 && B.exe && gcj.py submit B small 0
- быстрееОпасно так. Ты даже не просматриваешь, что вывела твоя программа, перед сабмитом?
Если есть очень мало времени, то очевидно нет. Обычно это две команды между которыми можно посмотреть.
Я к тому, что ты написал команды через &&, не успеешь ты посмотреть перед отправкой.
А я еще раз повторяю, что это вариант для осталось 30 секунд до конца контеста.
Мне также) Только у меня решение неправильное оказалось.
Как решать С?
Утверждение: всё хорошо, когда отрезки (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, иначе удаляем из списка все горы перед той, которую видит текущая, после чего вставляем текущую в начало списка. Чтобы получить высоты, рассмотрим дерево, в котором родителем каждой горы является гора, которую она видит. Будем обходить дерево (вначале заходим в вершину, потом в каждое поддерево по возрастанию номера) и присваивать каждой вершине угловые коэффициенты луча на самую высокую гору по возрастанию (например, последовательные целые числа).
Почему D-small такая дешевая? Начал ее писать вместо B-large и слил...
Мне тоже кажется, что написать обход графа состояний (или перебор) + простую динамику стоит больше, чем 8 баллов.
Ага, я накодил А и потом сел за D. В итоге, у меня даже D small не прошел. Сел дебажить и опомнился только за час до конца. Хорошо, хоть забил на нее и стал делать B и C.
Там проходит простое моделирование. Пусть изначально состояние — множество клеток, из которых достижима пещера. Ограничения позволяют сгенерировать все состояния (множества), достижимые из исходного путем применения команд для всех клеток множества сразу. Их можно прямо хранить как векторы в сете. Ответ Lucky, если достижимо состояние из одной клетки-пещеры.
Вообще задачи не понравились:(
В A еле разобрал условие.
В B многие писали, "ну может это работает", не доказывая
Сам в C тоже сдал "Сперва сделаем примерно, а потом подгоним".
Надеюсь, Round 3 будет покруче
Надеюсь, что не как в прошлом году, когда 2е от 67го отличалось только временем...
Ещё разбалловка странная. Посмотрев на разбалловку В (за large гораздо больше чем за small), поверил, что на В.large всякие халявы не прокатывают. Зря.
Я, чтобы поверить в успех по B-large, перед его скачиванием набросал генератор больших тестов и убедился, что моё решение без труда с ними справляется.
0 украинцев в топ-50, 1 украинец в топ-100... Затащили... Надеюсь, в следующем раунде будет круче.
Как тонко границы проходят... украинцы на 51-м и на 101-м местах :)
Did anyone else sort for B and then forget to reverse it before doing the output? Because... I did.
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
It seems that everyone got D-large wrong. Is there a bug in the testdata, or is the testdata extremely tricky?
Probably no one knows how to solve it properly so they tried some heuristics which didn't work.
Кстати. А то что их commandline tool показывает полный вердикт чекера, а не слово incorrect это баг или фича?
А что именно содержит этот вердикт? Может он ещё показывает и вердикты для .large по ходу контеста? :)
А можно поподробнее про ведикт, для тех кто command line tool не юзал?
Ну он выдал сообщение вида Incorrect. В 13-ом тесте 6-ой видит 9-го, а должен 8-го.
Ого, круто. Установлю-ка я эту штуку к следующему раунду.
Мне кажется это баг, а не фича. Хотя непонятно, как можно "случайно" добавить функционал, который получает вердикт по посылке. И непонятно, почему об этом нет нигде не слова.
Ну например скрипт который dashbpard его тоже получает и вырезает, а этот случайно не вырезал.
Я думаю, что это баг и его прикроют.
Скажем так. Правда ли, что в веб-интерфейсе точно никаких подробностией кроме Incorrect не увидишь?
Да.
Contest Analysis
http://code.google.com/codejam/contest/1842485/dashboard#s=a&a=4
Пожалуйста, подскажите что не верно в следующем решении C-small. Случайно генерирую высоты для гор h[]. Затем для каждой горы i выбираю гору j впереди с максимальным тангенсом, тоесть значением (h[j] — h[i]) / (j — i). Если j совпадает с обозримой наивысшей горой, то продолжаю. Если хоть одно не совпадает — генерирую заново.
Вердикт Incorrect? Отработать успевает? Если оба да, то бага в реализации скорее всего.
Дай код поглядеть)
Да вердикт Incorrect. Код: http://ideone.com/zW78R
Под правкой иллюстрация на триал тесты.
вы уверены, что 105 итераций хватает для нахождения ответа, даже для n < = 10? Мне это неочевидно, вроде для n = 10 различных тестов может быть около 5 тысяч, и непонятно, насколько часто при рандоме получается ответ на тот или иной.
UPD а в строчке 18 по-моему все-таки лучше сравнивать используя eps, хотя при рандоме это не особо влияет вроде
Во-первых, числа в аутпуте должны быть от 0 до 10^9, во-вторых, мне всё равно кажется, что 10^5 итераций — слишком мало.
rand() в каком диапазоне генерит?
http://www.cplusplus.com/reference/clibrary/cstdlib/rand/
http://www.cplusplus.com/reference/clibrary/cstdlib/RAND_MAX
Но это не так важно, поскольку приведенный выше код на ideone на сэмплах уже выдал числа, большие 10^9.
10^6 тоже не хватает, сейчас проверил. На 2 "possible" теста не находит ответ
10^8 на раунде хватило :) "impossible" тесты работали ~15-20 секунд, "possible" тесты находило максимум за 4 секунды.
читер :)
In problem B, once we fail enough attempts to say it isn't possible to add the current circle, should we start all over again or backtrack to when we added the previours circle?
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)
Is there someone who get T-shirts?
Look here.