Google Code Jam Round 3

12 лет назад, # |

Забыл, пропустил первые 45 минут. Ненавижу себя за это.

→ Ответить

12 лет назад, # ^ |

Google Clanedar с sms уведомлениями? Не знаю такого

→ Ответить

12 лет назад, # ^ |

-9

Да, это уже N-ое соревнование на выход на онсайт которое я так забываю. Тем не менее, 47-ое место :) Поздравляю с проходом!

→ Ответить

12 лет назад, # ^ |

-18

Проходят 25. Ну чуть больше, из-за отказывающихся/<18.

→ Ответить

Zlobober

12 лет назад, # ^ |

Ну так у Егора вообще первое место. Его можно поздравить :-)

→ Ответить

12 лет назад, # ^ |

Это я Егора поздравлял.. Ну а вдруг 22 человека возьмет и откажется :)

→ Ответить

12 лет назад, # ^ |

+14

А ок, сорри, я подумал что последние 2 предложения связанные. Тупанул. Егора тоже конечно поздравляю!

→ Ответить

12 лет назад, # |

Ну что ж, уже можно рассказывать решения. В A достаточно отсортировать по $\text{[math]}$ .

→ Ответить

natalia

12 лет назад, # ^ |

+13

И не забыть отсортировать еще и по индексу)

→ Ответить

12 лет назад, # ^ |

А в Java сортировка стабильная, там всё автоматически правильно получается.

→ Ответить

12 лет назад, # ^ |

В с++ тоже, если ему об этом сказать. stable_sort всех спасет. Только они это в самом видном месте условия написали.

→ Ответить

Zlobober

12 лет назад, # |

← Rev. 2 →

Правда ли, что D-large ничем не отличается по идее от D-small: строим граф на подстроках длины (k-1), строим рёбра между ними по добавлению одной буквы, а потом просто ищем минимальное количество рёбер, которое необходимо добавить, чтобы его можно было накрыть одним путём (с помощью известного критерия о существовании эйлерова цикла)? Естественно, граф в памяти не строим, а просто считаем сумму |deg_in - deg_out| по всем вершинам аккуратненько считая их степени.

UPD: У misof, тем не менее, какой-то поток, так что написанное выше вряд ли верно.

→ Ответить

12 лет назад, # ^ |

Тебе не кажется что подстрок длины 500 порядка 2⁵⁰⁰ * 5000?

→ Ответить

Zlobober

12 лет назад, # ^ |

У всех вершин одного класса эквивалентности одинаковые степени. Можно сжать весь класс в одну вершину, просто запомнив, что у неё каждая из степеней в 2^k раз больше.

→ Ответить

12 лет назад, # ^ |

На самом деле почти верно. Просто сумма разностей степеней — это тоже поток, только решаемый жадно. Нам еще надо k — 1 раз выкинуть из парсоча все внутренние ребра и добавить такие, что на i-м начная с нуля шаге (k — 1 — i) последних букв первой строки совпадают с началом второй строки. Каждый раз считаем сумму еще не пофилленной капасити слева, вычитаем 1 и прибавляем к ответу максимум этого и нуля

→ Ответить

12 лет назад, # |

Правда ли что в С нужен бинпоиск по ответу, внутри тернарник по количеству заказов, а функция считается жадно, делая заказы почти одинаковыми. А WA в large, это я где-то пропустил переполнение, а не непонятно как прошел small?

→ Ответить

12 лет назад, # ^ |

Нет, неправда. Решение намного проще.

→ Ответить

12 лет назад, # ^ |

Не правда, что нужно, или ты понмиаешь почему это не должно работать?

Казалось бы. Если мы зафиксировали число заказов, то количество еды в разных отличается не более чем на 1. Поэтому зафиксировав все что надо мы можем посчитать функцию. Кроме того, она выпуклая минус линейная, значит тоже выпуклая. Или нет?

→ Ответить

12 лет назад, # ^ |

То, что бинпоиск (а тем более тернарник) не нужен, не значит, что с ним неправильно.

→ Ответить

12 лет назад, # ^ |

Я перебирал кол-во типов жратвы, если их K то там два варианта: либо при макс. числе заказов, либо при макс. заказе K-ого типа.

→ Ответить

12 лет назад, # ^ |

Я так решал. Заметим, что последняя еда во всех заказах одинаковая (ее, возможно, 0 штук в каких-то заказах, но предыдущей еды там под максимум) Переберм эту последнюю еду. У нас до этого пусть в заказе каждом c ед суммарной стоимостью p1, эта еда стоит p2 и ее можно до q раз на заказ. Тогда мы максимизируем ca + b при условии ap1 + bp2 <= money и b <= qa (a — количество заказов, b — суммарное количество последних ед). Это делается жадно в зависимости от знака p1 / p2 — c

→ Ответить

12 лет назад, # ^ |

Я решал так: вначале забудем про ту еду, которую невыгодно использовать. Остальную еду можно отсортировать так, что и цена, и срок хранения будут строго возрастать. Будем брать еду в таком порядке: вначале первую, пока не закончится её срок хранения, потом аналогично следующую, и т. д. Если при этом построить график "количество дней от цены", то он будет представлять собой ломаную из n отрезков, выпуклую вверх. Найдём на ней точку, где отношение количества дней к цене максимально (это будет вершина, и её можно перебрать). Утверждается, что оптимальное количество доставок — одно из двух ближайших к этой точке (т. е. к отношению количества денег и стоимости в этой точке). Чтобы посчитать ответ при известном числе доставок, воспользуемся тем, что функция выпукла вверх, поэтому стоимости доставок должны быть как можно более близко. Соответственно, ответ ищется за линейное время проходом по тому же графику.

