Сегодня в 18:00 состоится третий раунд Google Code Jam. 25 лучших участников выиграют поездку в Нью Йорк на финальный раунд (и возможность не ждать, пока Почта России не привезёт им уже выигранную футболку).
Сегодня в 18:00 состоится третий раунд Google Code Jam. 25 лучших участников выиграют поездку в Нью Йорк на финальный раунд (и возможность не ждать, пока Почта России не привезёт им уже выигранную футболку).
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Быстрое получение футболки отличная мотивация для того чтобы выйти в финал :-)
Опять 200 человек с 64 поинтами?
Забыл, пропустил первые 45 минут. Ненавижу себя за это.
Google Clanedar с sms уведомлениями? Не знаю такого
Да, это уже N-ое соревнование на выход на онсайт которое я так забываю. Тем не менее, 47-ое место :) Поздравляю с проходом!
Проходят 25. Ну чуть больше, из-за отказывающихся/<18.
Ну так у Егора вообще первое место. Его можно поздравить :-)
Это я Егора поздравлял.. Ну а вдруг 22 человека возьмет и откажется :)
А ок, сорри, я подумал что последние 2 предложения связанные. Тупанул. Егора тоже конечно поздравляю!
Ну что ж, уже можно рассказывать решения. В A достаточно отсортировать по
.
И не забыть отсортировать еще и по индексу)
А в Java сортировка стабильная, там всё автоматически правильно получается.
В с++ тоже, если ему об этом сказать.
stable_sortвсех спасет. Только они это в самом видном месте условия написали.Правда ли, что D-large ничем не отличается по идее от D-small: строим граф на подстроках длины (k-1), строим рёбра между ними по добавлению одной буквы, а потом просто ищем минимальное количество рёбер, которое необходимо добавить, чтобы его можно было накрыть одним путём (с помощью известного критерия о существовании эйлерова цикла)? Естественно, граф в памяти не строим, а просто считаем сумму |degin - degout| по всем вершинам аккуратненько считая их степени.
UPD: У misof, тем не менее, какой-то поток, так что написанное выше вряд ли верно.
Тебе не кажется что подстрок длины 500 порядка 2500 * 5000?
У всех вершин одного класса эквивалентности одинаковые степени. Можно сжать весь класс в одну вершину, просто запомнив, что у неё каждая из степеней в 2k раз больше.
На самом деле почти верно. Просто сумма разностей степеней — это тоже поток, только решаемый жадно. Нам еще надо k — 1 раз выкинуть из парсоча все внутренние ребра и добавить такие, что на i-м начная с нуля шаге (k — 1 — i) последних букв первой строки совпадают с началом второй строки. Каждый раз считаем сумму еще не пофилленной капасити слева, вычитаем 1 и прибавляем к ответу максимум этого и нуля
Правда ли что в С нужен бинпоиск по ответу, внутри тернарник по количеству заказов, а функция считается жадно, делая заказы почти одинаковыми. А WA в large, это я где-то пропустил переполнение, а не непонятно как прошел small?
Нет, неправда. Решение намного проще.
Не правда, что нужно, или ты понмиаешь почему это не должно работать?
Казалось бы. Если мы зафиксировали число заказов, то количество еды в разных отличается не более чем на 1. Поэтому зафиксировав все что надо мы можем посчитать функцию. Кроме того, она выпуклая минус линейная, значит тоже выпуклая. Или нет?
То, что бинпоиск (а тем более тернарник) не нужен, не значит, что с ним неправильно.
Я перебирал кол-во типов жратвы, если их K то там два варианта: либо при макс. числе заказов, либо при макс. заказе K-ого типа.
Я так решал. Заметим, что последняя еда во всех заказах одинаковая (ее, возможно, 0 штук в каких-то заказах, но предыдущей еды там под максимум) Переберм эту последнюю еду. У нас до этого пусть в заказе каждом c ед суммарной стоимостью p1, эта еда стоит p2 и ее можно до q раз на заказ. Тогда мы максимизируем ca + b при условии ap1 + bp2 <= money и b <= qa (a — количество заказов, b — суммарное количество последних ед). Это делается жадно в зависимости от знака p1 / p2 — c
Я решал так: вначале забудем про ту еду, которую невыгодно использовать. Остальную еду можно отсортировать так, что и цена, и срок хранения будут строго возрастать. Будем брать еду в таком порядке: вначале первую, пока не закончится её срок хранения, потом аналогично следующую, и т. д. Если при этом построить график "количество дней от цены", то он будет представлять собой ломаную из n отрезков, выпуклую вверх. Найдём на ней точку, где отношение количества дней к цене максимально (это будет вершина, и её можно перебрать). Утверждается, что оптимальное количество доставок — одно из двух ближайших к этой точке (т. е. к отношению количества денег и стоимости в этой точке). Чтобы посчитать ответ при известном числе доставок, воспользуемся тем, что функция выпукла вверх, поэтому стоимости доставок должны быть как можно более близко. Соответственно, ответ ищется за линейное время проходом по тому же графику.
Бинпоиск по ответу не нужен, а так я именно так делал.
Когда знаем число заказов и знаем, что они все примерно одинаковые — дальше зачем внешний бинпоиск? Просто считаем максимум целевой функции и все.
Вообще я стремался равных значений в тернарнике, но с ними лажи почему-то не случилось...
Я чтобы не было проблем внутри тернарника в double считал, добавив бесконечно дорогой, бесконечно живущий продукт. А потом там где минимум в long long.
Зачем вообще там тернарник? Вроде же несложно доказать, что достаточно проверить только два значения — ближайшие к
.
Может быть затем, что когда видишь выпуклую функцию, которую надо минимизировать, и нет проблем с TL, то многим проще написать тернарник, а не думать дальше?
Никогда меня еще так не интересовал вопрос сколько человек из топ25 откажутся :) Насколько я понимаю, Гене еще нет 18, кто-то еще? :)
Egor в 2010 выйграл финал, пройдя в него с 33 места. Насчёт того, регулярно это или нет, сказать не могу.
B я решал с помощью DSU на HashMap'е. Bridge ищется достаточно очевидно, чтобы найти fork, нужно для каждой компоненты поддерживать, с какими сторонами она связана. Чтобы найти ring, будем делать так: когда добавляем камень, рассмотрим шесть соседних с ним позиций по порядку (при поиске ring можно считать, что поле бесконечное) и выделим группы идущих подряд (в порядке обхода), в которых стоят камни. Очевидно, что все камни в одной группе уже принадлежат одной компоненте связности. Так вот, ring образуется тогда и только тогда, когда камни в разных группах принадлежат одной компоненте. Соответственно, делаем merge на DSU с представителем каждой группы, если какой-то merge не удался, потому что вершины и так в одной компоненте, значит, ring найден.
Все ровно так
А я ring искал, обходя по пустым клеткам доски поставленные камни. Если получается вернуться в ту же точку, в процессе повернувшись на 360 градусов в нужную сторону — кольцо. Работает за O (m) каждая проверка.
Остальное — bridge и fork — с помощью системы непересекающихся множеств, это проще.
DSU — это и есть система непересекающихся множеств.
Я знаю. Я имел в виду, что bridge и fork проще, чем ring, а не то, что у меня проще, чем у тебя.
Было такое решение. Сначала делаем бинарный поиск по кол-ву поставленных фишек, и запускаем определение связных компонент. Проверка моста — есть ли компонента, у который >= 2 вершины. Проверка вилки — есть ли компонента, которая касается к >= 3 сторонам. Проверка кольца — если осталось >= 2 связных компонент из пустых клеток.
Это вроде не работает только для кольц, пустая клетка которых не является пустой в конце. И можно проскочить бинарным поиском момент, когда кольцо было. Поэтому потом по очереди пытаемся взять клетку с i-й фишкой, и посмотреть можно ли из неё добраться до края доски. Если можно, то есть кольцо за i-1 ход. После этого объединяем 2 части, выбирая минимум.
Получило WA. Тут что-то неучтено, или просто криво реализовано?
А проверку на кольцо делаешь для всех i? Причём нужно искать путь по позициям, свободным на момент перед выставлением i-й фишки. Не очень понятно, как сделать, чтобы это быстро работало.
Сейчас ты можешь скачать чьё-нибудь правильное решение и по стресс-тестировать со своим.
Да, делал для всех. Быстро это кажется можно сделать с помощью объединения множеств, для small делал просто DFS — во время укладывалось.
Потестил с правильным, в отличии от правильного решения, находит несколько колец позже чем надо. Оказалось, что "Если можно, то есть кольцо за i-1 ход." — фэйл. На самом деле, есть кольцо за max порядковый номер из тех уже поставленных фишек на данный момент, которых мы касаемся DFS'ом. Спасибо за помощь!
Делал так же, тоже проблема с кольцами. Исправил следующим образом: пусть у нас через i шагов не находится на доске кольца, но оно было раньше. Значит, в какой-то момент мы поставили фишку на единственную клетку в компоненте связности, при этом она не была на границе. Значит, на всех 6 соседних позициях тоже стояли фишки. Тогда будем удалять фишки в обратном порядке (с i-й по 0) и смотреть: если на момент удаления фишки у нее все 6 соседей тоже фишки, то раньше было кольцо. На большом тесте 4-5 минут работает.
Кстати багу в commandline tool похоже прикрыли. Или просто в этот раз чекеры написали плохо, без комментариев, что произошло. Ну или хорошо наоборот.
When will the T-Shirt be send?
Closer to the new year