Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 141
Очень хотелось бы услышать от авторов объяснение работы алгоритмов, особенно от автора который занял первое место.
Похоже на
(=
while :; do
dd if=/dev/urandom of=file.cpp bs=1K count=1
if clang++ file.cpp && [[ $(echo 123 | ./a.out) -eq 1591 ]]; then
cat file.cpp; echo win
fi
done
(=
А break где? ;)
Где-то тут :)
Скрытый текст
#!/bin/bash
i=`cat i`;
compile() {
r=$(clang++ file.cpp 2>&1| grep generated)
if echo $r | grep -q ' 0 errors'; then
let i++;
echo $i > i
cp file.cpp $i.cpp
fi
echo -ne "\r$r";
}
while :; do
dd if=/dev/urandom of=file.cpp bs=1K count=1 2>/dev/null
if compile && [[ $(echo 123 | ./a.out 2>/dev/null) -eq 1591 ]]; then
echo win
exit
fi
done
Перловский быстрее найдётся )
Лучше не ждать объяснений, а самому разобраться. Тем более, что там всё просто :)
Сори, но я немного не понял — это был сарказм, я надеюсь? Потому что если для вас понятен сорец победителя — я хочу пожать вам руку.
Нет, мне он действительно понятен. Правда, не в таких деталях, чтобы понять, зачем нужна конструкция !!~-n (которую я бы записал просто как n!=1). Хотя нет, посмотрел еще раз — и понял, это потому, что алгоритм не воспринимает 2, как простое число, и его приходится учесть отдельно. Так что в самом деле всё понятно. Непонятно только, почему он вызывает проблемы у других. Вы что, не ломали игрушки с помощью дизассемблера? Там и не такие головоломки встречались :)
.
.
Как я читал этот код:
1. Видим длинную строку. На код непохоже, вероятно, это таблица в какой-то системе счисления.
Смотрим на использование. Видим схему Горнера (x=x*96+"..."[i]-32) — всё правильно, основание 96, но как в одном цикле заполняется целый массив? Ага, u[i/7+2] — в течение 7 шагов это один и тот же элемент. То есть, числа 7-значные. Остроумно, примем на вооружение. Я бы оставил двойной цикл.
448=7*какая-то степень двойки — годится. Почему +2? Пока непонятно, оставим на потом.
2. Следующий цикл — разностная схема. Кодировка вторыми разностями, дело знакомое. Я иногда гладкие функции тоже так кодирую.
3. sqrt(n) — понятно. n>>24<<24 — знакомая конструкция, оставили старшие 8 бит. Не лучше ли n&-0x1000000? Или n&-1<<24? Автору виднее…
4. Опять n>>24. Почему не соптимизировано с предыдущим? Пока неважно, наверное, невыгодно. 2*!L*!!~-n… Понятно, если L==0 или… (считаю с конца) n!=1, то 2 иначе 0. Наверное, зачем-то нужно.
5. Ну, тут понятно. Одно решето для поиска простых, другое — для анализа нужного интервала. Детали уже неинтересны. Хотя… почему там в одном месте 2*i, а не i*i? Опять же, автору виднее…
В общем, всё просто. Где можно выиграть? Я бы попробовал задавать табличку как (n*n/ln(n)*какой-то коэффициент + поправка из таблицы), с шансами уложиться в 5 знаков на элемент, а на освободившихся 100 байтах попробовать устроить вычисление с шагом 30, которое раза в 2 быстрее — но лень…
1. Видим длинную строку. На код непохоже, вероятно, это таблица в какой-то системе счисления.
Смотрим на использование. Видим схему Горнера (x=x*96+"..."[i]-32) — всё правильно, основание 96, но как в одном цикле заполняется целый массив? Ага, u[i/7+2] — в течение 7 шагов это один и тот же элемент. То есть, числа 7-значные. Остроумно, примем на вооружение. Я бы оставил двойной цикл.
448=7*какая-то степень двойки — годится. Почему +2? Пока непонятно, оставим на потом.
2. Следующий цикл — разностная схема. Кодировка вторыми разностями, дело знакомое. Я иногда гладкие функции тоже так кодирую.
3. sqrt(n) — понятно. n>>24<<24 — знакомая конструкция, оставили старшие 8 бит. Не лучше ли n&-0x1000000? Или n&-1<<24? Автору виднее…
4. Опять n>>24. Почему не соптимизировано с предыдущим? Пока неважно, наверное, невыгодно. 2*!L*!!~-n… Понятно, если L==0 или… (считаю с конца) n!=1, то 2 иначе 0. Наверное, зачем-то нужно.
5. Ну, тут понятно. Одно решето для поиска простых, другое — для анализа нужного интервала. Детали уже неинтересны. Хотя… почему там в одном месте 2*i, а не i*i? Опять же, автору виднее…
В общем, всё просто. Где можно выиграть? Я бы попробовал задавать табличку как (n*n/ln(n)*какой-то коэффициент + поправка из таблицы), с шансами уложиться в 5 знаков на элемент, а на освободившихся 100 байтах попробовать устроить вычисление с шагом 30, которое раза в 2 быстрее — но лень…
Алгоритм победителя использует метод блочного решета эратосфена с предподсчётом на 64 значения. фактически, чем больше заранее рассчитанная таблица, тем меньшего, в среднем, размера блок элементов придётся проходить и тем быстрее будет работать реализация. Предподсчёт на 64 элемента, в среднем, ускоряет блочный алгоритм рассчёта в 128(или всё же в 64?) раз(а) относительно блочного решета без предподсчёта. Вся сила решения — в умении упаковать таблицу заранее просчитанных значений вместе с кодом распаковки и досчёта в 1к исходного кода.
например, простое блочное решето эратосфена, которое я отправил на конкурс:
оно же, с таблицей предподсчёта на 16 элементов, которое я так и не отправил:
Простое блочное решето, отправленное на конкурс, позволило занять 14 место. Версия с предподсчётом у меня работает, в худшем случае, ~17 раз быстрее. Что дало бы, примерно, 0,2 секунды и 7-5 место. Добавление таблицы предпросчёта до 64 значений даёт прирост примерно в 5-6 раз, что даёт примерно 0,04 — 0,034 секунды, а именно, результат победителей.
например, простое блочное решето эратосфена, которое я отправил на конкурс:
блочное решето
#define PM (1 << 16)
#define CZ (1 << 16)
char c[CZ + 1];
int pp[PM + 1];
char v[PM + 1];
int pc = 0;
int64_t prime_r(int n)
{
// first primes
pc = 0;
memset(pp,0x00, PM*sizeof(int));
memset(v,0xff, PM*sizeof(char));
for(int i = 2; i*i < PM; i++) if(v[i])for(int j = i*i; j < PM; j += i)v[j] = 0;
for(int i = 2; i < PM; i++)if(v[i]) pp[pc++] = i;
// sum of prime
int64_t sum = 0;
for(int64_t i = 0; pp[i] <= n && i < pc; i++)sum += pp[i];
for (int64_t ii = pp[pc - 1]; ii <= n; ii += CZ)
{
memset(c,0xff, CZ*sizeof(char));
for(int64_t i = 0; i < pc; i++)
{
int h = ii % pp[i];
int j = (h > 0) ? pp[i] - h: 0;
for(; j < CZ; j += pp[i]) c[j] = 0;
}
int64_t si = ((ii + CZ) >= n) ? n - ii : CZ;
for(int64_t i = 0; i < si; i+=2) if(c[i]) sum += (i + ii);
}
return sum;
}
оно же, с таблицей предподсчёта на 16 элементов, которое я так и не отправил:
блочное решето с предподсчётом на 16 субблоков
#define PM (1 << 16)
#define CZ (1 << 16)
char c[CZ + 1];
int pp[PM + 1];
char v[PM + 1];
int pc = 0;
int64_t cum_16 [16] = {
0,
0x1c20fef2f09ca,
0x6c63d57586d96,
0xeec0010744a8e,
0x1a233866cf59db,
0x28618ac5327caa,
0x399e13d0ec9c4e,
0x4dd275b39fbecc,
0x64fa7e62f08931,
0x7f0f2d33432004,
0x9c0f0b992adb2e,
0xbbf49b7cf3b1fe,
0xdebe8bda61ec0f,
0x10467f40dc3f52f,
0x12ceee2b93e7816,
0x158524685365cc7
};
int64_t prime_rr16(int n)
{
// first primes
pc = 0;
memset(pp,0x00, PM*sizeof(int));
memset(v,0xff, PM*sizeof(char));
for(int64_t i = 2; i*i < PM; i++) if(v[i])for(int64_t j = i*i; j < PM; j += i)v[j] = 0;
for(int64_t i = 2; i < PM; i++)if(v[i]) pp[pc++] = i;
// sum of prime
int64_t sum = 0;
for(int64_t i = 0; pp[i] <= n && i < pc; i++)sum += pp[i];
int64_t s = (n >> 27)? (n & 0xf8000000) + 1 : pp[pc-1];
if(n >> 27) sum = 0;
sum += cum_16[n >> 27];
for (int64_t ii = s; ii <= n; ii += CZ)
{
memset(c,0xff, CZ*sizeof(char));
for(int64_t i = 0; i < pc; i++)
{
int64_t h = ii % pp[i];
int64_t j = (h > 0) ? pp[i] - h: 0;
for(; j < CZ; j += pp[i]) c[j] = 0;
}
int64_t si = ((ii + CZ) >= n) ? n - ii : CZ;
for(int64_t i = 0; i < si; i+=2) if(c[i]) sum += (i + ii);
}
return sum;
}
Простое блочное решето, отправленное на конкурс, позволило занять 14 место. Версия с предподсчётом у меня работает, в худшем случае, ~17 раз быстрее. Что дало бы, примерно, 0,2 секунды и 7-5 место. Добавление таблицы предпросчёта до 64 значений даёт прирост примерно в 5-6 раз, что даёт примерно 0,04 — 0,034 секунды, а именно, результат победителей.
разница в три порядка — это круто.
Чудеса оптимизаций и предпросчетов. Мне вот интересно, много ли решений работают за рамками обозначенными заданием. Посмотреть бы, сколько чисел успеет посчитать, если ограничить временем в 60секунд, найти постепенно поднимая входное число.
Не знал, что блочное решето настолько быстрее обычного линейного.
ЗЫ большинство участников, похоже, read-only. Хороший стимул.
Не знал, что блочное решето настолько быстрее обычного линейного.
ЗЫ большинство участников, похоже, read-only. Хороший стимул.
Расстроил вердикт «Ошибка компиляции», хотя всё равно в лучшем случае было бы место 80е.
Странно, по той ссылке, которая рекомендовалась для проверки компилируемости ошибок не было выявлено, или я чего-то не понял.
Странно, по той ссылке, которая рекомендовалась для проверки компилируемости ошибок не было выявлено, или я чего-то не понял.
Видимо вы послали одно, а тестировали другое. Сообщения об ошибках компилятора лежат в архиве:
6_main.cpp:13:3: error: unknown type name '__int64'; did you mean '__int64_t'?
__int64 s=0;
^~~~~~~
__int64_t
/usr/include/x86_64-linux-gnu/bits/types.h:44:25: note: '__int64_t' declared here
typedef signed long int __int64_t;
^
1 error generated.
А скрипт забора почты (по pop3 или imap) и сохранения вложения не быстрее ли было нагуглить, чем руками две сотни писем разгребать?
А мне интересно, что же такое замутил mrigi с «попыткой работать с отсутствующей сетью»
Отправку данных на свой суперкомпьютер, стоящий в подвале?
Кстати да, опубликуйте! Интересно же.
Кстати да, опубликуйте! Интересно же.
Может быть у него ботнет из 10000 компьютеров был подготовлен? В правилах же это никак не оговаривалось.
Исходные тексты опубликованы ( 3.14.by/files/solutions.zip ), только IP на всякий случае зацензурен. В принципе, в десятку сетевое решение mrigi попадало :-)
Было еще одно решение с сетью — gribozavr -а, но он сразу написал что там сеть :-)
Было еще одно решение с сетью — gribozavr -а, но он сразу написал что там сеть :-)
Дык посмотрите его решение. Оно там есть в архиве.А если кому лень смотреть, то вот оно: paste.org.ru/?mcvbey
Жаль, что айпишник CENSORED. Из-за этого я не могу проверить работу этой прожки
Жаль, что айпишник CENSORED. Из-за этого я не могу проверить работу этой прожки
Спасибо за инвайт!
Не думал, что заберусь так высоко. Наверно мне повезло с тестами (у меня не монотонно возрастает время работы с ростом n) — на худшем для меня тесте мое решение работает 0.6 с на моей машине.
Суть решения описана в комментарии в самом решении. Если подробно — тупое блочное решето, вообще без оптимизаций, почти идентичное реализации с e-maxx. Всего блоков получилось порядка 7000, с шагом в 350 блоков я предпосчитал ответы. Теперь для первых 350*x блоков ответ берем из таблицы, а для оставшихся не более чем 350 блоков досчитываем блочным решетом.
Все константы подобраны эмпирически.
Думаю, у других топовых решений что то подобное и страшный текст кракозябрами — это просто сжатые предпросчитанные ответы.
Мое решение можно было еще соптимизировать мелкими оптимизациями (ускорение раза в 2-3), но я особо не заморачивался. К сожалению, новый год встретил с насморком и температурой и на всякие извращения уже не было сил.
Не думал, что заберусь так высоко. Наверно мне повезло с тестами (у меня не монотонно возрастает время работы с ростом n) — на худшем для меня тесте мое решение работает 0.6 с на моей машине.
Суть решения описана в комментарии в самом решении. Если подробно — тупое блочное решето, вообще без оптимизаций, почти идентичное реализации с e-maxx. Всего блоков получилось порядка 7000, с шагом в 350 блоков я предпосчитал ответы. Теперь для первых 350*x блоков ответ берем из таблицы, а для оставшихся не более чем 350 блоков досчитываем блочным решетом.
Все константы подобраны эмпирически.
Думаю, у других топовых решений что то подобное и страшный текст кракозябрами — это просто сжатые предпросчитанные ответы.
Мое решение можно было еще соптимизировать мелкими оптимизациями (ускорение раза в 2-3), но я особо не заморачивался. К сожалению, новый год встретил с насморком и температурой и на всякие извращения уже не было сил.
>>C#: Один случай.
Видимо, тяжелый.
// 4-поточный аткинс без предподсчётов — 44 место.
Видимо, тяжелый.
// 4-поточный аткинс без предподсчётов — 44 место.
Если распечатать содержимое массива u после распаковки, то там наверняка будет что-то типа этого:
...::[ HAI THERE GUISE! ]::… === ...::[ SHADEWARE PROUDLY PRESENTS THIS SOLUTION TO HABRAHABR CHALLENGE! ]::… === ...::[ GREETZ TO:
...::[ HAI THERE GUISE! ]::… === ...::[ SHADEWARE PROUDLY PRESENTS THIS SOLUTION TO HABRAHABR CHALLENGE! ]::… === ...::[ GREETZ TO:
Спасибо за новогодний контест! Было весело.
Мое решение представляет собой многопоточное блочное решето Эратосфена с предподсчетом. Идея следующая — разобьем отрезок допустимых значений инпута на равные части и подсчитаем в этих точках ответ. Тогда можно искать сумму простых только в интервале от ближайшего известного числа до n (или наоборот, в зависимости от того что ближе). В блочном решете это значит что нужно обрабатывать только те блоки, которые затрагивают эту область. Простые до корня из n нам придется найти в любом случае, но это быстро.
Ну и блоки обрабатываются независимо, поэтому запустим их в нескольких потоках. На моем двухъядерном ноутбуке это давало прирост скорости примерно в полтора раза.
Сдается мне, что, возможно, выгоднее было бы убрать потоки, а на освободившиеся символы запихать побольше предподсчета, что по видимости и сделал победитель =)
Более читаемое решение: http://pastebin.com/jjkpDNin
Мое решение представляет собой многопоточное блочное решето Эратосфена с предподсчетом. Идея следующая — разобьем отрезок допустимых значений инпута на равные части и подсчитаем в этих точках ответ. Тогда можно искать сумму простых только в интервале от ближайшего известного числа до n (или наоборот, в зависимости от того что ближе). В блочном решете это значит что нужно обрабатывать только те блоки, которые затрагивают эту область. Простые до корня из n нам придется найти в любом случае, но это быстро.
Ну и блоки обрабатываются независимо, поэтому запустим их в нескольких потоках. На моем двухъядерном ноутбуке это давало прирост скорости примерно в полтора раза.
Сдается мне, что, возможно, выгоднее было бы убрать потоки, а на освободившиеся символы запихать побольше предподсчета, что по видимости и сделал победитель =)
Более читаемое решение: http://pastebin.com/jjkpDNin
Пока победитель не написал, скажу, что его решение достаточно простое и используется обычное решето с бит сетом. Другое дело, что сумма простых чисел считается от ближайшего кратного ~16млн (1<<24) числа. То есть все суммы 1, 16млн, 32млн,… загнаны в предрасчет. А уже начиная от этих предрасчитаных сум нужно найти все простые до n и их сумму. Как-то так. Мне понравилась идея.
Думаю, что многопоточное решение всё-таки будет быстрее: у победителя каждое значение таблицы на 64 значения занимает 7 байтов, следовательно, уменьшение таблицы в 2 раза освободит 224 байта (или 192, если кодировка значения станет занимать 8 байтов) — мне кажется этого достаточно для реализации многопоточности.
Таким образом, 2-кратное увеличение обсчитываемого интервала должно с лихвой компенсироваться 4 потоками.
Таким образом, 2-кратное увеличение обсчитываемого интервала должно с лихвой компенсироваться 4 потоками.
Только сжать в 2 раза не получится. Простые числа — очень сложно ведущая себя последовательность, взять хотя бы расширенную гипотезу Римана. (Исходя из неё эта сумма будет порядка N^2/(2*ln(n)) и там будет достаточно случайный член порядка N^3/2, т.е. сжать можно максимум на 25%).
Наверное вы меня не поняли. Я предлагаю просто выкинуть из таблицы каждое второе значение и работать с шагом 1<<25. Это вообще не влияет на плотность упаковки вашего решения, да и у победителя гарантировано оставляет лишние 192 байтов на имплементацию многопоточности.
Да, в среднем надо будет просчитать в 2 раза больше, но зато это распределится на 4 потока, что, как мне кажется, должно улучшить среднее время.
Да, в среднем надо будет просчитать в 2 раза больше, но зато это распределится на 4 потока, что, как мне кажется, должно улучшить среднее время.
Для N<10^9 суммы простых с шагом 2^24 можно закодировать, используя значения, не превышающие 10^12 (например, первые разности последовательности S(N)-0.5126*N^2/ln(N), возможно еще минус константа). Так что в 6 байт в 96-ричной системе уложиться можно (старший байт может вылезти за 127, но тогда его можно честно записать как \2??). Третьи разности S(N) тоже почти не выходят за 10^12.
Да, кстати, на intel i7 на самом деле можно выполнять 8 потоков одновременно и иметь при этом выйгрыш в производительности.
То есть ядра-то 4, но потоков 8.
Во-первых, так сказано на сайте intel.
А во-вторых, я проверял у себя на компе (у меня тоже i7), максимальная производительность на 8 потоках получается.
То есть ядра-то 4, но потоков 8.
Во-первых, так сказано на сайте intel.
А во-вторых, я проверял у себя на компе (у меня тоже i7), максимальная производительность на 8 потоках получается.
Моя идея совпадает с этим комментом.
Только у меня 64 блока и несколько более эффективная реализация(которую, тем не менее, можно еще ускорить в несколько раз, было бы время).
Менее обфусцированный код
Только у меня 64 блока и несколько более эффективная реализация(которую, тем не менее, можно еще ускорить в несколько раз, было бы время).
Менее обфусцированный код
Впечатляет. Всемогущие хабралюди разгадали мой код быстрее меня самого. И они ни в чем не ошиблись, я лишь добавлю небольшое замечание.
Я заметил, что некоторые люди писали ручные битсеты. Зачем? vector_bool вполне быстр. Когда я ради интереса заменил его на vector_char, скорость просела в несколько раз. Мораль: доверяйте STL.
Также хотелось бы поблагодарить автора конкурса за отличную задачу и современные условия.
Я заметил, что некоторые люди писали ручные битсеты. Зачем? vector_bool вполне быстр. Когда я ради интереса заменил его на vector_char, скорость просела в несколько раз. Мораль: доверяйте STL.
Также хотелось бы поблагодарить автора конкурса за отличную задачу и современные условия.
А можно вас попросить поделиться кодом, генерирующим 448-байтный «стринг» из массива? :)
Скрытый текст
#include <iostream>
#include <algorithm>
#include <string>
#include <iterator>
int main()
{
std::vector<long long> arr
(
( std::istream_iterator<long long>(std::cin) ),
std::istream_iterator<long long>()
);
for (int i = arr.size() - 1; i > 1; --i)
{
arr[i] -= 2 * arr[i - 1] - arr[i - 2];
}
for (auto x : arr)
{
std::string str;
for (; x; x /= 96)
{
str += char(x % 96 + 32);
if ( std::string("\\\"\'").find(str.back()) != std::string::npos)
str += '\\';
}
std::cout << std::string(str.rbegin(), str.rend());
}
}
Результат (на этом же сайте, я, кстати, тестировал свой код).
У меня тоже решето с предподсчетом. Компилятор ругался, потому что я использовал символы с кодами больше 127. Решение старался сделать максимально прозрачным) Кстати, кто еще хочет порешать похожие задачи, но килобайта мало, есть трудная задача как раз на блочное решето: www.spoj.com/problems/PRIMES2/. Учтите, там Pentium 3!
как раз хотел спросить, как так удачно получилось у победителя, что в строковой константе все символы оказались «легальными»
уже увидел
А я не совсем понял — там удачно не оказалось кода 127, или он записан как \177 (всю строку просматривать лень). Просто в ASCII-7 есть 94 а не 95 непробельных символа, так что системе счисления следовало бы быть 95.
Символ 127 там есть, и ничего плохого от этого не случилось. Мне не важна графическая интерпретация строки, мне нужно было закодировать предподсчёт.
Строго говоря, компилятор не обязан допускать во входном коде символы за пределами extended character set. Clang ориентирован на UTF-8, поэтому на не-UTF-8 он ругается. (А мог бы и вообще ошибку кидать — и был бы прав.)
Все в пределах Extended ASCII Codes. Я компилировал перед отправкой, ошибок не было. Да, я понимаю, что это недопустимо в промышленном программировании, но эта задача имеет олимпиадный характер.
Что такое Extended ASCII Codes? (Такого понятия нет в стандарте.) Я понимаю что ошибок не было, но это добрая воля компилятора (по стандарту он мог бы и отказаться это компилировать).
Я имел в виду extended character set. К чему строгое следование стандарту в данной конкретной задаче? Согласно стандарту, компилятор много чего мог сделать, но это не значит, что он должен по-умолчанию придираться ко всему подряд.
Инициализации целочисленных переменных нулём по умолчанию тоже нет в стандарте, всем участникам повезло :)
Вы правы! Я вчера прогнал топовые решения под AddressSanitizer, Undefined Behavior Sanitizer — ничего не нашёл и совсем забыл про Memory Sanitizer. Как оказалось, зря — там всё плохо.
В решениях bklim, dark1ight, Icemore, madkite, MaSaK, Mrrl, ripatti, udalov, vbarinov, VladVR, ZhekSooN есть использование значений неинициализированных переменных.
В решениях bklim, dark1ight, Icemore, madkite, MaSaK, Mrrl, ripatti, udalov, vbarinov, VladVR, ZhekSooN есть использование значений неинициализированных переменных.
Что такое UTF-8 последовательность? Clang поругался только на 2 символа, что в них особенного? При ограничении в 1024 байта естественно ожидать от участников экономии кода исходя из предположений, которые при данных ключах компиляции почти всегда верны. Да, я согласен, что предупреждения игнорировать не стоит, но в данной задаче это не критично. Лучше поищите логические ошибки в программах, это сложнее и увлекательнее, так как тестов было мало, наверняка они есть.
Clang ругался на две строчки, со многими символами в каждой. pastebin.com/t7L3q67H — он подчёркивает всё, что не UTF-8.
Термин «UTF-8 последовательность» — согласно спецификации Unicode (в версии 6.2 это определение D86 в главе 3).
Термин «UTF-8 последовательность» — согласно спецификации Unicode (в версии 6.2 это определение D86 в главе 3).
Всмысле? Ткните мне переменную, которая используется без инициализации.
Глобальные переменные по умолчанию инициализируются нулями. Из стандарта:
«Objects with static storage duration (3.7.1) shall be zero-initialized (8.5) before any other initialization takes place.»
В остальных переменных, конечно же, по умолчанию мусор. Однако каждой из этих переменных всегда присваивается не мусорное значение до того, как значение этой переменной будет где либо использовано. Или так делать нельзя? Если да, то почему?
Глобальные переменные по умолчанию инициализируются нулями. Из стандарта:
«Objects with static storage duration (3.7.1) shall be zero-initialized (8.5) before any other initialization takes place.»
В остальных переменных, конечно же, по умолчанию мусор. Однако каждой из этих переменных всегда присваивается не мусорное значение до того, как значение этой переменной будет где либо использовано. Или так делать нельзя? Если да, то почему?
Я сильно извиняюсь, совсем забыл что для MemorySanitizer нужно использовать инструментированную стандартую библиотеку C++, а я использовал обычную — отсюда ложное срабатывание (считалось что n не инициализирована, но она инициализируется кодом в стандартной библиотеке во время чтения из cin). Перпроверил — в вашей программе всё ОК, остальные не перепроверял.
А где это в моём решении «использование значений неинициализированных переменных»? Просто любопытно. Я думаю, передачу указателя в scanf Вы не считаете таковым использованием? ;)
Все остальные переменные у меня инициализируются, а память под массив выделяется с помощью calloc (который по man-у инициализирует память нулями).
Все остальные переменные у меня инициализируются, а память под массив выделяется с помощью calloc (который по man-у инициализирует память нулями).
Извините, я использовал неправильную стандартную библиотеку и получил ложные срабатывания: habrahabr.ru/post/164567/#comment_5668261
Перепроверил ваше решение — всё ОК.
Перепроверил ваше решение — всё ОК.
Я бухал и все пропустил ((
Странно, почему никто не спрашивает:
К чему эти пляски с Clang, чем вас не устроил более распространенный (и быстрый) gcc?
Зачем нужны искусственные ограничения на размер решения? Видимо, раз задача при искусственных же ограничениях на тесты сводится к предподсчету, то она не очень удачна для соревнования по алгоритмам. Победителям пришлось прогонять код через обфускатор — это как бы намекает.
К чему эти пляски с Clang, чем вас не устроил более распространенный (и быстрый) gcc?
Зачем нужны искусственные ограничения на размер решения? Видимо, раз задача при искусственных же ограничениях на тесты сводится к предподсчету, то она не очень удачна для соревнования по алгоритмам. Победителям пришлось прогонять код через обфускатор — это как бы намекает.
Если бы не было ограничения на 1024 байта, то решения были бы более сложными, замысловатыми, использовали бы больше оптимизаций и пр. Тогда бы открывался бы ещё больший простор для предподсчёта. Было бы разумно использовать всякие сложные алгоритмы. В общем, задача была бы мега-сложная, пришлось бы кодить 5 часов, а то и все 24, чтобы можно было дать конкурентноспособное решение.
В общем, в этом конкурсе вся суть в том, чтобы написать решение так, чтоб оно было коротким. А то можно было бы, скажем, копирнуть какую-нибудь профессиональную программу. Например, статья на вики про решето Аткина ссылается на домашнюю страницу второго автора этого решета (Бернштейна). Там лежит его собственная реализация алгоритма: cr.yp.to/primegen.html. Какой-нибудь хабравчанин мог бы просто копирнуть эту прожку.
В общем, в этом конкурсе вся суть в том, чтобы написать решение так, чтоб оно было коротким. А то можно было бы, скажем, копирнуть какую-нибудь профессиональную программу. Например, статья на вики про решето Аткина ссылается на домашнюю страницу второго автора этого решета (Бернштейна). Там лежит его собственная реализация алгоритма: cr.yp.to/primegen.html. Какой-нибудь хабравчанин мог бы просто копирнуть эту прожку.
Мне кажется лучше подошла бы задача на строки (может даже онлайновая), или графы, или запросы на отрезке (поле для оптимизации структуры). В таких задачах предподсчет вряд ли возможен.
Чтобы люди не убивались 24 часа, можно заранее объявить время публикации условий и закрыть прием решений через 3-5 часов. Как, собственно, давно и делают онлайн-площадки соревнований по программированию.
Чтобы люди не убивались 24 часа, можно заранее объявить время публикации условий и закрыть прием решений через 3-5 часов. Как, собственно, давно и делают онлайн-площадки соревнований по программированию.
Так и не нужно было убиваться 24 часа, сели, за час написали — и дальше праздновать :-)
А насчет clang — за ним будущее, да и полезно вспомнить что компиляторы бывают разные.
А насчет clang — за ним будущее, да и полезно вспомнить что компиляторы бывают разные.
Победители потратили явно не час. Поэтому чтобы люди писали час, надо и ограничение такое поставить.
Я думаю у них нужно спросить, сколько они потратили )
И никто не мешает иметь домашние заготовки. Задача поиска всех простых чисел на интервале довольно часто встречается в олимпиадном программировании. Я думаю, в той или иной формулировки top таблицы с этой задачей уже сталкивался.
Я потратил все 24 часа (с учётом около 8-часового сна, еды и пр.). Я думаю, 4 часа точно кодил.
Я думаю, будущее не за clang. Всё-таки, gcc — это стандарт в мире свободного ПО и мире бизнеса. Никто не станет просто так пересаживаться на clang.
Без ограничений на размер решения была бы жесть! Можно написать решение за
~N^0.5 с предподсчетом за ~N(асимптотики с точностью до логарифмов). И тогда отделить решения было бы очень трудно. Я ничего не обфусцировал, и если бы написал цикл в 19 строчке не до N, а до (n-x+1)/2, то скорее всего, выиграл бы.
Спасибо за инвайт! (я на 6 месте в таблице).
Ох, похоже, что моё решение — самое быстрое из тех, что не использует предпросчёт (хех, пока тут не сказали, я и не догадывался, за счёт чего меня обходят более чем в четыре раза). Особой магии у меня нет, всё то же блочное решето, распараллеленное на 4 потока, каждый поток обрабатывает один из возможных остатков по модулю 12 (1, 5, 7, 11). Похоже, можно было ускорить ещё раза в полтора, взяв 8 потоков и простые остатки по модулю 30.
Ох, похоже, что моё решение — самое быстрое из тех, что не использует предпросчёт (хех, пока тут не сказали, я и не догадывался, за счёт чего меня обходят более чем в четыре раза). Особой магии у меня нет, всё то же блочное решето, распараллеленное на 4 потока, каждый поток обрабатывает один из возможных остатков по модулю 12 (1, 5, 7, 11). Похоже, можно было ускорить ещё раза в полтора, взяв 8 потоков и простые остатки по модулю 30.
Захотел провести альтернативное тестирование (среди первых 21). На тех же самых тестах, используя ту же самую методику запуска, проверки и измерения времени (на php). Вот такая тестирующая машинка:
Видим, что всё то же самое (linux x64 и clang 3.2), только процессор немного другой фирмы.
Получил я такие результаты (последнее число — суммарное время по 4-м тестам):
1 shadeware 0.20930314064026
2 mikhaelkh 0.25842094421387
3 kbxxi 0.65344190597534
4 ripatti 0.80067110061646
5 Icemore 0.82941699028015
6 Zver1992 1.9382400512695
7 monoid 2.2213151454926
8 Mrrl 3.3820571899414
9 Staker 3.9848639965057
10 SyDr 4.081221818924
11 madkite 16.979673147202
12 udalov 20.033820152283
13 bklim 21.501169919968
14 cfighter 22.276267766953
15 vanla 23.618012905121
16 ZhekSooN 24.388655185699
17 MaSaK 24.595273017883
18 VladVR 25.226194143295
19 dark1ight 26.574873924255
20 vbarinov 26.777559995651
21 borozdinKirill 33.735852956772
Не ожидал, что результаты будут настолько отличаться. Хотя первые два решения остались на местах.
Повторные запуски дают ту же картину.
Если кто хочет проверить у себя (а интересно посмотреть на результаты, полученные на других процессорах), то вот архив с решениями и тестирующими скриптами, которые я использовал. Там просто запустить ./test.sh (в linux x64, разумеется). В случае проблем попробовать перекомпилить с помощью ./compile.sh
$ uname -a
Linux moon 3.6.10-1-ARCH #1 SMP PREEMPT Tue Dec 11 09:40:17 CET 2012 x86_64 GNU/Linux
$ clang -v
clang version 3.2 (tags/RELEASE_32/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix
$ cat /proc/cpuinfo | grep -F 'model name' | head -1
model name: AMD FX(tm)-6100 Six-Core Processor
Видим, что всё то же самое (linux x64 и clang 3.2), только процессор немного другой фирмы.
Получил я такие результаты (последнее число — суммарное время по 4-м тестам):
1 shadeware 0.20930314064026
2 mikhaelkh 0.25842094421387
3 kbxxi 0.65344190597534
4 ripatti 0.80067110061646
5 Icemore 0.82941699028015
6 Zver1992 1.9382400512695
7 monoid 2.2213151454926
8 Mrrl 3.3820571899414
9 Staker 3.9848639965057
10 SyDr 4.081221818924
11 madkite 16.979673147202
12 udalov 20.033820152283
13 bklim 21.501169919968
14 cfighter 22.276267766953
15 vanla 23.618012905121
16 ZhekSooN 24.388655185699
17 MaSaK 24.595273017883
18 VladVR 25.226194143295
19 dark1ight 26.574873924255
20 vbarinov 26.777559995651
21 borozdinKirill 33.735852956772
Не ожидал, что результаты будут настолько отличаться. Хотя первые два решения остались на местах.
Повторные запуски дают ту же картину.
Если кто хочет проверить у себя (а интересно посмотреть на результаты, полученные на других процессорах), то вот архив с решениями и тестирующими скриптами, которые я использовал. Там просто запустить ./test.sh (в linux x64, разумеется). В случае проблем попробовать перекомпилить с помощью ./compile.sh
Вот что кеш животворящий делает :-)
Также полагаю влияет и то, что ваш процессор состоит из 3-х пар ядер — оптимизация многопоточных приложений должна быть другая, что и продемонстрировало ухудшение времени работы многопоточного решения от icemore.
Также полагаю влияет и то, что ваш процессор состоит из 3-х пар ядер — оптимизация многопоточных приложений должна быть другая, что и продемонстрировало ухудшение времени работы многопоточного решения от icemore.
Мне кажется, что дело ещё в скорости RAM. Забыл сказать, что у меня 1866MHz (на i7 у Вас максимум 1600MHz). Но зато, как Вы заметили, кэша меньше. В итоге моё решение (обычное решето, где кэш почти не используется, а скорость памяти очень важна) «поднялось» с 21-го до 11-го, обойдя решения с блочным решетом (где не так активно гуляют по памяти, а больше по кэшу).
Смотря на коды первых 2-х мест, так и хочется сказать авторам — «Вы ЗВЕРИ!»
Хочется порадоваться, что еще есть люди, способные на такое.
Главное, чтобы в коде для продакшна такого не было.
Если его эквивалент будет в микропроцессоре, где всего 1 килобайт ПЗУ — то чем это плохо?
Не хочу открывать холиварный коммент, однако хочется сказать: на таких вот примерах можно показать, для чего нужна алгоритмистика в программировании. А то некоторые люди считают, что если есть пузырьковая сортировка, то про qsort можно уже не знать, не говоря уже про какой-нибудь radix sort.
По мне, так это как раз не очень показательный пример :) Многие скажут: «Как мне это пригодиться на практике?», т.к. вряд ли большинство программистов сталкивается с реализацией теоретико-числовых алгоритмов (за исключением людей, которые занимаются криптографией). Гораздо лучше смотрелась бы задачка на нестандартную структуру данных.
А вообще, программирование — частный случай алгоритмистики, которая, в свою очередь, частный случай дискретной математики.
А вообще, программирование — частный случай алгоритмистики, которая, в свою очередь, частный случай дискретной математики.
Так тут практики гораздо больше чем кажеться — на непортабельном C++ коде срезалось участников больше, чем с неправильным алгоритмом.
Ну, я больше говорил про «алгоритмистику в общем».
Если, например, писать высоконагруженный игровой сервер, работающий в режиме критической многопоточности, разница 0.025 с. или 25 с. на какой-то операции может означать, будет сервер держать 10 или 1000 одновременных активных игроков. А это фактически будет означать, сможет ли проект жить (геймплей тут не беру в расчет).
Привел такой пример, т.к. знаю не еденичный случай, когда из-за того, что серверные разработчики забыли про теорию графов, хоронился проект, а иногда и игровая студия вместе с ним. Какие были убытки уж вообще молчу…
Если, например, писать высоконагруженный игровой сервер, работающий в режиме критической многопоточности, разница 0.025 с. или 25 с. на какой-то операции может означать, будет сервер держать 10 или 1000 одновременных активных игроков. А это фактически будет означать, сможет ли проект жить (геймплей тут не беру в расчет).
Привел такой пример, т.к. знаю не еденичный случай, когда из-за того, что серверные разработчики забыли про теорию графов, хоронился проект, а иногда и игровая студия вместе с ним. Какие были убытки уж вообще молчу…
Да, это же теория графов, она частенько бывает полезна. Ее даже можно назвать теоретическим минимумом для программиста. Я же говорю про теоретико-числовые алгоритмы, которые вообще непонятно как применять на практике. Можно решать только специально выдуманные задачи, т.е. «задача ради задачи».
Ну а в целом я с вами согласен, алгоритмы нужно знать и уметь применять.
Ну а в целом я с вами согласен, алгоритмы нужно знать и уметь применять.
Действительно, задачи, связанные с простыми числами, почти не встречаются (если не рассматривать криптографию). Мне они попадались либо когда были нужны точные вычисления (особенно, гарантированное сравнение с нулём — например, метод Гаусса или базис Грёбнера, ведомые многомодульной арифметикой — ну, или многомодульная арифметика сама по себе), либо когда структура конечного поля была удобна для задания какого-то графа (фрагмент решетки на плоскости Лобачевского).
Но это в production коде. При разработке (поиск подходящих параметров, конфигураций и т.п.) они встречаются чаще, но там важнее их быстро и правильно написать, чем добиваться эффективности.
На практике поиск простого числа ещё используется при реализации Hashtable в .NET…
Но это в production коде. При разработке (поиск подходящих параметров, конфигураций и т.п.) они встречаются чаще, но там важнее их быстро и правильно написать, чем добиваться эффективности.
На практике поиск простого числа ещё используется при реализации Hashtable в .NET…
Считайте меня занудой, но повторю свою мысль из стартового топика:
Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.
Я сам поленился участвовать, да и смотря на код победителей понимаю, что не мог бы рассчитывать на высокие места. Но мне всё равно хочется, чтобы победитель определялся на основании более обширных тестов, исключающих случайность. И хотя я уверен, что 1-2 места в любом случае останутся за shadeware и mikhaelkh (респект!!!), их же код, но с более плотной таблицей в верхней четвети диапазона был бы наверняка ещё быстрее на данных тестах, немотря на «провал» в области непосредственно перед таблицей.
Среднее время ТОП-3 менее 0.1 с — гораздо более показательными были бы 1000 и даже 10000 тестов на разных(!) значениях.
Также мне был бы интереснен рэнкинг «по худшему времени» — после обфускации большинство решений легко укладываются в 1024 байта, и для дальнейшего ускорения используют таблицу предварительно вычисленных значений. Это значит, что худшее время программы не так просто найти (хотя и не так сложно, учитывая небольшое число возможных локальных максимумов). Но на мой взгляд этот рэнкинг очень показательный.
Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.
Я сам поленился участвовать, да и смотря на код победителей понимаю, что не мог бы рассчитывать на высокие места. Но мне всё равно хочется, чтобы победитель определялся на основании более обширных тестов, исключающих случайность. И хотя я уверен, что 1-2 места в любом случае останутся за shadeware и mikhaelkh (респект!!!), их же код, но с более плотной таблицей в верхней четвети диапазона был бы наверняка ещё быстрее на данных тестах, немотря на «провал» в области непосредственно перед таблицей.
Среднее время ТОП-3 менее 0.1 с — гораздо более показательными были бы 1000 и даже 10000 тестов на разных(!) значениях.
Также мне был бы интереснен рэнкинг «по худшему времени» — после обфускации большинство решений легко укладываются в 1024 байта, и для дальнейшего ускорения используют таблицу предварительно вычисленных значений. Это значит, что худшее время программы не так просто найти (хотя и не так сложно, учитывая небольшое число возможных локальных максимумов). Но на мой взгляд этот рэнкинг очень показательный.
Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.
Ну, вообщем, так и случилось. BarsMonster должен был рассказать про способ оценивания решения подробнее в своем предыдущем посте. Я думал, что нужно минимизировать худшее время работы, как это обычно надо в олимпиадном программировании. У меня код во многом похож с shadeware, тоже предподсчет 64 значений но, в отличии от него есть оптимизация, выкидывающая все четные числа. Я все время считал весь массив, и это стоило мне 1 места, так как в тестах в среднем надо было посчитать 0.41 массива, как результат — мой код на 12% медленнее. Если бы я написал цикл в 19 строчке не до N, а до (n-x+1)/2, то программа заработала в 2 раза быстрее.
Значит все как в жизни — помимо корректной реализации нужны еще и верные предположения :-)
Кстати, вы не думали распределять таблицу не равномерно?
Ведь просеивание последних блоков занимает больше времени (число проходов растёт O(sqrt(N) / ln(N))).
Заодно и количество значений может быть любым, а не только степенью 2, позволяя использовать практически каждый свободный байт.
Ведь просеивание последних блоков занимает больше времени (число проходов растёт O(sqrt(N) / ln(N))).
Заодно и количество значений может быть любым, а не только степенью 2, позволяя использовать практически каждый свободный байт.
Да, у меня были далеко не идеальные оптимизации. По правде говоря, я вообще не ожидал, что выиграю.
Я стремился к чему-то такому.
Данный код работает в худшем случае в ~3 раза быстрее, чем то, что я послал на конкурс. Среднее же время вообще стремится к нулю. И исходник все еще можно обфусцировать до 1024 байт(изменилось не так уж и много).
Я стремился к чему-то такому.
Скрытый текст
//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstdlib>
int main()
{
//especially for
http://habrahabr.ru
//расшифровка предподсчета
long long precalc[66] = {};
for (int i = 0; i < 64 * 7; i++)
{
precalc[i / 7 + 2] = precalc[i / 7 + 2] * 96 + "+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL05Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i] - 32;
}
for (int i = 0; i < 64; i++)
{
precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
}
int n;
scanf("%d", &n);
long long answer;
int left;
if (n & (1 << 23) ) //n ближе к правой границе блока
{
answer = -precalc[(n >> 24) + 2];
//так как answer отрицательный, модуль числа будет уменьшатся
//при сложении, следовательно, основной код не изменится.
left = (n >> 24 << 24) + (1 << 24);
std::swap(left, n);
++left;
}
else //n ближе к левой границе
{
left = n >> 24 << 24;
if (left == 0)
{
answer = 2 * (n > 1);
}
else
{
answer = precalc[(n >> 24) + 1];
}
}
int sq = sqrt(n) + 1e-7;
//уменьшаем в 2 раза все переменные, так как четные числа учитываться не будут
n = (n - 1) / 2;
left /= 2;
sq /= 2;
std::vector<bool> sieve(sq + 1), block(n - left + 1);
block[0] = !left;
//блочное решето
for (int i = 1; i <= sq; ++i)
{
if (!sieve[i])
{
//просеивание до корня
//так как i уменьшено в 2 раза, то исходное i = 2 * i + 1
//i * i -> 2 * i * (i + 1)
for (int j = 2 * i * (i + 1); j <= sq; j += 2 * i + 1)
{
sieve[j] = 1;
}
//просеивание блока
int j;
//вычисление левой границы, от которой будем просеивать
if (left == 0)
{
j = 2 * i * (i + 1);
}
else
{
//находим первое j, которое кратно i && >= left
j = 2 * (left + i);
j -= j % (2 * i + 1);
//просеивать четные числа ни к чему, они будут пропускаться
if (j % 2 == 0)
{
j += 2 * i + 1;
}
j /= 2;
}
for (; j <= n; j += 2 * i + 1)
{
block[j - left] = 1;
}
}
}
//подсчет ответа
for (int i = 0; i <= n - left; ++i)
{
if (!block[i])
{
answer += i * 2 + left * 2 + 1;
}
}
printf("%lld", std::llabs(answer));
}
Данный код работает в худшем случае в ~3 раза быстрее, чем то, что я послал на конкурс. Среднее же время вообще стремится к нулю. И исходник все еще можно обфусцировать до 1024 байт(изменилось не так уж и много).
2-кратное изменение понятно, а дальше за счёт чего? Из-за вдвое меньшей используемой памяти?
Кстати, для относительно небольших N, можно «подбирать» корень — это дольше, но пренебрежимо мало по сранвению с остальным кодом. Зато позволяет сэкономить место.
вместо
Кстати, для относительно небольших N, можно «подбирать» корень — это дольше, но пренебрежимо мало по сранвению с остальным кодом. Зато позволяет сэкономить место.
for(;++q*q<n;);
вместо
#include <cmath>
q=sqrt(n)+1e-7;
Из-за вдвое меньшей используемой памяти?
В том числе. Это позволяет переписать циклы, чтобы счетчик инкрементился, а не увеличивался на два. Ну и еще компилятор лучше оптимизирует такие циклы.
Также при просеивании теперь пропускаются четные значения, и само просеивание начинается с i * i (вместо 2-3 * i).
++q*q<n
Это же undefined behavior :)
Я знаю про это, но недостатка в байтах не было. К тому же, нужно как-то найти размер для решета(n / 2 — некошерно).
Ну хорошо, забирайте ваш байт: :)
Ещё может быть можно выцарапать пару байтов заменив
на
* Я не придираюсь — наоборот, ваше решение кажется мне настолько близким к совершенству, что не могу удержаться от попыток довести его до абсолюта :)
for(;q*q<n;++q);
Ещё может быть можно выцарапать пару байтов заменив
for (int i = 0; i < 64; i++)
{
precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
}
на
for (int i = 0; i < n>>24; i++)
{
answer = precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
}
* Я не придираюсь — наоборот, ваше решение кажется мне настолько близким к совершенству, что не могу удержаться от попыток довести его до абсолюта :)
A, ещё я не понял, зачем в «стринге» использовать
\' вместо '.0.018682479858398 секунды ;-)
BarsMonster А у меня на измененном коде сколько? В 19 строчке N заменить на n-x+1>>1
Там не
N, а n.
Решение в 165 байт, по времени укладывается.
Можно сэкономить 4 байта, пожертвовав 7-ю гигабайтами.
Можно сэкономить 4 байта, пожертвовав 7-ю гигабайтами.
#include<iostream>
char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(!p[i])for(j=i*i;j<=n;j+=i)p[j]=1;for(;n-->2;)s+=p[n]?0:n;std::cout<<s;}
164
#include<iostream>
char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(j=!p[i])for(;j++*i<=n;)p[j*i]=1;for(;n-->2;)s+=p[n]?0:n;std::cout<<s;}
при
n=2 ответ 2, у тебя 0. Ещё SIGSEGV при n = 1<<30.Пофиксил, и теперь
Я не очень знаю Си, вроде бы s+=!p[n]*n--; — это не случай неопределённого поведения, и всё ок т.к. приоритет [] выше, чем --?
163
#include<iostream>
char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(j=!p[i])for(;++j*i<=n;)p[j*i]=1;for(;n;)s+=!p[n]*n--;std::cout<<s-1;}
Я не очень знаю Си, вроде бы s+=!p[n]*n--; — это не случай неопределённого поведения, и всё ок т.к. приоритет [] выше, чем --?
Это UB, приоритеты тут не при чём.
Там нет UB. Выражения s+=!p[n]*n--; и s+=!p[n]*n;n--; будут равнозначными.
C11, 6.5 p2
If a side effect on a scalar object is unsequenced relative to either a different side effect
on the same scalar object or a value computation using the value of the same scalar
object, the behavior is undefined.
IMHO, ключевое is unsequenced может возникнуть в этом выражении s+=!p[n]*n-- только если определен, например, operator* — для параметров функции не определен порядок.
Признаю, вы правы, учитывая следующее
так и не удалось найти те самые исключения «Except where noted»
Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.
так и не удалось найти те самые исключения «Except where noted»
std::cin>>n можно внести внутрь forИ, раз памяти не жалко, вместо 1<<30 использовать 2е9
[] и постфиксный — имеют одинаковый приоритет.
long long не нужен, достаточно просто long.
На linux-x86_64 используется модель LP64, где long 64-разрядный, в отличие от LLP64 в Windows x64, где long — 32 бита, а long long — 64 бита.
На linux-x86_64 используется модель LP64, где long 64-разрядный, в отличие от LLP64 в Windows x64, где long — 32 бита, а long long — 64 бита.
Я правильно понимаю, что единицу не стоит считать как простое число?
Еще задачи на решето:
easy:
www.spoj.com/problems/TDPRIMES/
www.spoj.com/problems/TDKPRIME/
hard:
www.spoj.com/problems/PRIMES2/
www.spoj.com/problems/KPRIMES2/
Учтите, там Pentium 3, в 8 раз медленнее моего Core 2 Duo. Мои решения hard задач работают ~3 раза быстрее TL.
Кто заинтересовался, советую почитать:
code.google.com/p/primesieve/
easy:
www.spoj.com/problems/TDPRIMES/
www.spoj.com/problems/TDKPRIME/
hard:
www.spoj.com/problems/PRIMES2/
www.spoj.com/problems/KPRIMES2/
Учтите, там Pentium 3, в 8 раз медленнее моего Core 2 Duo. Мои решения hard задач работают ~3 раза быстрее TL.
Кто заинтересовался, советую почитать:
code.google.com/p/primesieve/
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение