Всем привет!

Как вы знаете, уже третий год подряд финалисты ABBYY Cup собираются летом в московском офисе ABBYY на День открытых дверей. В этом году мне выпала честь написать пост о том, как прошел финал ABBYY Cup 3.0. Начнем с того, что все дни до 17 июля и после в Москве лил проливной дождь, что совсем не добавляло нам оптимизма: ранее заявленная развлекательная программа сильно зависела от погоды. Похоже, Вселенной было интересно узнать, как пройдет День открытых дверей ABBYY 2013, и она решила не портить этот день осадками : )

Но сюрпризов нам все равно хватило. Автобус с участниками, прибывшими в Москву 16 июля, приехал из кампуса МФТИ в Долгопрудном на целый час раньше. Вот уж никто не ожидал такого подарка от традиционных пробок на Дмитровском шоссе.

И все бы хорошо, если бы остальные участники не должны были приехать к назначенным 10 часам. «Недолго» думая, мы решили развлечь ребят роликом с многообещающим названием «Правда об ABBYY» (или кому-то послышалось нечто другое? : ) В нем в шутливой форме рассказывалось об условиях работы в компании, а также об исследованиях, ведущихся на «самом переднем» крае науки.
В 10:40 по московскому времени начался финал ABBYY Cup 3.0! Для меня как для организатора это самое приятное время. Тихо-спокойно идет контест, участники решают задачи… А нам остается с интересом наблюдать за изменениями в таблице результатов соревнования и болеть за любимчиков ; )

В результате, Egor, опоздавший к началу контеста, подозреваю, даже не завтракавший в этот день, занял первое место! Таким образом, пятерка призеров: Egor, KADR, yeputons, burunduk3, Petr . А полная таблица результатов соревнования здесь.

После тяжелого испытания участники заслужили полноценный горячий обед. Обсуждение задач плавно переместилось в столовую. В этот день мы не могли обойтись без рассказа о компании, поэтому мы попросили выступить наших сотрудников. Сначала с участниками пообщался президент и генеральный директор группы компаний ABBYY Сергей Андреев, а позже главный консультант по продуктам Compreno Александр Костюченко рассказал об исследованиях компании в области компьютерной лингвистики. Далее последовала небольшая экскурсия по офису ABBYY. Некоторые участники уже не первый год приезжают к нам офис. Так, например, Edvard и aRSeniy быстро нашли xbox и так увлеклись игрой, даже пропустили разбор задач.

И тут мы подошли к самому главному – награждению. Мы приготовили для ребят сюрприз: все подарки вручал Умный Бобер. Каждый смог прикоснуться к прекрасному: кто-то пожал ему руку, кто-то погладил, а вот Alex_KPR даже обнял.

В качестве развлекательной программы в этом году специально для ребят мы подготовили уникальный квест по центру Москвы! Разбившись на команды, получив задания, фонарики, карты и компасы, в 17 часов участники разбежались в поисках ответов на совершенно непонятные вопросы, которые в конечном итоге должны были привести к финишу. Завершить приключение можно было в любой момент: можно было позвонить нам по специальному номеру и узнать адрес места финиша.

В процессе подготовки к квесту мы предполагали, что в 21 час все команды устанут и либо найдут место финиша, либо позвонят и сдадутся. Но не тут-то было! В назначенное время никто до финиша еще не дошел, но и сдаваться никто не хотел! Вот это я понимаю, воля к победе! Представьте, каково было команде Mimino. Специально для него мы подготовили правила на английском языке и предоставили команде переводчика. Думаю, это соревнование для Mimino было куда сложнее любого контеста! А впрочем, аналогичное можно сказать и для всех участников мероприятия : )

В 22 часа команды потихоньку начали подходить финишу, который к слову, был назначен в одном из местных антикафе. Специально для квеста мы арендовали зал-библиотеку. В нем были собраны книги, старая мебель и музыкальные инструменты, приглушенный свет… Словом, атмосфера была очень романтичная и располагала к поэзии: вот бы сейчас вслух почитать Пастернака. И что же вы думаете? Fefer_Ivan, сидя в винтажном кресле, совершенно непринужденно продекларировал нам одно из стихотворений великого русского поэта XX века. Который год после Дня открытых дверей ABBYY я еще неделю пребываю в абсолютно влюбленном состоянии во всех спортивных программистов! Но в этот раз я была поражена просто до глубины души. Вот уж, правда, талантливый человек талантлив во всем!

Команды постепенно подтягивались, делились впечатлениями и взахлёб рассказывали о своих приключениях. И, как нам показалось, несмотря на большую усталость, были довольными. Дождавшись всех участников и подкрепившись после такой необыкновенной прогулки, мы постепенно стали расходиться: кто в метро, кто к автобусу в Долгопрудный, а кто на работу в офис ABBYY : )

На этом рассказ о Дне открытых дверей ABBYY 2013 заканчивается. Мы хотим сказать огромное спасибо всем участникам мероприятия! Мы очень рады, что есть ребята, которые приезжают к нам не первый год. Не менее приятно познакомиться с новыми лицами. Надеемся, что этот день оставил теплые воспоминания и у вас. До встречи!

https://get.google.com/albumarchive/pwa/114842746780416406882/JInSLJ?authkey=Gv1sRgCLPuzoHEm4X_YQ

