Олимпиада по программированию:
разбираем задачу, выбираем подход и язык для решения
Олимпиадные задачи делятся на классические и конструктивные. Классические задачи составляют по темам: динамическое программирование, алгоритмы на графах или на строках, теоретико-числовые алгоритмы и подобные, поэтому для решения необходимо свести задачу к известному алгоритму. Решение конструктивных задач не сводится к написанию общеизвестного алгоритма – его нужно «увидеть»
Решение олимпиадной задачи
Разберем классическую задачу 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 лет.