When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

By ruzana.miniakhmetova, 11 years ago, translation, In English

Hi everyone!

For three years ABBYY Cup finalists have been meeting for ABBYY Open Day at the ABBYY Moscow office (Headquarters) in summer. This year hasn’t been an exception. As an organizer I will tell you about ABBYY Open Day 2013 which took place on July 17th.

It should be noted that it was rainy all the days before the contest day. We were very concerned: we have announced the entertainment which was strongly depending on the weather. Evidently the Universe wanted to see the outdoor part of the Open Day and decided not to spoil the weather by rain. The day began with breakfast and watching a funny video with a promising name “The truth about ABBYY”.

At 10:40 AM the contest started. For me as an organizer this is nice time. There is silence in the room, participants solve problems, I can relax for a moment watching the results and rooting for my favorites. In two hours we got the final standings. In particular, I want to congratulate with great results Mimino, who was the only non-speaking Russian participant. Every ABBYY Open Day cannot take place without the talk about the company. So, after dinner the participants met the CEO of ABBYY Sergey Andreev. Then our technical consultant for Compreno products Alexander Kostuchenko demonstrated achievements of ABBYY R&D in computer linguistics.

We’ve had a tour on the office where the participants managed to see how the working process of programmers is organized. At the end of the official part we’ve had the most pleasant event, the awarding. This year all the winners could get the gift from Smart Beaver himself, the main character of all ABBYY Cup problems. Next the unofficial part of the day began. It was the quest in the centre of Moscow. All the participants divided in teams, got the rules and the tasks and scattered throughout Moscow. In order to find the finish line the teams should have answered all the questions about Moscow sights or they could drop the quest at any time by calling us. However, nobody wanted to give up. Imagine how hard these tasks were for Mimino. We translated the rules especially for him and provided a translator to his team.

At 10 PM the teams started to gather at the finish in one of the Moscow’s anticafe. We have been waiting for them with pizza, salads and Smart Beaver! Our ABBYY Open Day has ended. We are very happy that there are participants who visit us every year. And this year we have had one international participant. It was nice to meet everyone. See you next year!

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

Full text and comments »

  • Vote: I like it
  • +166
  • Vote: I do not like it

By ruzana.miniakhmetova, 11 years ago, translation, In English

UPD2: Dear all!

As promised, we invite ABBYY Cup 3.0 online part 25 best participants to ABBYY Open Day which takes place on the 17th of July at ABBYY Headquarters. So the onsite will be held at ABBYY Open Day.

If you want to visit us, please, mail to [email protected] in the next 5 days. Remind you that we'll privide you by food, lodging and help with transfer and visa. Transportations costs are on you.

UPD1: Solutions!

UPD: Dear all, ABBYY Cup 3.0 online part will take place today!