Альбом с фотографиями есть в ВКонтакте.

Всем привет!

Вчера состоялся финал ABBYY Cup 3.0! Хочется сказать большое спасибо всем-всем: кто решал контест, кто помогал его готовить, авторам задач и еще много кому! О том, как прошел День открытых дверей ABBYY, мы расскажем позже, а пока разборы:

Задача A

Утверждение: если прогулка начинается с дерева i и заканчивается в дереве j, то нужно выпилить все деревья до i, все деревья после j и все деревья с отрицательной эстетической привлекательностью между i и j. Для решения подзадачи A1 достаточно для каждой пары деревьев с одинаковой эстетической привлекательностью воспользоваться утверждением и выбрать максимум; ограничения позволяли сделать это хоть за O(n²), хоть за O(n³). Для решения подзадачи A2 требуется такое утверждение: сколько бы ни было деревьев с одинаковой эстетической привлекательностью, нам всегда выгодно рассматривать только пару из самого левого и самого правого таких деревьев. Тогда количество различных рассматриваемых пар сократится до O(n) (с O(n²)), дальше можно делать что угодно, например, считать частичные суммы или брать сумму на отрезке.

Задача B

Для решения подзадачи B1 требовалось проэмулировать поведение Брабобрея в точности так, как описано в условии. Для решения подзадачи B2 достаточно для каждого завершающего бобра хранить взведённый флаг-единичку. Назовём завершающим бобром такого бобра i, что справа от него нет бобра i + 1 (то есть в случае запроса, включающего бобров i и i + 1 придётся запускать Брабобрей ещё один раз). Тогда при обмене пары бобров i и j местами будет всего четыре кандидата, где состояние флага может измениться: i - 1, i, j - 1, j. Ответ на запрос — это просто количество завершающих бобров на отрезке, что уже является классической задачей.

Задача C

Для решения подзадачи C1 можно либо посчитать динамику, либо жадно вычитать наибольшую цифру — несложно доказывается, что всегда требуется вычитать именно наибольшую цифру. Для подзадачи C2 достаточно посчитать динамику для первого миллиона, разбить мысленно число на две группы цифр — старшие разряды и младшие — и выполнять не одно вычитание, а целую серию вычитаний, чтобы мгновенно минимизировать младшие разряды. Для решения подзадачи C3 необходимо уйти от желания хранить в параметрах динамики само число, а хранить лишь количество разрядов.

Задача D

Совершенно очевидно, что судьба бобрактора такова: либо мы пройдём по стрелкам и выберемся, либо уткнёмся в цикл. Во втором случае необходимо найти длину цикла l, но тогда нам нужен лишь остаток от деления времени на длину цикла. Таким образом, мы мысленно избавились от второго случая. Для решения подзадачи D1 достаточно проэмулировать поведение бобрактора, сохраняя на каждом шаге время последнего посещения текущей точки (чтобы определить длину цикла, когда мы на него наступим второй раз). Для решения подзадач D2 и D3 требовалось построить граф перемещений бобрактора, а затем обработать каждый из тестов мультитеста, причём в D2 граф можно построить в лоб, да и найти ответ на каждый тест — пройти по графу в лоб. В D3 предлагается использовать логарифмические структуры данных. В целом, идея решения лежит на поверхности; задача представляет интерес именно с технической точки зрения.

Задача E

Для решения подзадачи E1 необходимо прийти к следующему утверждению: если на ребре x → y есть пометки x и y, идущие подряд, то такое ребро может генерировать искомый путь. Назовём такое ребро инициирующим. Несложно понять, что, зафиксировав инициирующее ребро, дальнейший путь в обе стороны восстанавливается однозначно. Теперь надо понять, что достаточно рассматривать только инициирующие рёбра. Рассмотрим любой требуемый путь в графе. Он содержит p вершин и p - 1 рёбер. Но тогда по принципу Дирихле хотя бы одно ребро должно содержать как минимум две пометки. Пусть какое-то ребро x → y содержит пометки a b, (a, b) ≠ (x, y). Но тогда разрежем этот путь на два по ребру x → y и заметим, что тогда какой-то из двух подпутей уж точно содержит больше пометок, чем есть рёбер. Рассуждая подобным образом можно прийти к выводу, что найдётся хотя бы одно ребро x → y с пометками x и y. Если ни одного инициирующего ребра нет, то искомого пути не существует. Путь, сгенерированный инициирующим ребром — это кратчайший валидный путь для данного инициирующего ребра. К нему можно дописывать входящие и исходящие хвосты так, чтобы путь становился длиннее. Хвосты не должны содержать инициирующих рёбер, потому что инициирующие рёбра генерируют свои пути. Любой валидный путь — это путь из троек ("входящий хвост", "путь инициирующего ребра", "исходящий хвост"), соединённых между собой рёбрами без пометок. Для решения подзадачи E2 можно предподсчитать все хвосты и все сгенерированные инициирующими рёбрами пути, а затем динамикой посчитать количество путей фиксированной длины.

Друзья, вот и закончился онлайн-тур ABBYY Cup 3.0!

