Новогоднее хабра-соревнование по программированию-2013 (C++)

    Все мы слышали поговорку: как новый год встретишь — так его и проведешь. Оливье в сторону!

    Рассчитывать на 5 часов адского программирования в праздник было бы негуманно, потому задача всего одна и она весьма лапидарна:
    Программа должна прочитать из стандартного потока ввода целое число N (от 1 до 230), и напечатать сумму простых чисел меньших либо равных N.
    Побеждает тот, кто напишет самое быстрое решение, проходящее все тесты (хотя-бы один неправильный ответ — и решение отклоняется). Скорость решения оценивается на тестах в районе верхней границы допустимого диапазона N (но не ровно 230).

    Победитель получает всеобщее признание, сотни кармы и приятное чувство что он порвал всех на Хабре. Долгие годы молодые поколения разработчиков будут восхищаться его кодом, а девушки — чепчики в воздух бросать. По меньшей мере первые 4 read-only пользователя будут приглашены на Хабр.

    Ограничения:
    1. Размер файла с решением — не более 1024 байт без учета первой строки с комментарием
      (краткость — сестра таланта)
    2. Только один язык программирования — C++ в исполнении clang 3.2, только стандартные библиотеки (+pthreads). Если используете С++11 — указывайте свою версию libc++ на всякий случай. С OpenMP/TBB — не судьба, с clang они пока плохо уживаются.
      Много кода писать тут не придется, так что даже если С++ не ваш основной язык — в нем легко будет разобраться на уровне достаточном для решения задачи.
    3. Тесты будут проводиться на 64-х битном Linux-е.
      Можно использовать 4 ядра процессора (i7-3820) и не более 30 Гб памяти.
    4. Допустимое время работы на каждый тест — не более 60 секунд.

    Оформление решения, сроки и куда слать
    Решения принимаются до 23:59 (время Московское) 1-го Января 2013-го года по адресу contest@14.by, файл с решением должен быть прикреплен к письму — не нужно вставлять код в само письмо!

    В первой строке решения должен быть комментарий вида:
    //@BarsMonster
    
    Где BarsMonster — имя вашего пользователя на HabraHabr (участвовать могут и read-only пользователи, регистрируйтесь)

    Результаты и решения будут опубликованы на Хабре — по возможности не позднее 2-го Января.

    Пример решения: (немного не успевает по времени, 242 байта)
    //@BarsMonster
    #include<iostream>
    using namespace std;
    
    int main()
    {
      __int64_t n, sum=0;
      cin>>n;
      for(__int64_t i=2;i<=n;i++)
      {
        for(__int64_t j=2;j<i;j++)
          if(i%j==0)goto next;
        sum+=i;
    next:;
      }
      cout << sum << endl;
    }

    Пример работы:
    test@lbox2:~$ ./a.out
    10
    17
    
    test@lbox2:~$ time ./a.out
    100000
    454396537
    
    real    0m7.073s
    user    0m4.693s
    sys     0m0.000s


    Update: 22 минуты после начала конкурса — и уже пришло первое решение:-)
    Update: 3 часа после начала соревнования — 10 решений.
    Update: Для уменьшения количества драмы убрал запрет на повторную отправку, но прошу не злоупотреблять.
    Update: Для тех кто пишет в VisualStudio — простейшую проверку на компилируемость можно сделать тут: llvm.org/demo (не забываем выбирать C++)
    Update: 3 часа до конца соревнования — количество решений перевалило за 160.
    Update: 1 час до конца соревнования — 200 решений.
    Update: 7 минут до конца — прилетает по 3-5 решений в минуту
    Update: Прием решений закончен, получено 265 решений (с дубликатами). Таблица результатов, исходные коды победителей, анализ ошибок — все будет опубликовано 2-го Января (надеюсь успеть) в отдельной статье в этих же хабах.
    Update: 183 решения без повторных отправок.
    Update: Файл main.cpp прислали 42 участника
    Update: 162 решения скомпилировались с первого раза, я ожидал намного худшего.
    Update: 164 решения скомпилировались, 1 пало жертвой C++11, 18 — жертвой более более прозаических ошибок.
    Update: Простые тесты (1, 10, 1000, 100000, 1000000) прошли 109 решений, 47 дали неправильные ответы (включая и креши), 8 не успели выдать ответ за минуту (пример решения из статьи тест на 1млн проходит за 5 минут 36 секунд).
    Update: Сложные тесты завершены, 91 решение прошло все тесты в установленное время, 5 — с неправильными ответами, 13 — не уложились в минуту на тест. Время решения — измерялось с микросекундной точностью, и бралось среднее по результатам 4-х разных тестов. Формируется таблица результатов.
    Update: Для top-3 тесты повторены 100 раз (время суммировалось для большей точности) — результат не изменился.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 86
    • +2
      > в исполнении clang 3.1

      А почему не 3.2?
      • +2
        Потому что я пропустил релиз :-) Но замечание справедливое, изменил на 3.2.
      • 0
        Можно использовать ассемблерные вставки?
        • +1
          Ограничений нет, главное в 1024 байта уложитесь :-)
        • +1
          Можно юзать pthread?
        • +1
          Можно ли использовать С++11?
          • +1
            Да, на всякий случай укажите свою версию libc++
          • –1
            Сделал в студии — надеюсь прокатит и скомпилится.
            • 0
              Если код корректно написан, и не использует Microsoft-specific типов — то конечно прокатит.
              • –1
                Не уверен __int64 микрософтовский или общий.
                unsigned char еще использовал, два типа итого.
                • +4
                  __int64 — майкрософтовский, надо использовать int64_t из стандарта плюсов
                  • –1
                    Нда, поздно увидел поправку «для тех кто в студии». Два раза переотправлял. Так и хочется сказать — «не ругайсо, нащяльника». Ну да ладно.
                    Эхх, теперь до завтра ждать результатов. Особый, программистский накал страстей.
                    • +3
                      А можно просто писать long long?
            • 0
              OpenMP/TBB можно использовать?
              • 0
                К сожалению, это уже выпадает за пределы стандартных библиотек.
                Так что остаются средства pthreads/C++11
              • 0
                Вопрос, в приведенном пример учитывалось общее время работы программы вместе с вводом данных или только цикла расчета ???
                • 0
                  Конечно, с вводом. Да и вообще, какая разница? Мы же читаем только одно число и пишем одно число
                  • 0
                    Ну как вам сказать, ввод числа руками, ввод из файла и константа это разные по времени обработки методы ввода. Например константа вообще не требует обработки, ввод из файла зависит от скорость диска и т.п. ввод руками вообще зависит от пользователя, (что если я пойду чайку хлебнуть а интер не нажму)
                    А время как мы видем идет на миллисекунды, это важно, надо либо обозначить как именно все должны делать ввод данных либо ваша time неочем.
                    • +1
                      Ввод в данном случае не важен, т.к. важно время, занятое у ЦП (колонка user у time).
                      • 0
                        А с какой точностью оно измеряется? До 1 миллисекунды или хуже? И входит ли в него время на запуск программы?
                        • 0
                          All times are measured in terms of the number of clock ticks used.

                          Получается измеряется в тиках
                          Насчет второго сказать ничего не могу, с никсами почти не имел дела.
                        • 0
                          Колонка user считает суммарное время на каждом из 4-х ядер. Если распараллеливать, то значение получится в 4 раза больше реального.
                          • 0
                            Если бы в условиях задачи программа должна была бы принимать число как параметр, никаких проблем бы не было бы.
                            • 0
                              Очевидно, при тестировании руками никто ничего вводить не будет. :-)
                  • +1
                    Напишите параметры, с которыми вы компилируете.
                  • +1
                    Судя по ограничениям, можно использовать готовый массив простых чисел, если уложиться в 1024 байт?
                    • 0
                      Дядя, вы тут предсчетом не пролезете — 1024 байт = 1024 символов (а то и меньше). Там до 2^30 — не прокатит. Нужно писать блочное решето и генерировать числа в разных потоках, а вообще нужно подумать.
                      • +3
                        Нужно написать некоторый код, а на остатке байтов предподссчет засунуть, diff-кодирование.
                    • 0
                      Начнём с однопоточного решета. На Core i5 430UM 1200 Mhz в минуту уложился.
                      • 0
                        Хм, у меня тест Миллера-Рабина на 2 в 30-ой степени в минуту не помещается.
                        • +1
                          Хм, а решето Аткина, похоже, справляется.
                          • 0
                            миллер-рабин тоже в минуту не уложился, а актин что-то с segfault-ом вылетает, может как-то от промежуточного массива избавиться или сократить, но ковыряться глубже сегодня сил нет никаких)
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                std::bitset-ом пользуетесь? у меня и на нем вылетает, где-то на 90 млн., гуглю…
                                • +3
                                  понял, на стеке большие массивы создавать больше не буду)
                            • 0
                              Попробуйте линейное решето Эратосфена — должно проходить.
                              • 0
                                Не надо подсказывать! По крайней мере сегодня.
                                • 0
                                  Дак что тут из подсказки. Оно находится по запросу «решето эратосфена за линейное время» за 1 минуту. Просто такой вот тезис.
                            • 0
                              Для 230-1?
                          • 0
                            Ключи компиляции?
                          • 0
                            > Побеждает тот, кто напишет самое быстрое решение
                            Время оценивается какое? Wall clock?
                            • 0
                              Да, wall clock. Ввод перенаправляется из файла, потому ждать его не придется.
                            • +2
                              Можно уже обсуждать? :)
                              • +5
                                Я писал блочное решето Эратосфена ( e-maxx.ru/algo/eratosthenes_sieve#7 ) с оптимизациями:
                                1) Ходим только по нечётным.
                                2) Юзаем ручной битсет.
                                3) Выбираем размер блока, как LCM первых семи простых. Благодаря этому, мы можем предпосчитать, какие числа в этом блоке будут делиться на эти простые, и в каждом блоке уже начинать с 8-го простого.
                                4) Так как мы юзаем битсеты, можно быстро перепрыгивать сразу по 16 бит, предпосчитав для каждой маски сколько в ней нулевых бит и сумму их позиций.
                                5) На оставшееся место впихиваем предпосчёт.

                                Код: pastie.org/private/iffyfn64f6tvryzeucqw

                                На моём i7 на произвольных тестах дольше секунды не работает.
                                В среднем ~0.3 где-то.
                                • +1
                                  Маньячина, а теперь разархивированную версию ;-)
                                  • 0
                                    Я паковал 8 чисел, взаимно простых с 30 (от 30k+1 до 30k+29) в 1 байт. Выбивал числа так же умножая только на взаимно простые с 30, да еще запоминал таблицу умножения данного простого на числа 1..29 в системе счисления «сдвиг — бит». Плюс борьба с тем, чем массив c решетом не вмещался в кэш.
                                    На i5 2.67МГц для N=10^9 время 0.65 сек.
                                    Но это если решение вообще работает.
                                    • 0
                                      И даже на тесте 268588319 укладывается в секунду? ;)
                                      • +2
                                        У меня дома i7-2700K (Win7 64 + gcc 4.6.1):

                                        === a.exe ===
                                        1908937595474167

                                        Execution time: 0.465 s
                                        • 0
                                          результат такой же, время 0.156 s (на i5)
                                          • 0
                                            Тут всё теперь от тестов зависит, это же худший случай для моего кода.
                                            Я думаю, там ещё более быстрые решения будут.
                                            Посмотрим завтра что получилось :)

                                            Мой исходник в читаемом формате: pastie.org/private/zee1lhmd6pugvavtmcjpa
                                            • 0
                                              А в нечитаемом можно посмотреть? :)

                                              Ещё мне кажется, что для i == 0 можно просто начать с res = (-1) + 2 + 3 + 5 + 7 + 11 + 13; и сэкономить немало байтов кода, например для бОльшей таблицы предподсчета.

                                              Да и саму таблицу можно сделать эффективнее, вместо лестницы if-ов используя массив и цикл.
                                              • 0
                                                Правда надо будет отдельно обрабатывать N < 13, суммируя primes[j]
                                              • 0
                                                Ещё можно избавиться от относительно дорогого деления, заранее подсчитав:
                                                k[j] = start_from / primes[j];
                                                

                                                И после просеивания
                                                k[j] -= block_size;
                                                

                                                Не уверен, что улучшит, но вдруг :)

                                                И ещё — просеивание можно делать до sqrt(i), а не до j < primes_count;
                                                • 0
                                                  Да я вас уверяю, у меня далеко на самое крутое решение, в топ-10 бы попасть :)
                                                • 0
                                                  Ну и распараллелить должно быть несложно.
                                                  Хотя ради этого придётся уменьшить таблицу, что в итоге может оказаться невыгодным.
                                              • 0
                                                gcc — это вообще другой разговор. Почти всё на gcc будет чуть быстрее. Зачем Вы спрашивали ключи компиляции тогда?
                                                Просто на 268588319 у меня Ваше решение работает больше секунды (на 3,6ГГц) и раза в 3 медленнее, чем 2^30 — 1 (на clang 3.2 в linux x64 с флагом -O3) — из-за предподсчёта.
                                                • 0
                                                  Я тестил ещё на ноуте (i3-370 2.4Ghz, linux x64, clang -O3): 0m0.758s.
                                            • +2
                                              написал так:
                                              1) считаем простые числа в диапазоне от 1 до sqrt(n)
                                              2) так как чисел всего 2^31, определяет рабочий интервал, для которого уже просчитана сумма чисел в предыдущем интервале. интервалов 16, в среднем надо просчитать от начала интервала до его середины. итого 1/32
                                              3) считаем сумму оставшихся простых чисел в рабочем интервале, блочным решетом эратосфена с примитивными оптимизациями чётных значений.

                                              блочное решето с примитивными оптимизациями работает на значениях 2^29 около 0,5 секунд. С предпросчётом от 0,01 до 0,05
                                              • 0
                                                Совсем не понял зачем там G, D, F. Если их убрать, код уменьшится на 59 байт.
                                                • 0
                                                  PS и т.к. сказано, что тестироваться на Linux x86_64 будет, то int64_t можно было на long заменить. 3 байта всего, но может ещё что полезное поместится в суммарные 62 байта. :)
                                            • 0
                                              Какие прогнозы на лучшее время?
                                              Думаю, 0.3-0.5 сек на тест.
                                                • 0
                                                  Да, про явные формулы я забыл. Хакеры-математики, конечно, непобедимы.
                                                  • 0
                                                    Нет-нет, формул тут никаких нет, кроме китайской теоремы об остатках (она максимум даст ускорение в 2-3 раза).
                                                    • 0
                                                      А дзета-функция точно никак не поможет?
                                                      • 0
                                                        Первый раз слышу, детали в студию :-)
                                                        • 0
                                                          Я уже всё забыл. Но она как-то использовалась для оценок количества простых чисел.
                                                          • 0
                                                            Не, дзета-функция не даёт точного количества простых. С её помощью асимптотики находят
                                                        • +1
                                                          Общих формул то может нет, но есть предподсчёт — те же формулы. А с таким слабым ограничением на входные данные и указанием, что тестироваться будет на числах, близких 2^30, его очень резонно делать.
                                                  • +1
                                                    Я бы оценивал по суммарному результату на N случайных числах (одинаковых для всех), двоичные логарифмы которых (с плавающей точкой) распределены равномерно в интервале [20,30]
                                                    • 0
                                                      А потом, для десятки лучших на ещё бОльшем количестве тестов.
                                                      • 0
                                                        Можно спросить почему Вы бы оценивали иначе? И где можно прочитать про метод подборки входных тестовых данных, вамиприведенный?
                                                        • 0
                                                          Дело в том, что заранее зная тесты, можно написать программу, эффективную именно для этого.

                                                          Например, программа, печатающая 454396537 независимо от ввода, победит в конкурсе программ, которые будут тестироваться только числом 100000.
                                                          • 0
                                                            Использовать словарь Вам не даст ограничение размера программы в Х байт, где Х равен, как я смею предположить, не больше 1-2К.
                                                            • 0
                                                              Я привёл радикальный пример — словарь не обязательно должен быть полным, чтобы давать хороший результат в заданной узкой области за счёт остальных возможных значений.
                                                            • 0
                                                              Ограничений нет, главное в 1024 байта уложитесь :-)
                                                              откоментировал BarsMonster, к тому же выше уже писали любители читов, что «ничего не выходит, мама что делать?».
                                                          • 0
                                                            Нет, лучше, чтобы равномерно были распределены сами числа. Иначе половина примеров окажется меньше 2^25, а там время практически нулевое.
                                                            • 0
                                                              Да, вы правы — обычное равномерное распределение лучше, а я перемудрил.
                                                            • 0
                                                              Ещё интересным был бы рейтинг «по худшему времени» — подозреваю, что после обфускации большинство решений легко укладываются в 1024 байта, поэтому для дальнейшего ускорения логично использовать таблицу предварительно вычисленных значений.

                                                              Тесты на небольшом наборе вводов могут легко превратиться в лотерею — и победит тот, кто лучше угадает с таблицей.

                                                              А вот если отсортировать участников по лучшему «худшему времени» на одном вводе и потом тщательно проверять лучших, найдя худшее время каждого.
                                                              • 0
                                                                С какой таблицей?
                                                                • 0
                                                                  С таблицей предпросчитанных значений, судя по всему.

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