Some notes:

  • The constest will be rated for all participants but programming problem contest winners.
  • Programming problem contest winners may register and take part in beyound the rating.
  • Our jury dicided to add 7th problem of their authorship.

    Good luck at the constest!

    Hi everyone!

    We are happy to announce ABBYY Cup 3.0, the long-expected programming contest! As promised, this year’s participants are to be given the tasks which won our programming problem contest.

    ABBYY Cup 3.0 has two parts, an online and onsite one. The first part is starting very soon – Wednesday, June 12, 17:00-21:00 Moscow time.

    We would like to give our personal thanks to Codeforces project team, especially to MikeMirzayanov and Gerald, for their help in running contests. And many-many thanks to all of you who participated there! Dear winners, please don’t get surprised that you can’t recognize the tasks you once sent to us, simply because they could easily be reserved for the onsite part and also because we could modify them seriously.

    The details

    The online round includes 6 tasks, 100 points each. All these tasks are divided in test sets and arranged either in two or three groups according to complexity level and point value. The first scheme implies there are an “easy” group and a “difficult” group of 30 and 70 points respectively. Another scheme provides three groups (ranked as “easy”, “medium” and “difficult”) of 20, 30 and 50 points per each. To add, we have a surprise in stock for you and this is a marvelous heuristic task!

    Official contest languages are C/C++, Pascal, C# and Java. You can program the tasks in any language supported by Codeforces, however the jury has no guarantee that complete solutions do exist for all the languages enlisted. Passing the whole chain of tests is necessary. When points are equal, time penalty is used according to ACM rules. Any fully completed test set means a fully completed ACM-task and is a signal flag to set time penalty for other contestants. Besides this year all participants will be in rating. Registration for ABBYY Cup 3.0 opens 12 hours before the start of the contest and closes when the contest is over. Just a brief reminder: winners of April tasks contest can take part in this one but won’t fight for ratings.

    What’s then?

    According to the online round’s results, 25 best participants are to meet in ABBYY Cup final, July 17, which takes place in company’s Moscow office along with ABBYY Open Day event. Food and lodging will be provided by ABBYY, travelling costs compensation will be dicussed individually.

    Good luck!

  • Full text and comments »

    Announcement of ABBYY Cup 3.0
    Announcement of ABBYY Cup 3.0 - Finals
    By ruzana.miniakhmetova, 11 years ago, translation, In English

    Hi everyone!

    ABBYY’s first programming problem contest is over. Many thanks to all the participants! The winners will be announced in two weeks time. As of now, there are some statistics:

  • We have received 78 problems from 45 authors.
  • 21 authors sent us one problem a head, 15 authors sent two problems each, and 3 problems at a time were sent by other 9 authors .
  • As for the age of the participants, there were 23 students, 18 pupils and 4 graduates.
  • Geography of the contest: most of the authors (23 people) are from Russia. Then comes Ukraine (6), Kazakhstan (4), and Byelorussia (3). Armenia, Bangladesh, Great Britain, Georgia, Cuba, Iran, the USA, Uruguay and South Korea had one representative each.
  • Grading: 2 international Grandmasters, 8 international Masters, 11 Master’s candidates, 12 experts and 7 specialists. Others are not included in the rating list.
  • Over the last weekends we received as many problems in total as during the previous two weeks.
  • As you can see, this contest has been a pilot one and mostly an experiment. Again, many thanks to all who joined in! We are very happy and proud to receive so many problems from you!

    Full text and comments »

    • Vote: I like it
    • +114
    • Vote: I do not like it

    By ruzana.miniakhmetova, 11 years ago, In Russian

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

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

  • “Валера очень трудолюбивый мальчик, и поэтому он хочет добыть как можно больше бревен.”
  • “Вывод; … EPIC FAIL если отель слишком забит.”
  • “В далеком, далеком царстве бюрократия дошла до того, что теперь бобры обязаны получать разрешение на строительство плотины.”
  • “Как цивилизованные звери бобры заходят в кабинет по одному в порядке живой очереди.”
  • “Complexity: (quite) hard”.
  • “Гениальный биолог — бобровед Карловице Линневич на закате жизни открыл закон, по которому размножаются бобры. Его хобби его же и погубило.”
  • “Это утверждение может помочь при оценке численности бобров, что крайней необходимо ученым в Канаде… популяция будет расти невиданными темпами.”
  • “This problem is inspired by an episode of Futurama….”
  • “Мало кто знает, но у Умного Бобра (Феди) есть брат близнец — Злой Бобер (Виктор). Виктор большой фанат фильмов про злодеев. И на свое день рождение он решил устроить сюрприз для Феди. Виктор хочет, чтобы праздник прошел по сценарию его любимого фильма «Бобры не добры».”
  • “В фильме «Бобры не добры» неудачливого злодея придавило камнем, отколовшимся от потолка, после чего гости решили сбежать, но вместо этого Виктор просто пошел смотреть свой любимый фильм…”
  • “Существует некая квадратная матрица, в эту матрицу проникают «враги» (например: вирусы/бактерии/чума/эпидемия/захватчики одно из них).”
  • “За одну единицу времени (секунду, минуту, месяц, год, век и т.п.)”
  • Спасибо всем авторам за задачи и хорошее настроение, которое вы нам дарите!

    Full text and comments »

    By ruzana.miniakhmetova, 11 years ago, In Russian

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

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

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

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

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

  • строгий формат ввода/вывода, иногда даже с точностью до пробелов и переводов строк;
  • условия, как правило, имеют строгую однозначную трактовку. Вот уж где можно поучиться заказчикам в написании ТЗ!
  • строгие ограничения по времени выполнения и используемой памяти. В реальной разработке вам скорее скажут что-то в стиле «хотим, чтобы работало на таком-то железе и на такой-то ОС» или «слушай, твоя программа ест слишком много памяти». Куда реже можно услышать фразы типа «твоя программа должна работать не более 1,5 секунд» или «не смей использовать более 64 мегабайт памяти»;
  • все исходные величины строго ограничены.
  • Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.

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

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

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

  • задача считается решенной, если решение участника правильно сработало на всех тестах. Такая система оценки используется на ACM-соревнованиях.
  • за решение начисляются баллы, которые зависят от количества тестов, успешно пройденных программой. Такой подход часто используется на школьных олимпиадах: никто не уйдет обиженным с соревнования и получит хотя бы свои 0,5 балла.
  • тесты объединены в группы, за каждую из которых начисляется определенное количество баллов. Нужно заметить, что баллы за группу начисляются, только если решение правильно сработало на всех тестах из группы. Это разумный компромисс между справедливостью и удовлетворением участников. ABBYY Cup исповедует именно такую форму оценки решений;
  • иногда число баллов, полученных участником, зависит от времени, которое было затрачено на решение задачи. Например, такая система используется на Codeforces и Topcoder.
  • Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

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

    Full text and comments »

    By ruzana.miniakhmetova, 11 years ago, In Russian

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

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

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

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

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

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

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

    Full text and comments »

    By ruzana.miniakhmetova, 11 years ago, In Russian

    Привет!

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

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

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

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

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

    Full text and comments »

    By ruzana.miniakhmetova, 11 years ago, translation, In English

    ABBYY Cup 3.0 is coming! Within the Cup we announce the programming problem contest. Best problems will go to ABBYY Cup 3.0 and best authors will win prizes!

    A problem should include:

  • description;
  • input/output example;
  • brief description of solution.
  • You can also add a complexity level (easy, medium, hard) and your ideas about modifications. We are interested in "heuristic" problems besides "classic". An example of a heuristic problem from the ABBYY Cup 2.0 is here.

    All problems must be new i.e. invented by you. Every contestant can send no more than three problems. If your problem does not go to ABBYY Cup 3.0, we promise to keep it in secret. Jury members are no longer participants of programming contests and they are not interested in using your problems apart from ABBYY Cup.

    Please send your problems in .pdf, .doc, .docx, or .txt format to [email protected] with subject "ABBYY problem contest". Problems are accepted from 8 to 21 April. Write your name, surname, school and graduation year. It is desirable to write your Codeforces handle. Be sure that you receive the answer which confirms receiving your email!

    We hope that our problem contest will be held every year and will help to find new talants and make ABBYY Cup more interesring for contestants!

    Full text and comments »