...воспользоваться простой советской содой:

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // Ваш код тут
    int n;
    std::cin >> n;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        sum += x;
    }
    std::cout << sum << std::endl;
}

Это ускорит код настолько, что вам в жизни больше не придется думать о скорости ввода-вывода. Ставьте классы и подписывайтесь на мой канал!

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

Традиционная сборная таблица результатов с условиями: reg.algocode.ru. Пока данные берутся только из опроса (заполните!) и нескольких официальных таблиц, когда появятся остальные -- добавится информация оттуда. Отдельная просьба организаторам и другим людям с доступом к результатам своего региона: пожалуйста, перешлите их @prog_cf_bot.

TL;DR: the popular empirical bounds for FFT stability overestimate the precision by a few bits -- multiplication might thus produce wrong answer even after thorough testing on random inputs.

Introduction

So here's how people typically advise you to use FFT after proving various theorems and providing a $$$\mathcal{O}(n \log n)$$$ algorithm.

Suppose you want to multiply two big integers, stored in binary. Split them into groups of $$$B$$$ bits, called $$$a_0, a_1, \dots$$$ and $$$b_0, b_1, \dots$$$ respectively, so that the integers are equal to $$$a_0 + a_1 x + \dots$$$, $$$b_0 + b_1 x + \dots$$$ for $$$x = 2^B$$$. Multiply the polynomials $$$(a_0 + a_1 x + \dots) (b_0 + b_1 x + \dots)$$$ via FFT and substitute $$$x = 2^B$$$ to obtain the $$$n$$$-bit product.

$$$B$$$ is a variable here -- the algorithm works for every $$$B$$$, but larger $$$B$$$s are faster. We're limited by precision of 'double' though, because 'double' can only precisely store integers from $$$0$$$ to $$$2^{53} \approx 9 \cdot 10^{15}$$$ (e.g. $$$2^{53}+1$$$ cannot be represented by double). So we certainly require $$$2B + \log_2 \frac{n}{B} \le 53$$$ to be able to represent the product, but the actual limit is not $$$53$$$ but a bit less because of precision loss at intermediate stages. So there's this incentive to use $$$B$$$ as large as possible, but exactly how much we can increase it cannot be predictable because of the sheer complexity of analysis of floating-point error.

So here's what we're gonna do: let's start with some large value of $$$B$$$, run a few polynomials through this algorithm and check if the product is correct. If it isn't, decrease $$$B$$$ and repeat. If it is, call it a day and use this value of $$$B$$$ for the rest of your life. That's what I've always done. That's what I did writing my own bigint library, but I wanted to be more thorough so I stress-tested it for 20 hours in 8 threads on random input. Zero errors.

Twist

The problem is -- this is bullshit. The fact that the algorithm works for random data says nothing about how it behaves in worst case, for one simple reason. For random data, the errors accumulated during the intermediate stages are sort of independent and can be approximated as a one-dimensional random walk. The neat part about a $$$k$$$-step 1D random walk is that, on average, the distance from $$$0$$$ is around $$$\sqrt{k}$$$, as opposed to the maximal possible value of $$$k$$$. So the error is severely underestimated.

What is the worst case for FFT, then?

...или «как тестирующие системы борются с мельницами».

Привет, Codeforces!

Я уверен, что те из вас, кто пытался провести соревнования по программированию или написать свои утилиты для работы с контестами, знакомы с положением дел. Есть множество несовместимых форматов, никто не знает, как именно все должно работать, Polygon полон не описанных и на первый взгляд несовместимых опций, ej-polygon как будто никогда не работает полностью корректно, в архивы жюри приходится вносить изменения под каждую платформу, нестандартные виды задач требуют постоянной поддержки и хаков, и так далее.

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

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

Этот формат допускает практически произвольные типы задач, в дополнение к обычным типам: стандартному вводу-выводу, интерактивному и двойному запуску и задачам с грейдерами. Например, поддерживаются:

• Задачи с пользовательскими скорерами (пользователям Ejudge известные как программы оценки). Это значит, что баллы за решение не обязательно равны сумме баллов за каждый тест; возможны любые соотношения, в том числе отрицательные оценки, оценка программ по эффективности, вплоть до даже «напишите программу, которая выводит ваш юзерейм».

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