Спасибо большое всем участникам! Мы приносим свои извинения за проблемы с тестированием. MikeMirzayanov всех уже обрадовал планами о закупке тестирующих машин. Надеемся, что в будущем таких ситуаций не повторится.

А вот и разборы задач:

Задача "Спецзадание"

Это была одна из самых простых задач из предложенных. Решение задачи сводится к рассмотрению нескольких случаев. Изначально ответ равен единице. Заметим, что если в строке встречается "?", то он увеличивает число возможных кодов в 10 раз. За исключением случая, когда "?" стоит в начале строки. Тогда он увеличивает число возможных кодов в 9 раз. Далее нужно рассмотреть случаи, когда среди символов строки встречаются буквы. Тут нужно рассмотреть два случая:

UPD2: Дорогие участники!

Как мы и обещали, лучших 25 участников по результатам онлайн-тура ABBYY Cup 3.0 и победителей конкурса задач мы приглашаем на День открытых дверей ABBYY, который состоится 17 июля в московском офисе ABBYY. Всем гражданам РФ мы предоставим полную компенсацию дороги туда-обратно (по предварительному согласованию суммы), с остальными победителями вопрос компенсации будет обсуждаться индивидуально.

Дорогие победители, напишите, пожалуйста, в течение 5 дней нам на электронный ящик [email protected] о своем желании приехать.

Если вы не попали в 25 лучших и не являетесь победителем конкурса задач, но очень хотите приехать, также напишите нам в эти сроки. Напоминаем, что всех участникам Дня открытых дверей мы обеспечим питанием и проживанием.

По нашему опыту, примерно треть участников Дней открытых дверей состоит из ребят, не прошедших в финал. Мы считаем очень важным поддерживать менее опытных спортивных программистов, которые не посещают из года в год столичные онсайты, и дать им возможность познакомиться с IT-индустрией, пообщаться с коллегами в неформальной обстановке.

UPD1: Разборы!

UPD: Друзья, уже сегодня состоится онлайн-тур ABBYY Cup 3.0!

На всякий случай, несколько замечаний:

Всем привет.

А вот и долгожданные результаты конкурса задач по спортивному программированию от ABBYY! Поздравляем наших победителей:

Наверное тем победителям, кто прислал несколько задач, интересно знать, какая именно из задач принесла им победу. Этот вопрос вы можете задать мне лично в сообщении или в письме.

Всем участникам конкурса мы хотим подарить на выбор один из продуктов ABBYY для персонального использования! А победители могут выбрать два продукта. Сообщите нам, пожалуйста, о вашем выборе письмом.

Также всех победителей конкурса мы приглашаем на День открытых дверей ABBYY, который будет проходить в московском офисе ABBYY. Даты и формат компенсаций дороги и проживания будет обсуждаться индивидуально в переписке.

На данный момент решено, что контест будет проходить в два этапа: онлайн-часть (приблизительно начало июня) и онсайт (приблизительно середина июля на Дне открытых дверей ABBYY).

Спасибо большое всем участникам конкурса, ждем официального анонса ABBYY Cup 3.0!

Всем привет!

Закончился первый конкурс задач по спортивному программированию от ABBYY. Спасибо всем участникам за интересные задачи! После первого поста с цитатами авторы вошли во вкус, так что теперь можно издать целую книгу про приключения Умного Бобра! Победителей конкурса мы постараемся объявить через две недели, а пока немного статистики:

Друзья, напоминаем, что конкурс задач по спортивному программированию продолжается. Впереди целые выходные, чтобы придумать гениальную задачу и успеть отправить на [email protected].

А пока мы продолжаем нашу рубрику "цитаты из школьных сочинений задач":

Спасибо всем авторам за задачи и хорошее настроение, которое вы нам дарите!

Друзья, недавно в нашем Хаброблоге мы опубликовали пост о том, что же вообще представляет из себя задача спортивного программирования. Изначально пост предполагал сравнение олимпиадных задач с задачами реальной разработки. Однако в финальном варианте мы решили исключить аналогии с промышленным программированием. Будет интересно почитать в комментариях примеры ваших подобных сравнений :)

"Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с олимпиадной задачи.

Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.

Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи :) Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.

Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:

Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.

Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).

Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.

Существует немало способов оценки решений для «классических» задач:

Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

Конечно, говорить об особенностях олимпиадных задач можно бесконечно. Мы осветили лишь самые главные моменты. Если у вас есть вопросы или комментарии – добро пожаловать в комментарии..."

Создание олимпиадных задач — занятие творческое, требующее не только специальных знаний, но и вдохновения. Прийти к вам в качестве музы я не могу, но надеюсь, следующие материалы вас вдохновят на создание, например, “эвристических” задач:

1) Лекция (.ppt) руководителя группы печатного распознавания ABBYY Антона Масаловича.

Антон читал эту лекцию на летних тренировочных сборах IOI 2012, где разобрал некоторые олимпиадные задачи, связанные с распознаванием, и подходы к распознаванию вообще.

2) Лекция (видео в ВКонтакте) руководителя морфологии ABBYY Андрея Андрианова в Технопарке Mail.ru.

Укороченный вариант этой лекции кто-то из вас уже слышал в ЛКШ 2012 или на онсайте ABBYY Cup 2.0.

Вопросы по содержанию пишите в личку.

