Хотя я зарегистрировался в Codeforces около 3 недель назад, сегодня у меня есть время, чтобы испытать Codeforces.
Конечно же, это заставило меня прокатиться. Мне потребовалось время, чтобы найти, где я могу найти проблему из архива в режиме практики и представить решение. Это оказалась задача из Соревнования №600 Дивизион 2 с трудностью «А».
В Codeforces есть два дивизиона, один для профессионалов, который называется Дивизион 1. Дивизион 2 предназначен для людей, не участвующих в соревнованиях, или людей с рейтингом ниже 1900.
Задачи Дивизиона 2 легче понять и решить, чем задачи Дивизиона 1. В типичном конкурсе будет 7 задач с возрастающим уровнем сложности, отмеченными от «A» до «F». (Если вам интересно, он считается до 6, между пронумерованными E1 E2 возникнет проблема)
Я предпринял несколько попыток и решил проблему. Проблема была простой, но сложной, но она касалась деталей реализации, поскольку это более сложная проблема.
Это сильно отличается от программирования в повседневной рабочей среде, чем от платформы соревновательного программирования. Это возвращает меня к суровости моих школьных дней. Каждая проблема должна быть решена за определенное время и с учетом использования памяти.
Starting Competitive Programming — Steps and Mistakes
И прошел год или два с тех пор, как я использовал C ++ для написания решения с нуля. В работе использую C, Java и Python. C ++ показался мне чуждым. Я собрал шаблон, в котором есть несколько ярлыков, чтобы мне не приходилось использовать их каждый раз, когда я начинаю программировать.
В моих книгах по соревновательному программированию было несколько советов, например
- Тренируйтесь печатать быстрее, у вас должно получиться 50 слов в минуту (слов в минуту).
- Используйте макросы, чтобы уменьшить объем набора текста.
Похоже, что эти вещи будут иметь значение, когда будет более высокий уровень конкуренции. Я не буду сейчас об этом беспокоиться. Нет смысла печатать быстрее, когда вам интересно, что печатать.
Для тех, кому интересно, вот мои результаты теста набора текста.
Есть и другие советы, подобные тому, который мне понравился, особенно по оптимизации стандартного ввода и вывода для сокращения времени работы.
Я понял, почему программирование в реальном мире сильно отличается от соревновательного программирования. Это ограничения, среда и цели очень разные. Но общее между ними состоит в том, что у вас есть проблема, и вам нужно найти решение.
Вот и все, что касается платформы Codeforces. Это было немного ошеломляюще, но мне понравилось время, которое я потратил на это.
Кстати, в случае, если вам интересно, где ввести свой код и протестировать свои собственные тестовые примеры на Codeforces, посмотрите изображение ниже. А для отправки вы можете использовать кнопку отправки в том же меню.
Источник: digitrain.ru
Самый главный секрет CodeForces
Как ускорить программу на c codeforces
adamant → I’m adamant, AMA
d uality → Codeforces Round #884 (Div. 1 + Div. 2) Editorial
d uality → Codeforces Round #884 (Div. 1 + Div. 2)
actinium16 → EGOI 2023 teams
_ZeyadRafat_ → Issue about my code for problem D
Anodite → Is it a good idea?
EduardoBrito → OII 2023 Teams
adamant → Dirichlet convolution. Part 1: Fast prefix sum computations
tawhidmonowar → ++i vs i++ which one is faster and why?
A.TURKI → CF-predictor
pikamonstruosa → Portugol support in codeforces
KhaledFarhat → [GYM] The 2023 Damascus University Collegiate Programming Contest
filch178 → What do you do in your free time?
adamant → Dirichlet convolution. Part 2: Dirichlet series and prime counting
adamant → Stirling numbers with fixed n and k
adamant → Evaluation and interpolation on geometric progression
JohnCena420 → Graph Matching
Mohamed_salah41 → div 4 contests
adamant → Implementing Dinitz on bipartite graphs
phattd → Introducing Arugo — A website that provides virtual rating while practicing on problemset
relax_1 → Please , Help me !
Navii77 → Minimal payments (ABC 231)
CRESCENTNINJA → Why is Python not good for CP?
dimss → How to speed up the sieve of Eratosthenes by 1.5 times with one line
Tareq_Ali → Multi Ordered Set Data Structure
Блог пользователя andreyv
Снова про ввод/вывод в C++
Автор andreyv, 11 лет назад ,
Хочу продолжить тему скорости ввода/вывода в C++, которую когда-то начал товарищ freopen. freopen сравнивал производительность двух способов ввода/вывода в C++: унаследованной от C библиотеки stdio ( ) и более новой библиотеки iostreams ( /…). Однако в этих тестах не было учтено, что iostreams можно значительно ускорить, включив некоторые оптимизации. Об их существовании уже неоднократно упоминалось на Codeforces (раз, два, три). Сейчас я написал софт, который сравнивает производительность stdio и iostreams на стандартном вводе/выводе с учётом этого.
UPD1: Добавлена информация про _CRT_DISABLE_PERFCRIT_LOCKS .
UPD2: Для полноты картины добавлены вызовы printf() / scanf() на строках.
Что это за оптимизации?
Первая состоит в том, что в начале программы, перед каким-либо вводом/выводом, можно вставить строчку
ios_base::sync_with_stdio(false);
Эта команда отключает синхронизацию iostreams с stdio (описание). По умолчанию она включена, то есть, iostreams и stdio можно использовать вместе на одном и том же потоке, перемежая их вызовы. После отключения синхронизации так делать больше нельзя, однако за счёт этого iostreams может работать быстрее.
Вторая оптимизация заключается в том, что для cin можно выключить привязку к cout :
cin.tie(NULL);
По умолчанию cin привязан к cout , что означает, что перед каждой операцией над cin сначала сбрасывается буфер cout (описание). Отключение этой функции опять-таки позволяет iostreams работать быстрее. С этой оптимизацией надо быть внимательным в интерактивных задачах: либо не использовать её, либо не забывать явный flush .
Отмечу ещё, что на производительность iostreams негативно влияет частое использование endl , поскольку endl не только выводит символ новой строки, но и сбрасывает буфер потока (описание). Вместо endl можно просто выводить ‘n’ или «n» .
Какие тесты включены в программу?
Я постарался сымитировать наиболее типичные ситуации, возникающие при решении задач.
- Ввод/вывод int с помощью stdio, iostreams и, для сравнения, самопальных функций
- Ввод/вывод double
- Посимвольный ввод/вывод
- Ввод/вывод строк: как с char * , так и с std::string
Какие тесты не включены в программу?
- long long — полагаю, результат будет коррелировать с int
- Преобразование int и запись результата в собственный буфер достаточно большого размера, а затем прямой вывод буфера с помощью fwrite() / cout.write() (и аналогичное решение для ввода)
- Экзотический способ посимвольного ввода/вывода: cin.rdbuf()->sgetc() и cout.rdbuf()->sputc()
- Какие-либо манипуляции с размером буфера потоков (похоже, что в GCC iostreams для стандартных потоков игнорирует пользовательские установки насчёт этого). Это направление ещё можно исследовать потом.
Как это запустить у себя?
Надо скомпилировать программу, не забыв включить оптимизацию ( -O2 /Release), и запустить её с тем же рабочим каталогом, где она и находится. Если при запуске в Windows появляется сообщение Access denied, то может помочь запуск программы с повышенными правами. Программе потребуется пара сотен мегабайтов свободного места в каталоге для временных файлов.
Дополнительные замечания
- Почему нужно для каждого теста создавать новый процесс?
Из-за ios_base::sync_with_stdio(false) , который препятствует поочерёдному тестированию stdio и iostreams, а также (теоретически) мешает использовать freopen() , чтобы перенаправлять cin / cout .
- Зачем удалять файл от предыдущего запуска перед каждым тестом?
Чтобы все запуски были в равных условиях. Хотя, это несколько спорный вопрос. Может, лучше не удалять, а переписывать?
- Почему время измеряет запускаемый, а не запускающий процесс?
Чтобы исключить время запуска/завершения процесса.
- Почему бы вместо clock() не использовать более точные вызовы, например, getrusage() ?
Это можно. Но сначала мне надо понять, как это делать в Windows 🙂
Результаты
Запускал на компьютере с Pentium 4, так что время может показаться несколько большим.
- Для Visual C++ 2010: http://pastie.org/4680309
int, printf 9.45 9.48 9.44 int, cout 22.03 22.01 22.21 int, custom/out 11.17 11.06 11.20 int, scanf 5.04 4.77 4.82 int, cin 20.26 20.16 20.16 int, custom/in 10.25 10.25 10.25 double, printf 19.23 18.98 18.95 double, cout 37.49 37.52 37.44 double, scanf 12.11 11.75 11.73 double, cin 26.88 26.57 26.57 char, putchar 13.29 13.76 13.48 char, cout 23.52 24.15 23.41 char, getchar 12.87 12.82 12.74 char, cin 16.13 16.22 16.50 char *, printf 6.88 6.74 6.57 char *, puts 3.95 3.82 3.95 char *, cout 6.36 6.32 6.43 string, cout 6.40 6.40 6.61 char *, scanf 6.16 6.10 6.13 char *, gets 3.98 3.96 3.96 char *, cin 8.72 8.91 8.85 string, getline 11.70 11.47 11.53
Здесь всё очевидно: stdio значительно превосходит по скорости iostreams. Примечательно, что на int printf() / scanf() быстрее даже самописных функций (однако см. дополнение ниже). Ввод/вывод строк с помощью puts() / gets() быстрее, чем с помощью printf() / scanf() — ну, это и понятно. Запись std::string занимает столько же, сколько и запись char * , а вот чтение в std::string медленнее — наверняка из-за необходимости динамически выделять память.
- Для MinGW (GCC 4.7.0): http://pastie.org/4680314
int, printf 9.72 9.61 9.61 int, cout 6.08 6.05 6.10 int, custom/out 2.73 2.75 2.76 int, scanf 5.01 5.01 5.01 int, cin 3.99 4.04 4.04 int, custom/in 0.86 0.86 0.87 double, printf 22.51 22.40 22.42 double, cout 110.98 111.77 111.01 double, scanf 12.18 12.20 12.17 double, cin 118.87 118.84 118.87 char, putchar 1.67 1.65 1.64 char, cout 3.93 3.87 3.85 char, getchar 0.78 0.80 0.80 char, cin 3.29 3.31 3.29 char *, printf 5.55 5.47 5.49 char *, puts 5.37 5.32 5.41 char *, cout 8.72 8.72 8.78 string, cout 8.74 8.71 9.06 char *, scanf 7.07 7.04 7.02 char *, gets 3.84 3.79 3.77 char *, cin 5.30 5.38 5.35 string, getline 14.15 14.12 14.16
А здесь всё уже не так однозначно.
Неожиданно оказывается, что iostreams на 20-30% быстрее stdio на int . Правда, самописные функции значительно обгоняют и то, и то. С double наоборот: iostreams заметно тормозит. Посимвольный ввод/вывод с putchar() / getchar() работает в 2-3 раза быстрее cout / cin . Ввод/вывод строк отличается не так сильно, но stdio и тут быстрее. На строках puts() / gets() также быстрее, чем printf() / scanf() . std::string , как и в предыдущем случае, работает одинаково с char * на выводе, однако медленнее на вводе.
Какие делать выводы и что использовать, пусть каждый решает сам. В комментариях приветствуется флейм конструктивное обсуждение.
Дополнение
В Visual C++ есть способ значительно ускорить базовые операции с потоками stdio, отключив блокировку потоков для функций getchar() , putchar() и некоторых других. Для этого надо перед всеми #include вставить строчку
#define _CRT_DISABLE_PERFCRIT_LOCKS
(описание). Это сработает только при выполнении следующих дополнительных условий:
- Программа статически компонуется со стандартной библиотекой ( /MT ; на Codeforces, похоже, это так)
- Программа включает , но не включает ни , ни какой-либо файл из библиотеки iostreams ( /…)
Вместо всей этой магии можно также просто использовать _putchar_nolock() / _getchar_nolock() вместо putchar() / getchar() . В Linux тоже есть похожие функции: ссылка.
С этой оптимизацией посимвольный ввод/вывод ускоряется в восемь-девять (!) раз, а вместе с ним и вручную написанные функции ввода/вывода int :
int, custom/out 1.70 1.70 1.72 int, custom/in 1.28 1.26 1.28 char, putchar 1.72 1.62 1.61 char, getchar 1.36 1.34 1.36
В MinGW такое поведение включено по умолчанию и не имеет вышеописанных ограничений.
c++, ввод-вывод, производительность
Источник: codeforces.com
Про сайт Codeforces
Если вы добрались до сюда, то вы уже довольно хорошо программируете, и имеет смысл не только решать задачи нашего курса, но также и дополнительно более-менее регулярно тренироваться. Рекомендую вам зарегистрироваться на сайте codeforces.com (есди он у вас вдруг открывается на английском языке, то в правом верхнем углу можно переключиться на русский), изучить его и время от времени принимать участие в его «раундах».
А именно, на этом сайте регулярно проводятся соревнования — «раунды». Они бывают в среднем раз в одну-две недели (каждый раунд писать не обязательно, но я бы вам рекомендовал хотя бы раз в месяц-полтора писать раунды). Это не какие-то призовые олимпиады и т.п., в них имеет смысл участвовать из интереса, и с целью тренировки. Раунды проводятся по разным правилам, ниже я опишу наиболее распространенный вариант.
Во-первых, у всех участников codeforces есть так называемый «рейтинг» — целое число, показывающее, насколько вы успешно выступали на раундах codeforces. Если вы хорошо выступаете, ваш рейтинг будет расти, если плохо, то падать. От рейтинга зависит цвет, которым ваш ник пишется на страничках codeforces. Кроме того, все участники codeforces делятся на два «дивизиона» по рейтингу. Вы изначально участвуете во втором дивизионе, если ваш рейтинг становится достаточно высоким (1700 и выше), то вы переходите в первый дивизион.
Раунды обычно проводятся отдельно по дивизионам. Наиболее часто проводятся два параллельных раунда — для первого и для второго дивизиона; задачи частично пересекаются, частично отличаются. Бывают объединенные раунды для двух дивизионов, бывают раунды только для второго дивизиона. Бывают раунды по совсем особым схемам и правилам.
Большинство раундов являются «рейтинговыми», т.е. результаты участия в них влияют на ваш рейтинг, но бывают и «нерейтинговые» раунды. Обычно о рейтинговости раунда предупреждают заранее.
Наиболее часто раунды проводятся по следующим правилам. Для участия в раунде надо заранее зарегистрироваться на этот раунд (т.е. не просто зарегистрироваться на сайте, но еще и нажать специальную кнопку «зарегистрироваться на раунд»), обычно регистрация на раунд заканчивается минут за 5-10 до начала раунда. Раунд длится 2-2.5 часа. Вам предлагается 5 задач, упорядоченных по сложности (по крайней мере как думают авторы задач). У каждой задачи есть своя стоимость, определяющая количество баллов, которые вы получите при успешном решении этой задачи. У простых задач стоимость невысокая (обычно от 500), у сложных — высокая (обычно 2500). (Эти баллы не имеют прямого отношения к баллам рейтинга.)
Вы можете решать задачи в произвольном порядке (хотя обычно все решают от простых к сложным), на любых допустимых языках программирования. Когда вы считаете, что вы написали решение, вы можете его отправить на проверку (аналогично тому, как вы делаете на нашем сайте). Ваша задача будет проверена на так называемых «претестах» — некотором наборе тестов, который не обязательно является полным (т.е. вы можете пройти все претесты, даже если ваше решение не совсем правильное). Если ваше решение не прошло хотя бы один претест, оно не принимается, и вам об этом сообщают. Если оно прошло все претесты, то оно «принимается на окончательную проверку», которая будет проходить в конце раунда.
Если ваше решение не прошло претесты, вы можете его пересдавать. Если оно прошло все претесты, вы все равно можете его пересдать — если, например, вы нашли у себя ошибку. При этом за каждую лишнюю посылку вы впоследствии получите 50 штрафных баллов.
Стоимость задач падает со временем, к концу контеста опускаясь до примерно половины начальной стоимости. Соответственно, если в итоге окажется, что вы решили задачу, то вы получите столько баллов, сколько она стоила в момент вашей последней посылки, минус 50 баллов за каждую предыдущую посылку. В течение раунда вы можете смотреть его текущие результаты, т.е. кто что на данный момент решил.
Вдобавок ко всему этому, существует система «взломов». А именно, если ваше решение по некоторой задаче прошло претесты, вы можете его «заблокировать» (нажав на соответствующую кнопку в интерфейсе). После этого вы уже не можете перепосылать эту задачу, но зато вы получаете возможность смотреть исходные коды других участников по этой задаче (только те, что прошли претесты). Чтобы вам не возиться в огромной таблице результатов, все участники перед раундом псевдослучайным образом делятся по «комнатам», и вы можете просматривать решения только участников из своей комнаты. Чтобы просмотреть уод участника, надо сделать двойной щелчок по соответствующей ячейке в таблице результатов комнаты.
Цель просмотра решения — попробовать найти в нем ошибки. Если вы думаете, что вы нашли ошибку в решении, вы можете придумать тест, на котором, как вы думаете, это решение будет работать неправильно, и отправить этот тест в систему — попробовать «взломать» это решение.
Система тут же проверит это решение на вашем тесте и, если оно действительно не работает, то вы получите плюс 100 баллов, если вы ошиблись, то вы получаете минус 50 баллов. В случае успешного взлома участник, которого взломали, это увидит, и (если он еще не заблокировал задачу) сможет перепослать свое решение. Если он уже заблокировал задачу, то ему не повезло. Соответственно, аналогично другие участники могут взламывать ваши решения; при этом, конечно, вы не видите тест, которым вас взломали.
При просмотре решения вы не можете куда-либо копировать его текст; вы должны смотреть код чисто глазами.
После окончания времени раунда все решения перетестируются на полноценном наборе тестов. Теперь если у вас все-таки было неверное решение, то оно почти наверняка не пройдет какой-нибудь из полноценных тестов. После этого вычисляются окончательные результаты.
А именно, по каждой задаче, которую вы сдали, вам начисляются баллы, соответствующие стоимости задачи в тот момент, когда вы послали по ней последнее решение, минус 50 баллов за каждую предыдущую посылку по этой задаче. По тем задачам, которые вы так и не сдали, штрафные баллы не начисляются. Добавляются результаты взломов (100 баллов за успешный взлом, 50 баллов за неуспешный), и получается ваш итоговый балл, определяющий место, которое вы в итоге занимаете. От этого места зависит прирост вашего рейтинга.
После каждого раунда публикуются краткие разборы задач (в тот же день или через день-два). Рекомендую вам их читать. Кроме того, после окончания раунда вы все еще можете «дорешивать» — отправлять задачи на проверку просто чтобы дописать или исправить ошибки, которые у вас были. На результаты раунда это, конечно, не влияет, но все-таки разобраться в своих ошибках нужно.
Кроме того, на этом сайте есть много другой полезной информации. Во-первых, там есть функционал блогов, и пользователи часто пишут различные тексты и статьи на темы, связанные с программированием. На многих страницах сайта справа есть список постов, которые в данный момент обсуждаются. Во-вторых, на сайте есть раздел «тренировки», куда выкладываются задачи многих прошедших олимпиад; их можно самостоятельно решать в учебных целях.
Источник: algoprog.ru