• Опциональная компиляция на каждом тесте, которая пригодится на некоторых контестах по практической разработке.

• Задачи только с выводом, когда от пользователя просят отправить ZIP архив, который содержит ответы на каждый тест.

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

• Арбитраж, позволяющий создавать задачи марафонского типа (про ранние идеи на эту тему можно прочесть тут), то есть задачи, в которых баллы за решение могут зависеть от результатов других решений.

Cуществующим платформам, поддерживающим формат Полигона или что-то на него похожее, в целом потребуется немного модификаций для поддержки всего, кроме стратегий и арбитража: я надеюсь, что основные вендоры с этим справятся. Полноценную поддержку стратегий реализовать может быть несколько затруднительно, так что эта часть пока опциональна (впрочем, это не умаляет значимости всего остального). Технически, реализовать арбитраж должно быть просто, но для этого могут потребоваться некоторые изменения в архитектуре софта.

Черновик спецификации доступен здесь: https://github.com/imachug/problem-xml-specs. Хотя я думаю, что спецификация практически окончена и публикую ее здесь для большей обозримости, я буду рад услышать ваши мысли по этому поводу и изменить что-то в случае необходимости.

Тегаю некоторых людей для лучшей видимости — ваш вклад будет очень полезен: geranazavr555, MikeMirzayanov, grphil, andrewzta, dkirienko.

Unfortunately, most derivations of the chance of polynomial hashing collision are invalid, wrong, or misleading, and finding reliable public sources with proofs is incredibly difficult. This article is a formal analysis of the method. The goal of this article is to complement well-known empirical facts with theory, provide boundaries on the probability of collision, justify common choices, and advise against certain popular parameters.

There is no code in this article, and it's mostly theoretical. It's more of a summa of everything we know about polynomial hashing in integers rather than a guide for beginners. You'll probably find something of interest still. I do, however, describe some methods of cracking hashes, which I can provide code and additional explanation for if someone asks in the comments and some general guidelines in the last section of the present article.

Table of contents

• The concept of polynomial hashing
• Classical justification of the coprimality requirement
• The pitfall
• Probability of size-bounded collision
• Probability of value-bounded collision
• Back to basics
• Conditions of surjectivity
• Handling lengths
• Side note on coprimality
• The two scenarios
• Reversal
• Thue-Morse sequence
• Attempt to reuse Thue-Morse sequence for other moduli
• Birthday paradox
• Lower bounds for anti-hash tests
• Particularities
• Key takeaways