Отдельное пожелание от жюри конкурса: условие задачи не должно занимать более половины страницы А4. Если у жюри будут вопросы по содержанию, они зададут их вам лично : )

Привет!

Спасибо всем, кто уже прислал задачи! Ваши интересные легенды натолкнули нас на мысль открыть рубрику "цитаты из школьных сочинений задач". Лучшие, на наш взгляд, перлы:

• "Можно поставить большие ограничения так, чтобы оптимальный ответ не было сил найти"
• "И вот в городе Неизвестном прошла суровая зима и наступило прекрасное лето. (Да-да, сразу лето)"
• "Василий — курьер. Очень хороший курьер."
• "Василий нанял вас в качестве своего секретаря."
• "Мэр города долго закрывал на это глаза, но больше терпеть он не мог."
• "Пересекаться могут только трассы, состоящие из различного по чётности количества перекрестков."
• "У Умного Бобра во дворе растет красивая бинарная яблоня"
• "Затем он срывает яблоко (не меняя структуру дерева)"
• "Каждый день Умный Бобер выходит во двор и лезет на яблоню за ближайшим яблоком."
• "...выводим удвоенный (Бобру еще слезать надо) результат."

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

Так что присылайте свои идеи на [email protected] и не забывайте про описания решений.

Удачи и вдохновения!

ABBYY Cup 3.0 уже не за горами! И в рамках Cup’а мы решили провести конкурс задач по спортивному программированию для тех, кому по плечу не только решать задачи, но и придумывать их. Лучшие задачи попадут в ABBYY Cup 3.0, а их авторы получат призы и приглашение на День открытых дверей ABBYY!

Нам кажется, нет смысла рассказывать вам, какими должны быть олимпиадные задачи :) Напомним лишь формальные признаки, которые хотелось бы сохранить:

Можно добавить в примечании уровень сложности (easy, medium, hard), возможность модификации задачи и т.д. Помимо «классических» задач нам были бы интересны «эвристические» задачи. Примеры «эвристики» с ABBYY Cup 2.0 здесь.

Обязательное условие – задачи должны быть новыми, т.е. придуманные вами, а не найденные в глубинах интернета. От каждого участника принимается не более трёх задач. При условии, что хотя бы одна из ваших задач попадает на ABBYY Cup 3.0, вы получаете приглашение на День открытых дверей ABBYY. Если ваша задача не попадет на ABBYY Cup 3.0, мы обязуемся сохранить её в тайне, и вы сможете смело использовать ее в других контестах. Члены жюри конкурса не являются действующими участниками олимпиадного программирования и не заинтересованы в использовании задач, которые не попадут на Сup.

Задачи (в виде файла .pdf, .doc, .docx, .txt) принимаются с 8 по 21 апреля на адрес [email protected]. В теме письма укажите «Конкурс задач», а в самом письме – ФИО, название вашего вуза и факультета, а также курс или год выпуска (для школьников – школа, город, класс). Если у вас есть страница ВКонтакте и хендл на Codeforces (а он точно есть :)), TopCoder, их тоже желательно указать. Убедитесь, что вам пришел ответ с подтверждением о получении заявки!

Надеемся, что наш конкурс задач станет хорошей традицией, которая поможет в открытии новых талантов и сделает ABBYY Cup еще более интересным для участников!

День открытых дверей ABBYY назначен на 6 июля.

Мы уже набрали критическое количество заявок. Спасибо всем за теплые слова :) Если вы заполнили заявку, но не получили от меня письма с орг информацией, напишите мне в личку, пожалуйста. Если вдруг появятся свободные места (кто-то из тех, кто подал заявку, откажется), сразу же напишу здесь, чтобы у вас была возможность к нам приехать!

Друзья, ABBYY Cup 2.0 завершился!

Большое спасибо всем участникам! Мы надеемся, что вы получили удовольствие от решения задач обоих дивизионов! Особенно приятно видеть так много положительных отзывов об эвристической задаче :) Мы, в свою очередь, постараемся, чтобы в будущих наших Cup'ах было еще больше интересных задач!

Отдельное спасибо команде Codeforces: MikeMirzayanov, Gerald, Delinur и, конечно же, tourist! С вами было очень приятно и интересно работать :)

В прошлом году ABBYY Cup 1.0 приняло участие 186 человек, а в этом году в Easy дивизионе приняло участие 1213 человек, а Hard — 604!!! Благодаря контесту на Codeforces появилось 252 новых пользователя. Хочется надеяться, что ABBYY Cup немного приобщил их к олимпиадному программированию. Очень приятно, что 12 участников смогли зачесть себе результаты легкого дивизиона как вступительные экзамены на кафедры ABBYY в МФТИ.

Attention! Напоминаем, что всех участников мы приглашаем на День открытых дверей ABBYY. Огромная просьба всем, кто хочет приехать к нам, написать на [email protected] с контактной информацией о себе (фамилия, имя, handle, из какого вы города) и в какие даты летом (лучше несколько диапазонов дат в июне и в июле) вам удобнее приехать. В зависимости от количества желающих, мы решим, кому и в какой мере мы сможем помочь с организацией поездки (полная компенсация расходов, частичная и т.д.). Ждем ваших писем!

Еще раз всем спасибо! И до встречи в ABBYY :)

