Pull to refresh

Олимпиадное хобби. Разделяй и властвуй

Reading time 6 min
Views 6.1K
Доброго всем понедельника. Если понедельник для вас не самый приятный день, то предлагаю вам немного расслабиться и проникнуться моим хобби. Моё хобби — решение олимпиадных задач по программированию: встряхивает мозг, будоражит воображение и заряжает энергией (правда не всегда положительной). Не верите? Попробуйте сами, только честно попытайтесь решить поставленную задачу, получите долгожданный Accepted, и наслаждайтесь полученными эмоциями.

Сегодня случай подкинул нам задачу №10474. Это задача на умение применять вовремя простые алгоритмы, поэтому не ждите от нее чего-то сложного и хитроумного. Если вам не интересно решать задачи за счет пары стандартных алгоритмов, то пропускайте топик, а всем остальным добро пожаловать под кат. Нас ждет пара алгоритмов, выбор наиболее удобного решения, ну и, конечно же, Accepted!


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

Давайте, если нам попадается легкая задача, то будем находить ее самое быстрое или самое красивое решение, тогда нам не будет казаться, что мы зря потратили время. Ну и не забывайте делиться своими решениями, которые безусловно могут оказаться красивее и быстрее моего. Может нам даже удастся выдумать алгоритм, которого еще никто не знает, ведь аудитория на хабре достойная ;)

Условие задачи


Перейдём к делу. Как я уже говорил, сегодня будем решать задачу №10474
Привожу вольный перевод условия задачи:
Raju и Meena любят играть в Marbles (предположительно — название игры). У них есть много табличек с числам. Вначале Raju располагает таблички одна за другой в порядке возрастания их чисел. Потом Meena просит Raju найти номер первой таблички с каким-нибудь числом. Она считает до трёх. Если Raju называет правильный номер, то он получает очко, в противном случае очко получает Meena. После определенного числа попыток игра останавливается и побеждает тот, у кого больше очков. Сегодня у вас появился шанс поиграть как Raju. Как продвинутые ребята, вы используете компьютер. Но не стоит недооценивать Meena, она написала программу для отслеживания времени, которое вы тратите на получение правильного ответа. Вам нужно написать программу, которая поможет вам исполнять роль Raju.

Входные данные:
Возможно несколько тестов, но не более 65. Тест начинается двумя числами: N — число табличек и Q — число запросов Meena. Потом следуют N строк, содержащих числа, написанные на N табличках. Эти числа не упорядочены. Далее идут Q строк с запросами. Ни одно из входящих чисел не превышает 10000, и все числа неотрицательны.
Ввод оканчивается, когда N и Q равны 0.

Выходные данные:
Ограничение по времени работы алгоритма: 3 секунды.
Для каждого теста выводится порядковый номер теста.
Для каждого запроса выводится одна строка. Формат строки зависит от того, найдено запрашиваемое число среди табличек или нет. Два варианта:
  • «x found at y», если первая табличка с числом x найдена в позиции y. Позиции нумеруются так: 1, 2, 3...
  • «x not found», если таблички с числом x нет.
Пример:
Ввод:
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

Вывод:
CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3

Эта задача относится к классу алгоритмических задач, а точнее к разделу «Разделяй и властвуй».

Это маленькая подсказка для всех. Теперь рекомендую создать собственное решение, не читая дальше. Тогда вам будет интересно сравнить результат с моим.

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

Решение


Вариант 1

Я решил, что стоит упорядочить массив, а потом в нем найти число. Знаю, что сейчас многие меня назовут «Кэпом». На сайте, где я беру задачи, основным критерием качества решения является время выполнения программы. Чтобы ускорить время выполнения нашего алгоритма, мы будем использовать быструю сортировку, а также бинарный поиск в массиве. Т.е. для решения задачи мы последовательно реализуем алгоритм быстрой сортировки входного массива с числами, а потом алгоритм двоичного поиска.

Знание этих алгоритмов, а главное, умение их реализовать, пригодится в реальном программировании, поэтому рекомендую ознакомиться с алгоритмами тем, кто до сих пор ни разу их не реализовывал, тем более оба они очень простые.

