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

    Доброго всем понедельника. Если понедельник для вас не самый приятный день, то предлагаю вам немного расслабиться и проникнуться моим хобби. Моё хобби — решение олимпиадных задач по программированию: встряхивает мозг, будоражит воображение и заряжает энергией (правда не всегда положительной). Не верите? Попробуйте сами, только честно попытайтесь решить поставленную задачу, получите долгожданный 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. у кого есть лишний инвайт, не пожалейте для Алексея, думаю ему есть чем поделиться с нами.
    Поделиться публикацией

    Комментарии 36

      +1
      Нет компиляторов разрешонных языков, но мой вариант на C#:
      /// Псеводсортировка
      int[] M = new int[10000];
      for (int i = 0; i < N; i++) M[N_array[i]]++; // Инициализируем, как второй вариант
      int ii = 1;
      for (int i = 0; i < M.Length; i++) // Устанавливаем в M[element] порядковый номер этого элемента, либо 0 если его нет 
          if (M[i] > 0)
          {
              int j = M[i];
              M[i] = ii;
              ii += j;
          }
      
      ///Анализ
      Console.WriteLine("Case# 1:");
      for (int i = 0; i < Q; i++)
      {
          int n = M[Q_array[i]];
          if (n == 0)
              Console.WriteLine("{0} not found", Q_array[i]);
          else
              Console.WriteLine("{0} found at {1}", Q_array[i], n);
      }
      Console.ReadLine();
      
        0
        Для скорости можно в цикле for (int i = 0; i < N; i++) искать max, а цикл for (int i = 0; i < M.Length; i++) заменить на for (int i = 0; i < max; i++)
          0
          Я рад, что вы так быстро пришли к выводу, что с нашими граничными условиями на числа, можно обойтись не только без сортировки, но и без поиска. Но спешу вас огорчить: я проверял такой подход, он медленнее, чем первый вариант. Мою реализацию вашего подхода на C++ можно скачать тут и проверить. Accepted (0.488)
          Предполагаю, что такой подход дает бешеный прирост производительности в случаях, когда у нас много разных чисел от 1 до 10000, но когда чисел мало, а разброс между ними большой (например два числа: 1 и 10000) и Q стремится к максимуму, то все преимущества сразу пропадают, потому что независимо от количества разных чисел нам все равно приходится работать с массивом в 10000 элементов.
            +4
            Просто нужно владеть инструментом: pastebin.com/Rhr7Uswk (этот же алгоритм, но правильно написанный на C): Accepted (0.108)

            Ошибки, приводящие к значительному падению быстродействия:
            • использование iostream
            • динамичсекое выделение памяти
            • «плохие» типы данных (работа с 16-битными целыми медленнее, чем с 32-битным в 32-битном и 64-битном режимах)


            Если же говорить о теории, то самый быстрый из возможных алгоритмов — отсортировать оба списка: и самих элементов, и и запрашиваемых. А затем использовать бинарный поиск в массиве M, каждый раз отталкиваясь от предыдущего найденного элемента.
              +3
              Сомневаюсь, что быстрая сортировка и бинпоиск с асимптотикой O(n log n) могут быть быстрее сортировки подсчетом с асимптотикой O(n).

              А вот моё решение на С++: pastebin.com/E9Xc4aBm Accepted (0.104).
                0
                Благодарю за то, что открыли мне глаза на некоторые особенности языка C++. Теперь мне удалось ускорить второй вариант решения до Accepted (0.108)
              0
              Честно говоря, я сначала полагал, что такое решение должно быть значительно быстрее чем оба варианта из поста, но это оказалось не так. Думаю, что тут все дело в «не очень удачных тестовых наборах» под такой подход.
                0
                Для меня тоже это очень странно, что ваш второй способ быстрее этого… И тут и там используется один проход по массиву…
              +2
              Ещё один вариант. Хорош, когда на одном наборе мало тестов.

              Проходимся по массиву, подсчитывая числа, которые меньше нашего. Заодно ищем наше число — есть оно или нет.

              Когда на одном наборе 10 тыс. тестов — ваш вариант, наверно, лучше.
                +1
                Несмотря на всю полезность знания алгоритмов быстрой сортировки и бинпоиска, должен напомнить, что олимпиадные задачи важно не только правильно решить, но и написать это решение за минимальное время.

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

                  … уметь быстро и без ошибок писать эти алгоритмы.

                  Собственно, подобные задачи на проверку знания алгоритмов и рассчитаны.
                    +1
                    >> уметь быстро и без ошибок писать эти алгоритмы.

                    вовсе нет. на этих соревнованиях необходимо выжимать все что только можно из компилятора, стандартной библиотеки и языка как такового в целом. Попытка «написать быстро и без ошибок qsort» равносильна провалу, потому что пока вы ее будете писать другие команды уже решат задачу.
                      0
                      Лично я уже не помню, когда последний раз писал вручную быструю сортировку — как в Си, так и в более привычной для меня Java присутствуют ее реализации с возможностью использования произвольных компараторов. Задачи, в которых этого не хватает, исключительно редки.

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

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

                      Поэтому важно не только знать реализации простейших вещей, но и быть в курсе всего арсенала функций, которых можно использовать уже готовыми.
                        0
                        Когда я учился, все быстрые сортировки как раз таки писались ручками, потому что STL был в то время весьма зачаточным, а самым популярным языком на олимпиадах в тогда был Pascal, где никакими ништяками вроде std::map и близко не пахло. И такие задачи «на знание алгоритмов» определенно наследие прошлого.
                    +1
                    Из условия задачи не смог понять, какое ограничение на N и Q.
                      +1
                      Ни одно из входящих чисел не превышает 10000

                      «входящие числа» — это все числа во входном файле, включая N и Q
                      0
                      Ваш второй способ — тоже сортировка (черпаком, если не ошибаюсь).
                        0
                        Мне кажется, что идея с bucket sort тут должна выстрелить в массив Elements[] на позицию RequestedNumber мы кладем число, где впервые встречается этот элемент (aavezel предлагает что-то очень похожее, только не понятно зачем ему более одного массива), т.е.

                        4 1
                        2
                        3
                        5
                        1
                        5

                        Elements[2] = 2
                        Elements[3] = 3
                        Elements[5] = 4
                        Elements[1] = 5

                        -? Elements[5] -> 4

                        Время работы линейно($\BigO(n)$) от длины массива входных данных — быстрее сделать невозможно, потому что нам все равно придется все числа считать.
                        Раcход памяти псевдоконстанта — \BigO(k) где k = max(a_i)
                        Время на один запрос константна от длины входных данных
                          +1
                          пугает серьёзность, с которой разбирается столь элементарная задача.
                            +1
                            Нагуглил конкурентов. Выгодно отличается от данной системы наличием нескольких десятков языков, включая, например, D, Erlang, Go, Whitespace, Brainf***, PDF и bash. :)

                            www.spoj.pl
                              0
                              А вот еще русские:
                              acm.sgu.ru
                              acm.timus.ru
                                0
                                > acm.sgu.ru
                                Delphi, MSVC, gcc, g++

                                :S

                                > acm.timus.ru
                                Java, C, C++, Pascal, C#

                                :S

                                > spoj.pl
                                ADA 95, Assembler, Bash, Brainf**k, C, C#, C++, C99 strict, Clips, Clojure, Common Lisp, D, Erlang, F#, Fortran 95, Go, Haskell, Icon, Intercal, JAR, Java, JavaScript, Lua, Nemerle, Nice, Ocaml, Pascal, PDF, Perl, Perl 6, PHP, Pike, PostScript, Prolog, Python, Python 3, Ruby, Scala, Scheme, Smalltalk, Tcl, TECS, Whitespace

                                WIN :P

                                Недостатка перед остальными не вижу. Аудитория — десятки решений в минуту, задач — тысячи.
                                  0
                                  На большинстве используемых языков никто не решает олимпиадные задачи, потому у нас никто и не реализует их поддержку. (ну разве что плохо, что Python нет)

                                  Зато для многих задач есть и русские условия.
                                    0
                                    Да, для решения олимпиадных задач почему-то часто только системные ЯП допускаются. Извините, но отсутствие таких штук как Scheme непростительно. Мы же не драйвера пишем и не системные утилиты.

                                    > ну разве что плохо, что Python нет

                                    Чем он такой особенный? Будете делать Python, всё-равно скриптовый язык появится, можно поддержать и Ruby с Tcl. Но больше всего для некоторых задач не хватает Haskell и Scheme.
                                0
                                На spoj'e не делают разницы между языками и временем исполнения в отличие от acm.mipt.ru
                                  0
                                  > acm.mipt.ru
                                  С/С++ (видимо, они считают это одним языком), Pascal, Perl, Python, Java

                                  Похоже, в Российских онлайн-судьях допустимые языки определяются по их позиции на TPCI. На spoj.pl ограничения по времени выполенения не очень строгие и можно любую задачу решать на подходящем языке, а не на аком-либо из популярных, или на PostScript'е с брейнфаком, если делать нечего. :) Если же вы приучены забивать гвозди микроскопом, то, да, можно и на acm.*.ru
                                    0
                                    С чего это вы взяли? А по поводу временных ограничений на споже то, видимо, мало вы там что решали. Есть задачи, на которых в принципе не сможете пройти временные лимиты на интерпретируемых языках.
                                      0
                                      Кстати, разделение таки есть. Разве что лимит один на всех.

                                      www.spoj.pl/ranks/FASHION/lang=JAVA

                                      Там для некоторых задач уже есть ограничение на языки, можно предложить разработчикам ослабить таймлимит (на коэффициент) для нектороых языков. А вообще, если задача требовательна к процессору и на неё стоит строгий лимит — значит нужно выбрать язык, реализация вашего алгоритма на котором справится за установленное время. Не писать же числодробилки на Tcl, например, даже если вы всё остальное решаете на нём.
                                0
                                Кстати, проблема с браузером у меня возникала также! Нужно кукис почистить и все дальше отлично работать будет ;)
                                  0
                                  У меня не заходит в хроме. Выдаётся сообщение, что слишком много переадресаций.

                                  Видимо, надо почистить куки и зайти как незнакомый пользователь.
                                    +1
                                    Сортировка подсчетом — Accepted (0.100).
                                    Автору большое спасибо за задачки, и есть одна небольшая просьба — выкладывать решение не на dropbox.com, а например на pastebin.com.
                                      0
                                      Обещаю исправиться
                                      +2
                                      За идею с задачками респект. Отличная мысль. Возьму на вооружение.
                                        +1
                                        Алексею, читателю хабры, удалось получить лучшее время (0.052) среди всех пользователей сайта uva.onlinejudge.org. Вот его решение. Мои поздравления!
                                        Он также написал генератор тестов, возможно кому-нибудь понадобится.
                                          0
                                          Алексей молодец.
                                          p.s. нужно попробовать искать не только максимум но и минимум.
                                          Сейчас хотел попробовать, но uva.onlinejudge.org не работает…
                                            0
                                            Сайт тоже некоторое время не работал у меня.
                                            Потом прочитал, что хром мне выводит, что, мол, куча переадресаций идёт с этого сайта на него же.

                                            очистил куки и спокойно зашёл.

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                        Самое читаемое