Разбор задач будет пополняться :)

Разбор задачи <<Развивающая игра>>

Это была самая простая задача из сложного набора. Для начала заметим, что можно решать данную задачу для каждого элемента a_i отдельно. То есть, если мы фиксируем некоторое k, то вклад каждого a_i в ответ можно считать отдельно.

Итак, фиксируем некоторое a_i. Найдем максимально возможное j такое, что i + 2^j ≤ n. Несложно видеть, что для всех k < i + 2^j вклад a_i в ответ будет равен a_i. То есть нужно будет сделать a_i ходов с переходом в a_i + 2^j. Далее найдем такое максимальное u, что 2^j + 2^u ≤ n. Заметим, что u < j. Также заметим, что для всех k таких, что i + 2^j ≤ k < i + 2^j + 2^u вклад a_i в ответ будет равен 2·a_i. Далее найдем такое q, что i + 2^j + 2^u + 2^q ≤ n.

Итак, для каждого элемента a_i мы должны найти соответствующую последовательность степеней двойки. Очевидно, что общая сложность этого процесса .

Теперь нам нужно считать ответ. Можно это делать, например, так: будем хранить массив b_i. b_i — это изменение ответа при переходе от i к i + 1. Этот массив строится тривиальным образом во время построения последовательностей степеней двоек. И потом по нему также нетрудно получить ответ. Итого, сложность решения составляет .

Разбор задачи “Жадные торговцы”

Для начала заметим, что торговцы будут платить только за те ребра, которые являются мостами (мостами называются рёбра неориентированного графа, при удалении которых количество компонент связности в графе увеличивается). Все другие ребра не подходят, так как при их удалении граф останется связным и путь между никакими двумя вершинами не исчезнет. Итак, первым этапом в решении является поиск мостов. Воспользуемся для этого известным алгоритмом, который работает за время O(n + m).

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

Заметим также, что число динариев, которое заплатит каждый из торговцев — это расстояние между некоторыми двумя вершинами в новом графе. Но так как этот граф является деревом, эти расстояния можно искать быстро, используя алгоритмы поиска LCA (наименьшего общего предка) для двух вершин. В данной задаче можно использовать один из самых простых алгоритмов поиска LCA, который осуществляет препроцессинг за время и обрабатывает один запрос за . Сложность такого решения составляет .

Отметим также, что решение можно несколько упростить. Построим дерево рекурсивного обхода исходного графа и назначим веса его ребрам. Вес, равный 1, будут иметь мосты, а все остальные ребра будут иметь вес, равный 0. Тогда после этих преобразований для нахождения ответа для одного торговца достаточно посчитать расстояние между двумя вершинами в построенном дереве рекурсивного обхода.

Разбор задачи <<Бобер и разрешение коллизий>>

Заметим, что при обходе ячеек с шагом m по модулю h множество ячеек хеш-таблицы разбивается на некоторое количество циклов, в каждом из которых одинаковое число элементов. При этом число циклов равно НОД(h, m), а число элементов в каждом из циклов -- h / НОД(h, m). Смысл циклов в том, что если объект имеет изначальное значение хэш-функции внутри одного цикла, то он будет добавлен в качестве элемента этого же цикла.

Теперь можно работать с каждым циклом отдельно. Нам необходимо эффективно добавлять/удалять элементы и при этом считать число коллизий. Для этого проще всего использовать для каждого цикла дерево отрезков или комбинацию из бинарного поиска и дерева Фенвика.

Cложность такого решения составляет для дерева отрезков или для бинарного поиска и дерева Фенвика. Заметим, что большой разницы в скорости работы этих решений нет за счет скрытых констант при подсчете сложности.

Разбор задачи <<Магические квадраты>>

Рассмотрим два подхода к решению данной задачи. Заметим, что для начала мы по исходным данным определяем значение s как сумму всех чисел, делённую на n. Далее будем пользоваться этим значением при решении.

Первый подход – переборный. Он основан на двух идеях:

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

Второй подход основан на дискретной оптимизации. Рассмотрим следующий функционал качества: Q = |sum₁ - s| + ... + |sum_t - s|, где |x| — абсолютная величина x, t = 2 * n + 2, sum₁, .., sum_n — суммы в строках квадрата, sum_n + 1, sum_2n — суммы в столбцах, sum_t - 1 — сумма элементов на главной диагонали, sum_t - 1 — сумма элементов на побочной диагонали. Итак, мы должны найти такую перестановку, которая минимизирует данный функционал. Можно это делать так: выберем случайную перестановку. Будем пытаться делать в ней инверсии, которые улучшают исходный функционал качества, 1000 раз. Если в итоге Q = 0 — мы нашли ответ, если Q > 0 -- возьмём другую перестановку и начнём сначала. Даже такой тривиальный алгоритм оптимизации в данной задаче работает хорошо и проходит все тесты с большим запасом по времени.

Разбор задачи <<Задача от бобра — 2>>

Решение данной задачи можно разделить на две части:

• Удаление шума на изображении;
• Классификация фигур.

Для удаления шума можно было воспользоваться следующими методами:

