Олимпиада по программированию:
разбираем задачу, выбираем подход и язык для решения
Олимпиадные задачи делятся на классические и конструктивные. Классические задачи составляют по темам: динамическое программирование, алгоритмы на графах или на строках, теоретико-числовые алгоритмы и подобные, поэтому для решения необходимо свести задачу к известному алгоритму. Решение конструктивных задач не сводится к написанию общеизвестного алгоритма – его нужно «увидеть»
Решение олимпиадной задачи
Разберем классическую задачу 1 на алгоритмы вместе с Андреем Лозицким, преподавателем курса «Олимпиадное программирование» Школы CODDY.
Условие задачи
- Ограничение по времени на тест – 2 секунды.
- Ограничение по памяти на тест – 256 мегабайт.
- Ввод – стандартный ввод.
- Вывод – стандартный вывод.
Вы – опытный участник соревнований Codeforces. Недавно вы обнаружили, что за все время своего участия в раундах Codeforces успели сделать y попыток, из которых x были успешными.
| Многие работодатели предлагают на собеседованиях решать именно алгоритмические задачи |
Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x / y .
Ваше любимое рациональное число в диапазоне [0;1] – это p / q .
Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать долю успешных попыток равной p / q ?
Первая строка содержит одно целое число t ( l
Каждая из следующих t строк содержит четыре целых числа x , y , p и q ( 0 0 ; q > 0 ).
Гарантируется, что p / q – несократимая дробь.
Для каждого теста выведите одно целое число – минимальное количество попыток, которое вам придется сделать, чтобы ваша доля успешных попыток стала равна вашему любимому рациональному числу, либо минус 1, если добиться желаемого невозможно.
| Входные данные | Выходные данные |
| 4 | 4 |
| 3 10 1 1 | 10 |
| 7 14 3 8 | 0 |
| 20 70 2 7 | -1 |
| 5 6 1 1 |
Обычно условие задачи написано в виде жизненной истории, потому что писать четкую математическую формулировку не принято. Поэтому сначала выделите математическую формулировку задачи. Затем разберитесь с примерами к ней.
- В первом тесте нужно совершить 4 удачные попытки, тогда доля успешных попыток будет 7/14 или 1/2.
- Во втором тесте – 2 удачные и 8 провальных попыток, тогда доля успешных попыток будет 9/24 или 3/8.
- В третьем тесте доля успешных попыток уже равна 2/7.
- В четвертом тесте доли успешных попыток 1/1 нельзя добиться ни при каких условиях.
Затем посмотрите на ограничения, которые написаны в условии задачи: программа должна работать не более 2 секунд и использовать не более 256 Мб памяти.
Все данные ограничены числом 10 9 . Также определитесь, на каком языке станете писать решение и какова будет сложность алгоритма.
Сложность алгоритма – зависимость объема работы, которая выполняется алгоритмом от размера входных данных. Обозначается O ( f ( n )).
Например, если сложность алгоритма будет O ( n 2 ), а входные данные примерно равны 10 9 , то решение не сможет пройти такой тест. Алгоритму потребуется примерно 10 18 операций, а самый быстрый язык программирования может выполнять максимум 10 9 операций в секунду. Поэтому сложность алгоритма должна зависеть от другой функции, которая растет медленнее, чем f ( n ) = n 2 .
Еще обращайте внимание на ввод/вывод данных. Программа должна выдавать такой же результат, как и в примере, с точностью до пробелов и перевода строк.
Также смотрите, какой ввод/вывод нужен: стандартный или файловый. При стандартном вводе/выводе программа должна вывести результат на экран, а при файловом – записать его в текстовый файл.
Решение
Исходно мы имеем x успешных и ( y – x ) неуспешных попыток. Так как p / q – несократимая дробь, то в конце мы должны иметь p * r успешных и ( q * r – p * r ) неуспешных попыток, где r – некоторое натуральное число.
Понятно, что количество успешных и неуспешных попыток может только увеличиваться, тогда в конечном счете должны быть верны неравенства p * r >= x и q * r – p * r >= y – x .
Заметим, что правая часть неравенств всегда остается постоянной, а левая часть растет при возрастании t . Следовательно, если эти неравенства будут верны при каком-нибудь r , то они будут так же верны при более больших r .
Так как по условию задачи нам нужно найти минимальное количество попыток, при котором доля успешных попыток станет равной p / q , то нам нужно найти минимальное r , при котором равенства станут верными, а ответом на задачу будет q * r – y .
Искать r можно разными способами:
- Подставлять поочередно числа из отрезка [1;10 9 ]. Сложность алгоритма будет O ( n * t ). Но тогда для самого худшего случая потребуется сделать 10 12 операций за 2 секунды. На это не способен ни один язык программирования.
- Использовать бинарный поиск на отрезке [1;10 9 ]. Тогда сложность алгоритма будет O ( log ( n )* t ), и нам потребуется в самом худшем случае совершить примерно 30 000 операций за 2 секунды. На это уже способен любой язык программирования.
- Решить эффективнее: неравенства p*r >= x и q*r – p*r> = y – x решаемы. Из первого неравенства получаем, что r >= x / p , из второго: r >= ( y – x )/( q – p ). Для того чтобы оба неравенства выполнялись, r должно удовлетворять условию r >= max (( x / p ); ( y – x )/( q – p )). Минимальное r ищется из соотношения max (( x / p ); ( y – x )/( q – p )) с округлением вверх. Нужно учесть два частных случая, когда q и p равны 1 и 1 или 0 и 1. В этом случае нужно вывести минус 1. Данное решение является самым эффективным – оно не зависит от входных параметров. Сложность таких алгоритмов обозначается O (1).
Код решения с линейным поиском
#include using namespace std; bool neravenstvo(long long x, long long y, long long p, long long q, long long r) < return (p*r >= x) && (q*r - p*r >= y - x); > int main() < long long x, y, p, q, t; cin >> t; for(int i = 0; i < t; ++i) < cin >> x >> y >> p >> q; if(!neravenstvo(x, y, p, q, 1e9)) < cout for(long long r = 1; r > > >Код решения с бинарным поиском
#include using namespace std; bool neravenstvo(long long x, long long y, long long p, long long q, long long r) < return p * r >= x && q * r - p * r >= y - x; > int main() < int t; cin >> t; for(int i = 0; i < t; ++i) < long long x, y, p, q; cin >> x >> y >> p >> q; long long l = -1; long long r = 1e9; if (!neravenstvo(x, y, p, q, r)) < cout while (r - l > 1) < ll m = (l + r) / 2; if (neravenstvo(x, y, p, q, m)) < r = m; >else < l = m; >> cin return 0; >Код решения с формулой
#include using namespace std; int main() < int t; cin >> t; for(int i = 0; i < t; ++i)< int x, y, p, q; cin >> x >> y >> p >> q; if (p == 0) < cout if (p == q) < cout int r1 = (x + p - 1) / p; int r2 = ((y - x) + (q - p) - 1) / (q - p); cout >Язык для решения задач
После того как придумали решение задачи, определитесь с языком программирования. Далеко не на каждой олимпиаде разрешают выбрать любой язык. Самые популярные – Python, C++, C#, Java, Pascal.
Лучше освоить как минимум два языка программирования, так как бывают задачки, в которых решение простое, но громоздкое, поэтому требуется язык, на котором быстро пишут.
Бывают, наоборот, ресурсоемкие задачи, для решения которых необходимо придумать оптимальный алгоритм, имеющий наименьшую сложность, и использовать быстродействующий язык.
В первом случае лучше использовать Python, во втором – C++. Python – один из самых простых языков, но он довольно медленный. В зависимости от задачи Python работает в 100, а то и в 1000 раз медленнее, чем С++. Наоборот, С++ – один из самых быстрых языков программирования, но при написании кода можно наделать ошибок, на исправление которых уйдет времени больше, чем на подготовку самого решения.
Основная проблема не в том, что для работы на языке С++ необходимо быть аккуратным: после каждой команды ставить «;», объявлять тип переменной, ставить фигурные скобки. Проблема в том, что если программист допустил ошибку в алгоритме, например в результате работы программы он выходит за пределы массива, то Python сообщит об этом, а С++ – нет.
Тренировки перед олимпиадами
Чтобы научиться решать олимпиадные задачи, нужно много практиковаться. Для самостоятельного изучения теории советуем книги Томаса Кормена «Алгоритмы. Построение и анализ» и Дональда Кнута «Искусство программирования» в четырех томах. Подробный справочник по алгоритмам также есть на сайте MAXimal (http://e-maxx.ru). Там разобраны алгоритмы на языке С++, которые применяют на олимпиадах.
Для практики рекомендуем ресурсы с архивами олимпиадных задач: HackerRank (https://www.hackerrank.com), AtCoder (http://atcoder.jp), Codeforces (http://codeforces.com). На этих сайтах вы сможете решать задачи, сразу тестировать их и изучать подробные разборы. Также каждую неделю проходят тренировочные соревнования. Чтобы принять участие, необходимо только зарегистрироваться.
Участие в олимпиадах помогает не только обзавестись полезными знакомствами и с пользой провести время, но и устроиться в ведущие ИТ-компании. Многие работодатели предлагают на собеседованиях решать именно алгоритмические задачи.
Чтобы натренироваться, участвуйте в олимпиадах Яндекс.Алгоритм, Google Code Jam, Facebook Hacker Jam и подобных. Призеры и победители получают ценные призы, а участников с интересными решениями приглашают на работу.
1 Задача из третьего раунда Олимпиады VK CUP 2017 – Международного чемпионата по программированию для участников от 14 до 23 лет.
Как решать олимпиадные задачи по программированию?
Пытаюсь решать олимпиадные задачи по программированию и столкнулся с тем, что не понимаю как это правильно делать.
Обычно они делятся на два типа — первые, те, которые я прямо сразу знаю как решать. И тут все решение — просто начинаю писать код, отлаживать и т.д., никаких проблем.
А вторые — те, для которых или не знаю решения или даже условие сходу не понимаю. (уровень сложных на hackerrank или F,G на codeforces) Как решать такие «правильно»? Правильно — в смысле, чтобы улучшать не только скилл кодирования, но и какую-то теоретическую часть?
Имеет ли смысл сначала попытаться придумать решение самому или сразу гуглить теорию?
Если гуглить не сразу, то через какое время (сколько попыток решения)?
- Вопрос задан более трёх лет назад
- 6115 просмотров
1 комментарий
Оценить 1 комментарий
Как эффективно подготовиться к олимпиадам по программированию?
Скоро стартует вторая олимпиада Типичного программиста, и мы решили спросить у экспертов, как можно успешно к подготовится к подобным соревнованиям.
Как эффективно подготовиться к олимпиадам по программированию?
Михаил Рубинчик
менеджер Образовательные программы СКБ Контур, тренер команд УрФУ по спортивному программированию
Сейчас проводится много разных олимпиад по информатике и программированию. В России самую долгую историю имеют олимпиады по правилам ACM ICPC, а также довольно похожие на них олимпиады школьников. В целом они по подготовке очень похожи (хотя немного отличаются тактиками).
Мы будем говорить про ACM ICPC, т.к. для таких олимпиад есть множество готовых рецептов. Прежде всего, нужно научиться решать задачи. Как ни странно, чтобы научиться решать задачи, нужно решать задачи ? Поэтому самый верный путь для новичка такой: открываешь любой архив задач и решаешь по возрастанию сложности. Если вдруг какая-то задача уж очень долго не поддаётся, пропускаешь её и решаешь следующую. Если слишком много задач пропущены, то стоит посоветоваться с более опытным олимпиадником, нет ли там какого-то сакрального знания. Прорешивание архива задач — это самый важный на старте процесс. Например, можно использовать acm.timus.ru. А далее постепенно добавлять другие элементы: чтение книг и сайтов по алгоритмам (например, e-maxx.ru), участие в онлайн соревнованиях (codeforces.ru, opencup.ru).
Рейтинг полезности ответа:
Артём Зюрюкин
генеральный директор Zartis Russia
Можно поучаствовать в семинарах при университете, проводящем олимпиаду, а также найти тех, кто уже участвовал. Если вы планируете принять участие в международной олимпиаде (например, крупнейшей в мире ACM/ICPC), то найти тестовые задания и материалы для подготовки можно и на сайте самой олимпиады. Кроме того, полезным будет обсудить сложности с участниками сообществ выбранных олимпиад в социальных сетях.
Рейтинг полезности ответа:
Андрей Зырянов
руководитель научно-исследовательской лаборатории Parallels Lab в МФТИ
Олимпиады бывают разные. Отсюда и требования разные. Если «классические», как ACM ICPC, то вам нужно начать решать задачи на acm.mipt.ru и judge.mipt.ru. Если по информационной безопасности (Capture The Flag) — изучать архитектуру ЭВМ, криптографию и сетевые протоколы. По разработке ПО (DevCup, ImagineCup, «Старт в науку») — изучать ООП и работать в команде над небольшими проектами. Залог эффективности — трудолюбие. Этим нужно заниматься, причем постоянно. Если нет прогресса в самостоятельном изучении, потребуется помощь преподавателей.
Рейтинг полезности ответа:
Роман Юферев
руководитель направления ИТ-менеджмента и мониторинга в компании VIAcode
Ходить на эти самые олимпиады. Смотреть задачи. Осознавать, что ничего не понимаешь и разбираться. Идти на следующую олимпиаду. Вот такая вот «многоходовочка».
Рейтинг полезности ответа:
Сергей Масягин
проректор по работе со студентами и абитуриентами Университета Иннополис
Для ответа на этот вопрос мы опросили чемпионов мира по программированию Николая Калинина, Геннадия Короткевича, Нияза Нигматуллина, Андрея Станкевича и Павла Маврина, которые сейчас тренируют новое поколение. Все они сходятся во мнении, что главное в этом вопросе — много практики. Обратите внимание на codeforces.ru, topcoder.com — периодически там бывают контесты, после которых на сайтах появляются разборы к ним. Также рекомендую к прочтению Programming Challenges, Miguel Skiena. Есть множество ресурсов, где можно найти теорию, таких как e-maxx.ru, habrahabr.ru.
Рейтинг полезности ответа:
Антон Пискунов
основатель и генеральный директор BeastGaming
Никогда в них не участвовал и не могу ничего конкретного посоветовать. Но на мой взгляд вам потребуется просто достаточно хорошо изучить опыт предыдущих участников, созвониться или списаться с ними и попросить рассказать как было в прошлый раз. А уже на основе полученного опыта строить роадмап подготовки.
Рейтинг полезности ответа:
Сергей Зефиров
программист с широким опытом работы, энтузиаст и евангелист языка Haskell
Не готовиться к олимпиадам по программированию. Совсем.
Олимпиадное программирование применяет совершенно другие приёмы, чем программирование длительных проектов, которые только и встречаются в обычной жизни.
Готовясь к олимпиадам, вы наработаете себе стиль и подход к программированию, который придётся довольно долго исправлять.
Рейтинг полезности ответа:
Всеволод Шмыров
разработчик в команде API Яндекс.Карт
Для успешного развития нужно постоянно решать различные практические задания. Придумывать мелкие проекты и реализовывать их.
Рейтинг полезности ответа:
Олег Горшков
руководитель отдела системной интеграции ecommerce-студии Simtech Development
Здесь нет волшебных способов или специальных фокусов. Чтобы показать отличный результат на олимпиаде, прежде всего, нужно знать дисциплину. То есть тот язык, на котором вы программируете. Поставьте цель и упорно к ней идите. Набивайте руку на программировании и более глубоком изучении языка. Очень хорошо помогает прорешивание задач, которые были в прошлые годы и на других олимпиадах. Усложняйте их, придумавайте подобные и реализовывайте.
Также обращайте внимание на то, кто разрабатывает задания и судит вашу номинацию. От этого зависит из какой сферы будет задача. Как правило, они все берутся из реальных проектов и адаптируются под условия олимпиады.
Как решать олимпиадные задачи по программированию
- Главная
- Топ
- Каталог
- Соревнования
- Тренировки
- Архив
- Группы
- Рейтинг
- Edu
- API
- Календарь
- Помощь
- ICPC Challenge
- Главная страница секции
- Конкурс задач
- Об ABBYY Cup 3.0
- ABBYY Cup 2.0
→ Соревнования
- ABBYY Cup 3.0 — Finals (онлайн-трансляция)
- ABBYY Cup 3.0 — Finals
- ABBYY Cup 3.0
→ На платформе
Олимпиадные задачи по программированию: что за зверь?
Автор ruzana.miniakhmetova, 11 лет назад ,
Друзья, недавно в нашем Хаброблоге мы опубликовали пост о том, что же вообще представляет из себя задача спортивного программирования. Изначально пост предполагал сравнение олимпиадных задач с задачами реальной разработки. Однако в финальном варианте мы решили исключить аналогии с промышленным программированием. Будет интересно почитать в комментариях примеры ваших подобных сравнений 🙂
«Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с олимпиадной задачи.
Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.
Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи 🙂 Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.
Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:
Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.
Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).
Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.
Существует немало способов оценки решений для «классических» задач:
Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.
Конечно, говорить об особенностях олимпиадных задач можно бесконечно. Мы осветили лишь самые главные моменты. Если у вас есть вопросы или комментарии – добро пожаловать в комментарии. «
abbyy, конкурс задач, хабрахабр