1 января 2013 в 00:00

Новогоднее хабра-соревнование по программированию-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 раз (время суммировалось для большей точности) — результат не изменился.
Михаил Сваричевский @BarsMonster
карма
975,7
рейтинг 0,0
Пользователь
Самое читаемое Разработка

Комментарии (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?
            • +2
              Конечно, да :)
  • 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
    Напишите параметры, с которыми вы компилируете.
    • 0
      clang++ --std=c++11 -O3 -pthread yourfile.cpp
  • +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
    Ключи компиляции?
  • 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
        Да, про явные формулы я забыл. Хакеры-математики, конечно, непобедимы.
        • 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
          С таблицей предпросчитанных значений, судя по всему.

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