a. Делаем следующие операции: сканируем изображение и по нему строим новое. Если некоторый черный пиксель имеет белых соседей, то мы его делаем белым. За несколько таких проходов мы избавляемся от почти всего шума на фоне. Потом делаем обратную операцию по замене былых пикселей на черные. Таким образом мы избавляется от шума внутри фигур.

Заметим, что после всех таких операций может остаться шум (в виде маленьких компонент черного цвета) и некоторые фигуры могут утратить связность. Обе эти проблемы решаются несложно: удаляем маленькие компоненты черного цвета и потом объединяем близкие компоненты черного цвета.

b. Можно было поступить проще. Выделяем компоненты черного цвета и отбрасываем те, которые имеют малый размер. Если внимательно посмотреть на тесты, то в реальности при равномерном распределении шума не возникает больших шумовых компонент черного и не теряется связность фигур. Однако предыдущий подход является существенно более надежным.

Самый простой способ для классификации фигур — это сравнение распределений расстояний от всех пикселей фигуры до центра каждой из фигур. Центр можно вычислить как среднее арифметическое координат всех точек фигуры. Сравнивать у распределений можно выборочные мат. ожидания и дисперсии.

Задача <<Репрезентативная выборка>>

Сразу приступим к полному решению задачи. Давайте отсортируем строки лексикографически и посчитаем lcp[i] -- длину наибольшего общего префикса строк i и i + 1. Несложно доказать, что наибольший общий префикс любых двух строк i и j теперь равен min (lcp[i], lcp[i + 1], ..., lcp[j - 1]) (подобное утверждение используется при использовании суффиксного массива). Это полезно.

Теперь применим метод динамического программирования. Сделаем такое ДП: F(i, j, k) — максимальный возможный ответ на задачу, если из строк с номерами i... j нужно выбрать ровно k строк. Переход следующий: найдём позицию p на отрезке i... j - 1 с минимальным lcp[p], тогда F(i, j, k) = max_{q = 0... k}(F(i, p, q) + F(p + 1, j, k - q) + q·(k - q)·lcp[p]), то есть предполагаем, что выбрано q из строк из i... p, k - q строк из p + 1... j, и для всех пар этих строк длина наибольшего общего префикса равна lcp[p] (это следует из утверждения в первом абзаце).

Такое решение достаточно для получения 50 баллов. Пока что кажется, что сложность этого решения порядка O(N⁴). Осталось показать, что на самом деле можно реализовать это решение так, чтобы его сложность оказалась равна O(N²).

Для начала заметим, что различных отрезков i... j, на которых нас интересуют значения функции F, на самом деле ровно 2N - 1, а не O(N²). Почему это так, можно понять из переходов нашего ДП. Отрезок 1... N разбивается на два отрезка 1... p и p + 1... N, каждый из этих отрезков разбивается ещё на два отрезка, и так далее; видим, что между позициями i и i + 1 для любого i ровно один раз за весь подсчёт ДП произойдёт <<разрез>>, и этот разрез породит два новых отрезка, на которых нас интересуют значения ДП. Отсюда и получаем оценку в 2N - 1 нужных отрезков, следовательно, наше решение уже имеет сложность не более O(N³).

Последнее и самое сложное — догадаться, что решение выше может иметь сложность O(N²). Например, реализовать его можно так. Давайте заведём рекурсивную функцию F(i, j), возвращающую массив длины j - i + 2 — собственно значения ДП F(i, j, k) (понятно, что нас интересуют только значения k из отрезка от 0 до j - i + 1). Внутри этой функции делаем следующее: найдём p, вызовем F(i, p) и F(p + 1, j), теперь переберём x от 0 до p - i + 1, переберём y от 0 до j - p и обновим значение F(i, j, x + y), если оно улучшилось (подробнее можно увидеть в авторском решении, там всё довольно прозрачно). Максимальное время работы функции F, вызванной на отрезке i... j длины j - i + 1 = N, можно записать как T(N) = max_{X = 1..N - 1}(T(X) + T(N - X) + (X + 1)·(N - X + 1)). Осталось понять, что T(N) = O(N²). Это можно сделать, например, написав простое ДП для подсчёта T. Если подумать, то можно понять это так: когда мы в цикле перебираем x = 0... p - i + 1 и y = 0... j - p, давайте будем представлять, что мы перебираем как будто пару строк: x = i... p и y = p + 1... j (тут перебор по x и y проходит на одну итерацию меньше, но это не принципиально); тогда каждая пара строк за весь подсчёт ДП окажется перебрана ровно один раз, что и даёт нам итоговую сложность O(N²).

Вот здесь можно ознакомиться с авторским решением.

Многие участники сдавали решения, использующее бор. Такие решения также могут иметь сложность O(N²), однако работают дольше и используют намного больше памяти. Тем не менее, ограничения по времени и по памяти были достаточно лояльны к разным решениям :)

UPD: ABBYY Cup 2.0 завершился! Свежая информация!

UPD: Публикуем разбор :)

И снова привет!

Напоминаем, что сегодня в 16 часов состоится долгожданный сложный дивизион ABBYY Cup 2.0!

Задачи будут сложными для полного решения, рассчитанные на ребят из Див1 Codeforces. Для участия не забудьте зарегистрироваться на контест!