I'd like to share this one unpopular but awesome algorithm that I only heard a mention of once. Kapun's algorithm finds a hash collision for moduli as large as $$$10^{18}$$$. I know, we have lots of algorithms that do much better than that (and I'm writing an article on that at the moment, keep tuned), but Kapun's algorithm is really surprising in its simplicity. That its correctness is so difficult to prove is of more surprise even.

Here we go.

A polynomial hash of a string $$$s$$$ is defined as

We want to find two strings with the same polynomial hash using only two characters: $$$0$$$ and $$$1$$$.

We can reformulate this problem in another way. Let $$$a_i = b^i \mod M$$$, then we want to find two distinct subsets of $$$a$$$ with the same sum modulo $$$M$$$. Now forget about the modulus: let's just find two subsets with the same sum.

Firstly, when is this possible? There are $$$2^n$$$ possible subsets and $$$n(M - 1) - n + 1 = n (M - 2) + 1$$$ distinct sums. If $$$2^n > n (M - 2) + 1$$$, that is, $$$\frac{2^n}{n} \gg M$$$, there are certainly two subsets with the same sum. Generating $$$M$$$ or even just $$$\sqrt{M}$$$ strings (if you use birthday paradox) is impossible for large $$$M$$$, but there's still a way through.

It turns out there is a deterministic algorithm that attempts to solve this problem that is very easy to implement!

Традиционное обсуждение (или осуждение -- кому как) регионального этапа ВсОШ 2022 года. Кажется, к 15 часам МСК он уже должен был закончиться везде.

Традиционная сборная таблица результатов: https://reg.prog.cf/. Пока данные берутся только из опроса (заполните!) и нескольких официальных таблиц, когда появятся остальные -- добавится информация оттуда.

Отдельная просьба организаторам и другим людям с доступом к результатам своего региона: пожалуйста, перешлите их @prog_cf_bot.

The first day of IATI 2021 has finished about half an hour ago. Please feel free to discuss the competition here!

Problems

• Day 1: https://drive.google.com/drive/folders/181qblYWJlQjkAUQaMtzxDwJnvh7zUeBO?usp=sharing
• Day 2: https://drive.google.com/drive/folders/18Sd24hOt6VmhdQgaUuak0804lj3bTnM8?usp=sharing

Results

• Seniors: https://cdn.iati-shu.org/files/standing_A12.pdf
• Juniors: https://cdn.iati-shu.org/files/standing_B12.pdf

Editorials

• A11-Heaps (unofficial)
• A12-Miners
• A13-News
• A21-Hint (unofficial)
• A22-Delivery (unofficial)
• A23-Rabbit (unofficial)
• B11-Pretty
• B12-Wall
• B13-Sum-prod
• B21-Monopoly
• B22-Cutting
• B23-Sss

^ Please feel free to provide links when they are available

AtCoder

Условие

Даны числа A и B. Выведите A + B.

Разбор

В задаче требуется вывести сумму двух чисел. Обратите внимание: в языках C и C++ необходимо использовать достаточно большие типы данных.

Решение:

print(int(input()) + int(input()))

I am looking at the post called Is Mike Mirzayanov dictator? at the moment. I'm reading through the comments, I'm looking at people's reactions, I'm reading Mike's replies, and... I am utterly disappointed.

I demand progress.

For context, I do believe Codeforces is the best website for competitive programming contests at the moment. I sincerely give credit to Mike for creating Codeforces and providing participants and contest authors a platform for interaction completely for free. I am confident that Codeforces is the most appropriate website for being the platform for sharing knowledge, exchanging tricks and methods, and collaboration between both contest participants, their authors, and coordinators.

Please consider this an open letter, for this is a will not of a single person, but of many individuals. Please consider signing it by stating so in a comment under the post, should you incline to do so.

Polygon is not world's greatest evil. Polygon doesn't even have a particular defect that makes it horrible. You can't say what's exactly wrong with Polygon. Polygon seems to work, it seems like every feature is supported, but if you touch it here it will fall apart, and if you touch it there a problem (pun not intended) will appear. Or not, depending on your luck. Polygon is like PHP. For those who haven't read the famous rant, I'll cite it for you:

I can't even say what's wrong with PHP, because-- okay. Imagine you have uh, a toolbox. A set of tools. Looks okay, standard stuff in there.

You pull out a screwdriver, and you see it's one of those weird tri-headed things. Okay, well, that's not very useful to you, but you guess it comes in handy sometimes.

You pull out the hammer, but to your dismay, it has the claw part on both sides. Still serviceable though, I mean, you can hit nails with the middle of the head holding it sideways.

You pull out the pliers, but they don't have those serrated surfaces; it's flat and smooth. That's less useful, but it still turns bolts well enough, so whatever.

And on you go. Everything in the box is kind of weird and quirky, but maybe not enough to make it completely worthless. And there's no clear problem with the set as a whole; it still has all the tools.

Now imagine you meet millions of carpenters using this toolbox who tell you “well hey what's the problem with these tools? They're all I've ever used and they work fine!” And the carpenters show you the houses they've built, where every room is a pentagon and the roof is upside-down. And you knock on the front door and it just collapses inwards and they all yell at you for breaking their door.

That's what's wrong with PHP.

This is the tenth time I stumble upon a controversial blog, write a large comment that'd be useful both to the OP and other people, and when I finally post the comment Codeforces tells me the post is deleted and my giant rant doesn't get saved. I usually breath in and out and get over it, but this time I figured out I have spare contribution to post a complaint I can share my thought with the community.

It'd be great if comments were saved to drafts just like posts. This would be useful in case of network problems or power failure too, and would just improve UX overall.

Hello, Codeforces!

A few days ago MohammadParsaElahimanesh posted a blog titled Can we find each Required node in segment tree in O(1)? Apparently what they meant was to find each node in $$$\mathcal{O}(ans)$$$, according to ecnerwala's explanation. But I was too dumb to realize that and accidentally invented a parallel node resolution method instead, which speeds up segment tree a lot.

A benchmark for you first, with 30 million RMQ on a 32-bit integer array of 17 million elements. It was run in custom test on Codeforces on Apr 6, 2021.

• Classic implementation from cp-algorithms: 7.765 seconds, or 260 ns per query
• Optimized classic implementation: (which I was taught) 4.452 seconds, or 150 ns per query (75% faster than classic)
• Bottom-up implementation: 1.914 seconds, or 64 ns per query (133% faster than optimized)
• Novel parallel implementation: 0.383 seconds, or 13 ns per query (400% faster than bottom-up, or 2000% faster than classic implementation)

Привет, Codeforces!

Я на днях написал скрипт, который публикует все новые посты (и их обновления) с Codeforces в Телеграм-канал -- с форматированием и всем причитающимся.

• @cf_blogs -- английская версия.
• @cf_blogs_ru -- русская версия.

Обновления должны приходить достаточно быстро, меньше чем за 5 минут.

Приятного использования!

Привет всем! Вы, возможно, заметили, что на какое-то время Codeforces сменил логотип на новый, но, кажется, админы не могут решить, что лучше. Давайте честно проголосуем всем сообществом и выберем логотип вместе. Голосуйте за один из трех комментариев под постом.

Привет, Codeforces!

На текущий момент, провести свой раунд на Codeforces — непростая задача. Во-первых, на Codeforces нельзя предложить только одну задачу, так что, если у вас мало друзей, увлекающихся спортивным программированием, и придумать 6 задач вы тоже не можете, — вы в пролете. Во-вторых, часто в предложения попадают неприятные и неинтересные задачи, а координаторам приходится долго их разгребать и объяснять авторам, чем же задачи плохи. Я считаю, что такой статус кво — проблема и для участников, и для авторов.

Я предлагаю такую идею. Авторы предлагают кривые задачи потому, что когда им отклоняют одну из задач контеста, под угрозу попадает сам факт проведения раунда. Поэтому авторы 'брутфорсят' задачи, чтобы заделать дыру. Что, если мы поможем авторам публиковать задачи по одной, а затем собирать задачи от разных авторов в один контест? Это снизит долю плохих задач, так как авторам контестов не придется быстро латать дыры.

Вопрос в том, как обойти самое узкое место процесса — координаторов. Достаточно много красных (или 2300+) участников хотели бы помочь в координации и модерации задач. В Div 1 много людей, которые занимаются спортивным программированием, но редко пишут раунды Codeforces — может, из-за стиля или тайминга. Думаю, такие люди — идеальные модераторы: у них есть опыт, они не будут читерить, они готовы помочь и им интересно посмотреть 'за кулисы'.

Короче говоря, идея — помочь тестерам и авторам задач друг друга найти, чтобы снизить нагрузку на координаторов и чаще проводить качественные раунды.

Как вам идея?

I'm interested in non-classic problems here on Codeforces, so I've looked through the problems with special tag. The ones with non-standard format are:

1. Problems that can only be solved in a single special language, such as Q# or a secret language. Example: a single problem 409B - Mysterious Language or the whole Kotlin Heroes 5: ICPC Round contest.
2. Problems with a stateful checker, which detects how many submissions one has made. Example: 409H - A + B Strikes Back.

I also vaguely remember a problem where one had to output his username with some limitations on the source code, but it could be just a comment on a blog.

Anyway, I can't find out how to create any similar problem on Polygon. Obviously there's a whitelist of supported languages, but what about allowing the user to add an interpreter for the language in C? Or allowing the checker to read the original code, not its output? I'm interested how this is implemented for the official contests and if I can do that in a gym.

As for the second type, it'd be useful if the checker could get meta-information such as the user handle or ID, and access a local DB or use network as a state store. I couldn't find any sane documentation so I'm asking here.