→ Ответить

andrewzta

12 лет назад, # ^ |

Бинпоиск по ответу не нужен, а так я именно так делал.

Когда знаем число заказов и знаем, что они все примерно одинаковые — дальше зачем внешний бинпоиск? Просто считаем максимум целевой функции и все.

Вообще я стремался равных значений в тернарнике, но с ними лажи почему-то не случилось...

→ Ответить

12 лет назад, # ^ |

Я чтобы не было проблем внутри тернарника в double считал, добавив бесконечно дорогой, бесконечно живущий продукт. А потом там где минимум в long long.

→ Ответить

12 лет назад, # ^ |

Зачем вообще там тернарник? Вроде же несложно доказать, что достаточно проверить только два значения — ближайшие к $\text{[math]}$ .

→ Ответить

12 лет назад, # ^ |

Может быть затем, что когда видишь выпуклую функцию, которую надо минимизировать, и нет проблем с TL, то многим проще написать тернарник, а не думать дальше?

→ Ответить

dzhulgakov

12 лет назад, # |

Никогда меня еще так не интересовал вопрос сколько человек из топ25 откажутся :) Насколько я понимаю, Гене еще нет 18, кто-то еще? :)

→ Ответить

12 лет назад, # ^ |

Egor в 2010 выйграл финал, пройдя в него с 33 места. Насчёт того, регулярно это или нет, сказать не могу.

→ Ответить

12 лет назад, # |

+13

B я решал с помощью DSU на HashMap'е. Bridge ищется достаточно очевидно, чтобы найти fork, нужно для каждой компоненты поддерживать, с какими сторонами она связана. Чтобы найти ring, будем делать так: когда добавляем камень, рассмотрим шесть соседних с ним позиций по порядку (при поиске ring можно считать, что поле бесконечное) и выделим группы идущих подряд (в порядке обхода), в которых стоят камни. Очевидно, что все камни в одной группе уже принадлежат одной компоненте связности. Так вот, ring образуется тогда и только тогда, когда камни в разных группах принадлежат одной компоненте. Соответственно, делаем merge на DSU с представителем каждой группы, если какой-то merge не удался, потому что вершины и так в одной компоненте, значит, ring найден.

→ Ответить

12 лет назад, # ^ |

Все ровно так

→ Ответить

Gassa

12 лет назад, # ^ |

А я ring искал, обходя по пустым клеткам доски поставленные камни. Если получается вернуться в ту же точку, в процессе повернувшись на 360 градусов в нужную сторону — кольцо. Работает за O (m) каждая проверка.

Остальное — bridge и fork — с помощью системы непересекающихся множеств, это проще.

→ Ответить

12 лет назад, # ^ |

DSU — это и есть система непересекающихся множеств.

→ Ответить

Gassa

12 лет назад, # ^ |

Я знаю. Я имел в виду, что bridge и fork проще, чем ring, а не то, что у меня проще, чем у тебя.

→ Ответить

12 лет назад, # ^ |

Было такое решение. Сначала делаем бинарный поиск по кол-ву поставленных фишек, и запускаем определение связных компонент. Проверка моста — есть ли компонента, у который >= 2 вершины. Проверка вилки — есть ли компонента, которая касается к >= 3 сторонам. Проверка кольца — если осталось >= 2 связных компонент из пустых клеток.

Это вроде не работает только для кольц, пустая клетка которых не является пустой в конце. И можно проскочить бинарным поиском момент, когда кольцо было. Поэтому потом по очереди пытаемся взять клетку с i-й фишкой, и посмотреть можно ли из неё добраться до края доски. Если можно, то есть кольцо за i-1 ход. После этого объединяем 2 части, выбирая минимум.

Получило WA. Тут что-то неучтено, или просто криво реализовано?

→ Ответить

12 лет назад, # ^ |

А проверку на кольцо делаешь для всех i? Причём нужно искать путь по позициям, свободным на момент перед выставлением i-й фишки. Не очень понятно, как сделать, чтобы это быстро работало.

Сейчас ты можешь скачать чьё-нибудь правильное решение и по стресс-тестировать со своим.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Да, делал для всех. Быстро это кажется можно сделать с помощью объединения множеств, для small делал просто DFS — во время укладывалось.

Потестил с правильным, в отличии от правильного решения, находит несколько колец позже чем надо. Оказалось, что "Если можно, то есть кольцо за i-1 ход." — фэйл. На самом деле, есть кольцо за max порядковый номер из тех уже поставленных фишек на данный момент, которых мы касаемся DFS'ом. Спасибо за помощь!

→ Ответить

ashmelev

12 лет назад, # ^ |

← Rev. 2 →

Делал так же, тоже проблема с кольцами. Исправил следующим образом: пусть у нас через i шагов не находится на доске кольца, но оно было раньше. Значит, в какой-то момент мы поставили фишку на единственную клетку в компоненте связности, при этом она не была на границе. Значит, на всех 6 соседних позициях тоже стояли фишки. Тогда будем удалять фишки в обратном порядке (с i-й по 0) и смотреть: если на момент удаления фишки у нее все 6 соседей тоже фишки, то раньше было кольцо. На большом тесте 4-5 минут работает.

→ Ответить