Правила не изменились: в течение 5 часов участники должны будут решить 6 задач (одна из них эвристическая). Тесты разбиты на три группы (легкая, средняя, сложная) стоимостью в 20, 30 и 50 баллов соответственно. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время. Контест будет рейтинговым для всех независимо от формы участия и рейтинга.

Всех участников мы ждем на Дне открытых дверей ABBYY, где расскажем о наших технологиях и вручим подарки. Лучшим поможем с организацией поездки, а также подарим ценные гаджеты.

Надеемся, решение задач принесет вам интеллектуальное удовольствие!

Удачи, и пусть победит сильнейший : )

UPD1: Задача <<Строки Фибоначчи>>

Выпишем, рекурентность для ответа.

Здесь ans(k, s_i) — количетство вхождений строки s_i в строку f_k, а cross(k, s_i) --- количество вхождений строки s_i в строку f_k таких, что они пересекают разрез на стыке f_k - 1 и f_k - 2.

Понятно, что значение cross(k, s_i) зависит, только лишь от некоторого суффикса f_k - 1 и некотрого префикса f_k - 2. А именно, длина этих префиксов/суффиксов должна быть не менее длины s_i.

Если посмотреть на префиксы/суффиксы строк f_i фиксированной длины L, то можно заметить, что начиная с некоторого момента префиксы начинают повторяться, а суффиксы чередоваться.

Этих фактов уже достаточно для решения задачи. Сгенерируем строку Фибоначчи f_j, такую, что |f_j| > |s_i|, а также строку f_j + 1. Утверждается, что начиная со стороки f_j + 2 префиксы стабилизируются, а суффиксы чередуются: суффикс f_j, суффикс f_j + 1, суффикс f_j, и так далее. Это означает, что для всех k > j + 1 значения cross(k, s_i) также будет чередоваться.

Посчитаем два значения cross(j + 2, s_i) и cross(j + 3, s_i). Далее нужно вычислить рекурентность.

Чтобы сдать задачу на 30 баллов, было достаточно циклом посчитать рекуррентность.

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

Итак, второй дивизион ABBYY Cup 2.0 завершился!

Всем спасибо за участие! Хороших выходных :)

UPD: Друзья, а вот и долгожданный разбор!

Задача <<Хорошие элементы матрицы>>

Это была самая простая из задач, предложенных на ABBYY Cup’е. В ней просто требовалось посчитать сумму некоторых элементов матрицы. Ограничения позволяли использовать для хранения суммы обычные целочисленные типы для хранения суммы. Проверка принадлежности элемента к <<средней>> строке или <<среднему>> столбцу является тривиальнойым. Принадлежность элемента (i, j) матрицы к главной диагонали проверяется как i = j, а к побочной: i = n-j+1. Итоговая сложность решения составляет O(N²).

Задача “Прямоугольная игра”

Немного переформулируем исходную задачу: дано число N, и нужно найти цепочку с максимальной суммой. Цепочкой будем называть такую последовательность чисел, что:

• A₁ = N, A_k = 1
• A_i делится нацело на A_i + 1 для i от 1 до k - 1

Для решения будем использовать жадный алгоритм. Мы знаем, что A₁ = N. После этого выбираем максимально возможное подходящее значение для A₂. Далее аналогично для A₃ и так далее, пока не получим 1. Доказательство корректности данного подхода основано на единственности разложения любого числа на простые множители. Для эффективной реализации можно было факторизовать исходное число N. И потом просто каждый раз делить его на минимально возможный простой множитель. Итоговая сложность решения составляет .

Задача <<Вечеринка>>

Заметим, что если некоторый человек идет на вечеринку, то на нее также идут все люди, которые находятся с ним в одной связной компоненте по ребрам дружбы. Также отметим, что на вечеринке может присутствовать ровно одна такая связная компонента. Если же внутри некоторой связной <<дружной>> компоненты есть ребра антипатии, то такая компонента не может образовывать дружную вечеринку. Итого, решение следующее: выделяем все связные <<дружные>> компоненты. Выбираем из них максимальную и не содержащую ребер антипатии. Для выделения компонент связности можно было пользоваться поиском в ширину или поиском в глубину. Итоговая сложность решения составляет O(n + k + m). Возможен альтернативный вариант за O(n²), если использовать для хранения графа матрицу смежности.

Задача <<Шифрование сообщений>>

Заметим, что каждый элемент A_i модифицируется следующим образом: к нему прибавляются некоторые элементы B_i. Причем прибавляется некоторый интервал, то есть элементы B_i такие, что L(i)≤i≤R(i). Итак, мы свели задачу к двум подзадачам:

1. Определение значений L(i) и R(i) для некоторого индекса i. Приведем вариант формул для определения этих величин: R(i) = min(m, i) L(i) = max(1, i - (n - m)), где n – длина массива A_i, m – длина массива B_i, i от 1 до n.

2. Обоснование правильности этих формул оставляем читателю в качестве упражнения. Быстрый подсчет суммы элементов B_i в интервале от L(i) до R(i). Перед построением ответа вычислим следующую величину: S(i) = сумма элементов Bi от 1 до i. Пусть S(0) = 0. Тогда S(i) = S(i–1) + B_i. А сумма в интервале от L(i) до R(i) будет равна S(R(i)) - S(L(i) - 1). Итоговая сложность решения составляет O(n + m).