Алгоритм быстрой сортировки отлично описан здесь. Я лишь приведу его краткое описание по шагам:
1. В массиве выбирается некоторый элемент — опорный. Обычно берут центральный элемент, но бывают случаи, когда лучше выбирать какие-то другие элементы, это зависит от свойств массива.
2. Все элементы меньше опорного числа перемещаются в левую часть массива, а элементы больше опорного в правую. Т.о. мы разделяем массив на два подмножества. Слева от опорного элемента располагаются элементы меньше опорного, справа наоборот.
3. В обоих подмассивах снова выполняются все шаги, если число элементов не менее двух.

У быстрой сортировки есть модификации, которые ускоряют ее работу. Если вам интересно, то попробуйте реализовать модификацию и проверьте ускорение алгоритма на деле.

Алгоритм бинарного поиска в упорядоченном массиве еще более простой.
1. Выбирается центральный элемент массива, который разделяет массив на два подмассива.
2. Если выбранный элемент больше искомого, то продолжаем поиск в левом подмассиве по той же схеме. Если меньше, то в правом.
В итоге, мы достаточно быстро добираемся до искомого элемента.

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

Первый вариант решения: Accepted 0.368

Вариант 2

Если обратить внимание на ограничение, которое описано в условии: ни одно из входных чисел не превышает 10000, то появляется еще одно решение. Перед вводом чисел на табличках мы можем создать массив M на 10000 элементов.
M[i] = 0, если таблички с числом i нет
M[i] = r, где r — количество табличек с числом i

Этот массив мы можем заполнить сразу, при вводе чисел. При заполнении массива мы определим количество уникальных чисел.

Далее, мы создадим еще два массива (или массив структур, если вам удобнее). Первый массив elements будет содержать уникальные числа, упорядоченные по возрастанию. Второй массив positions будет содержать позицию, где positions[i] — номер первой позиции числа elements[i]. Эти массивы мы можем заполнить с помощью одного прохода по массиву M.
0. pos = 0 — текущая позиция, j = 0 — номер текущего уникального числа
1. Ищем M[i]!=0
2. Заносим новое число в elements[j]=i
3. positions[i]=pos
4. Сдвигаем pos на M[i], j++
5. Если мы не прошли все 10000 чисел (или можно запомнить максимальное, для ускорения работы), то переходим к шагу 1

Теперь у нас есть массив elements, где мы снова будем искать числа с помощью двоичного поиска. Ответ же будем выдавать из массива positions с индексом найденного числа в массиве elements.

Второй вариант решения: Accepted 0.248

Почему же второй вариант оказался быстрее первого? Главное отличие этих двух подходов в том, что во втором варианте мы отказались от сортировки, которая является самой затратной по времени. Вместо траты времени на сортировку, мы украли больше оперативной памяти, чем требовалось. И двоичный поиск ведется в массиве с меньшим числом элементов в случаях, когда имеются таблички с одинаковыми числами.
Второй вариант оказался бы неприменимым, если бы входные числа были бы ограничены лишь возможностями вместимости 4 байтов. На олимпиаде иногда стоит обращать внимание на такого рода условия, которые зачастую создают, намекая на альтернативные варианты решения задачи.

Почему же задача относится к разделу алгоритмов «Разделяй и властвуй»? Потому что оба использованных алгоритма относятся к этому разделу, ведь в быстрой сортировке мы разделяли массив на две части, а потом его сортировали, и в двоичном поиске мы постоянно сужали поиск разделением искомой области пополам.

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

P.S. сайт http://uva.onlinejudge.org/, откуда взята задача у меня неожиданно перестал грузиться в FF. Не уверен, что это проблема именно браузера, но в остальных браузерах сайт открывается. Имейте ввиду, если вдруг столкнётесь с такой же проблемой.

Мои решения, как всегда можно скачать: вариант 1 и вариант 2.

Accepted (0.248). Удачи!

UPD: Благодаря подсказкам господина dimoclus, мне удалось ускорить второй вариант до Accepted (0.108) (скачать)
UPD: Также, прошу обратить внимание на решение господина KapJI, скорость выполнения которого 0.104

UPD: Алексею, читателю хабры, удалось получить лучшее время (0.052) среди всех пользователей сайта uva.onlinejudge.org. Вот его решение. Мои поздравления!
P.S. у кого есть лишний инвайт, не пожалейте для Алексея, думаю ему есть чем поделиться с нами.
Tags:
Hubs:
+18
Comments 36
Comments Comments 36

Articles