Разборы других задач давно готовы, но маркап сегодня не дает нормального превью формул :(

Надеюсь, MikeMirzayanov поможет!

Всем привет!

Друзья, напоминаем, что сегодня в 18 часов состоится второй дивизион ABBYY Cup 2.0!

Всех участников ждет подарок: помимо задачек от Умного Бобра будет специальная задача от проекта Codeforces!

Длительность контеста не изменилась, за четыре часа участникам предстоит решить 7 задач. Тесты разбиты на две группы стоимостью в 30 и 70 баллов соответственно. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время.

Ну и как писал MikeMirzayanov:

Простой контест будет рейтинговым для участников из Див 2 (независимо от того студенты они или нет). То есть рейтинг будет пересчитан для всех официальных участников простого контеста + участников из Див 2, кто вне конкурса.

Не забудьте, что легкий дивизион ABBYY Cup 2.0 предназначен, главным образом, для ребят из Див 2 Codeforces и тех, кто имеет небольшой опыт спортивного программирования. Ребята из первого дивизиона Codeforces могут участвовать во втором дивизионе вне конкурса.

Желаем всем весеннего настроения и бодрого духа! Отдельно хочется пожелать удачи всем, кто будет участвовать в контесте в первый раз в жизни! А таких, судя по зарегистрированным, будет немало. С дебютом, друзья :)

Всем удачи!

Всем привет!

Друзья, надеемся, вы уже определились со своими планами на ближайшие субботние вечера. Тем из вас, кто готов провести их в компании Умного Бобра, сообщаем, что регистрация на ABBYY Cup 2.0 открыта! А для школьников и выпускников (в том числе аспирантов), участвующих вне конкурса, мы сделали отдельные чекбоксы :)

Как написал MikeMirzayanov:

Простой контест будет рейтинговым для участников из Див 2 (независимо от того студенты они или нет). То есть рейтинг будет пересчитан для всех официальных участников простого контеста + участников из Див 2, кто вне конкурса. Сложный контест будет рейтинговым для всех участников, независимо от формы участия и рейтинга.

Регистрация обязательна для всех студентов-участников и для всех, кто участвует вне контеста, но желает зачесть результаты при трудоустройстве в ABBYY. Во всех остальных случаях (при наличии хендла на Codeforces) регистрироваться необязательно.

Компания ABBYY, ведущий мировой разработчик в области программного обеспечения и поставщик услуг в области распознавания и ввода документов, совместно с проектом Codeforces и Саратовским государственным университетом проводит студенческую online-олимпиаду ABBYY Cup. Мы постарались учесть пожелания участников прошлой олимпиады, и в этом году контест будет состоять из двух дивизионов.

Если вы из второго дивизиона Codeforces, то есть вы никогда не участвовали в олимпиадах по программированию или имеете небольшой опыт участия, то вам правильнее подать заявку во второй (легкий) дивизион ABBYY Cup. Задачи в этом дивизионе будут даже легче, чем на ABBYY Cup 1.0. Первый (сложный) дивизион будет интересен, в первую очередь, участникам первого дивизиона Codeforсes – ребятам со значительным опытом спортивного программирования.

Мы благодарим Гену Короткевича tourist за участие в подготовке пакета задач.

Подробности

В каждом из дивизионов будет 6 задач, каждая стоимостью в 100 баллов. Официальные языки соревнования – C/C++, Pascal, C# и Java. Задачи можно сдавать на всех языках, поддерживаемых на Codeforces, но жюри не гарантирует существования полных решений на всех языках из этого списка. Засчитывается только полное прохождение группы тестов. При равенстве баллов штрафное время учитывается по правилам ACM. Полное решение какой-либо группы тестов засчитывается за сданную ACM-задачу, и в соответствии с этим вы будете получать штрафное время.

Соревнования второго дивизиона начнутся 21 апреля, в субботу, 18:00. Длительность – 4 часа. Тесты разбиты на две группы (легкую и сложную) стоимостью в 30 и 70 баллов соответственно. В этих соревнованиях официально смогут принять участие те, кто находится во втором дивизионе Codeforces. Ребята из первого дивизиона Codeforces могут участвовать во втором дивизионе вне конкурса.

Соревнования первого дивизиона начнутся 28 апреля, в субботу, 16:00. Длительность – 5 часов (задачи того стоят :)). Тесты разбиты на три группы (легкая, средняя, сложная) стоимостью в 20, 30 и 50 баллов соответственно. В этих соревнованиях могут принять участие все, независимо от рейтинга.

Регистрация откроется 16 апреля на официальной странице ABBYY Cup!

Результаты контестов могут быть зачтены как первый этап собеседования при трудоустройстве в ABBYY или при поступлении на базовые кафедры ABBYY в МФТИ.

Награждение

Всех участников мы приглашаем на День открытых дверей ABBYY, где расскажем о наших технологиях и вручим подарки. Победители сложного дивизиона получат ценные гаджеты, а также компенсацию затрат на дорогу в столицу и обратно. Дата мероприятия будет анонсирована позднее. О том, как прошел День открытых дверей ABBYY для победителей ABBYY Cup 1.0, читайте на странице олимпиады и в блоге участника и победителя Alex_KPR.

До встречи в ABBYY!