To Codeforces staff mainly.

Currently, we have Java 11 and Kotlin 1.4.0 on Codeforces.
Kotlin therefore compiles under Java 8 instead of 11.
Java 9 and 11 bring some new API for BigIntegers such as public BigInteger.TWO (it was private) and BigInteger/BigDecimal sqrt() methods.
We can use them from Java, but not from Kotlin since Kotlin uses older version of Java.

Submission with this stuff on Kotlin 110180362.
Submission with the same stuff on Java 110180543.

Please, update Kotlin targeting from Java 8 to 11. It shouldn't bring any problems.
The only compilation flag you have to add is -jvm-target 11 (from the docs).

Всем привет.

Футболки с хакеркапа 2020 уже в пути, но моя, например, задержалась на таможне в Москве и нужно либо прийти лично куда-то в Москве, либо через брокера оформить документы за 1100р. чтобы эта футболка поехала дальше.

Это с FexEx-ом такие приколы? Есть какие-нибудь варианты бесплатно её доставить? Может, кто-то интересовался или с прошлых лет есть решения.

Hello, Codeforces!

Recently I was solving max-flow problems, here is one of the problems I can't solve.

You're given a network with min and max constraints on the edges. For simplicity suppose all the edges have capacity=1. For example, you have the following network:

We want to put a lower constraint on the edge C->D so that it's min=1 and check whether there exists a flow from S to T which uses the edge C->D. Note that it's unable in the given example. To find max flow on this network, we should change it slightly to remove lower constraints from the edges (algorithm is here (on russian): https://e-maxx.ru/algo/flow_with_limits). After these changes we will get the following network (I removed edge C->D with capacity 0 from the image):

Now run any max-flow algorithm and it will find the next flow (yellow edges are used edges):

As you can see, the flow is found and it means that we can use these edges in the original network and we will get the flow from S to T with edge C->D. Restore the original network now:

But, as you can see, this is not the flow from S to T.

So, my question is: How to check lower contraints in networks with cycles?

After submitting a solution and watching submissions page, it doesn't update (Testing on test x is static). When i press F5 it updates, but still being static, so i have to press F5 to update it again.

Chrome says net::ERR_CERT_DATE_INVALID.

Does anyone have the same problem?

Всем привет.

Есть у меня такая проблема, что начинаю писать код на задачу слишком рано, когда только придумал идею и минимальную реализацию.
Иногда это даёт свои плоды и я оказываюсь где-то в топе (последний хороший результат получился на 540 раунде Codeforces Round 540 (Div. 3)).
Только вот чаще я трачу очень много времени на задачу, когда можно было посидеть, немного подумать и понять, как сократить или упростить решение. В частности, сегодняшняя задача 1131D - Выбор гурмана, которую после контеста переписал и она без каких-либо проблем зашла, а написанный на контесте код валился либо на 6, либо на 9 тесте.
Найти баланс между временем на обдумывание и временем на написание бывает достаточно сложно, поэтому хочется спросить у вас, а как с такой проблемой справлялись вы?
Сидеть и полчаса думать, как написать простую задачу — фиговая идея, в то же время если сразу после прочтения сесть и что-то писать, на решение могут уйти те же полчаса.
Желательно советы, направленные именно на решение этой проблемы, а не любимое многими "решай больше задач".

Всем привет.

На днях мне предложили тренировать наших новых первокурсников. Информация об этом очень быстро дошла до них, и немало человек нашлось, которые действительно хотели бы начать что-то изучать и тренироваться. Две команды первокурсников даже неплохо выступили на нашей 1/8, так что они сами по себе хорошо соображают, но знают из программирования маловато.

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

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

Спасибо.

Всем привет.

На днях уже всплыли две темы, в которых говорилось о том, что на кф что-то считается неправильно.

Сначала был пост от NikitaMikhaylov о том, что кф неправильно считает количество символов, когда пытаешься отправить решение (там дело то ли в переводах строк, которые почему-то не учитываются, то ли в пробелах, так толком и не выяснилось).
Затем был пост от MikeMirzayanov, приспустивший с небес рейтинг tourist.

Так вот, я это к чему.

Есть задача 660D - Number of Parallelograms с Educational Codeforces Round 11. Ограничение по памяти у неё 256 мегабайт.
И есть моё решение 17255435, которое ест 263936 КБ.
Переведём в мегабайты, получим 263936 / 1024 = 257.75 мегабайт.

Итак, вопрос: что я делаю не так?

Решил я как-то на ночь порешать пару задач из архива и наткнулся вот на такое чудо: 439B - Деву-дурачок

Читаю задачу и думаю, что она делает на месте задачи B? Разве можно придумать задачу проще этой, засунуть её в тот же контест и поставить на место задачи А? Видимо можно, не знаю. Я решил сначала написать решение этой задачи чтобы убедиться, что я правильно её понял.

Первый раз я написал задачу на интах и в конце заменил инты на лонги. Получил WA на 8 тесте. Так как я не привык сразу же лезть в детали посылки и смотреть, что за тест такой сломал моё решение, сначала я поковырялся в своём коде и только после того, как не нашёл ничего неверного, полез смотреть детали посылки. И что я там вижу? Каким-то странным образом отправилось решение на интах и получилось переполнение. Ладно, едем дальше.

Второй раз я отправил решение на лонгах и наблюдал, как стремительно растёт циферка в надписи Выполняется на тесте x Увы, но я получил TL на тесте 29. Было обидно, вот честно. Опять же я полез в свой код, только уже искать не баг, а пути оптимизации. Решил вместо Arrays.sort(), который примитивы сортирует quicksort'ом, написать сортировку подсчётом, благо в худшем случае я потрачу на N памяти больше и ускорю сортировку примерно в log N раз (напомню, 1 <= N <= 10^5, 0 <= log N < 17).

И что на этот раз? Решение отработало более чем в 10 раз быстрее, чем с Arrays.sort(). Всё дело, конечно, в асимптотике O(N^2) при сортировке quicksort'ом в худшем случае.

Если так прикинуть, на яве тоже должно всё решаться на уровне библиотечных алгоритмов. Замена массива int[] на List<Integer> это подтвердила. Ведь Collections.sort(), применяемый для листов, использует алгоритм сортировки слиянием (или, что чаще случается, TimSort'ом). Использовав такой подход, я замедлил своё решение примерно в 1.5-2 раза, но избавился от сортировки подсчётом.

А теперь давайте вспомним, что в Java 8 есть такая замечательная вещь как Stream API. Использовав её в этой задаче, мы можем ввести данные, отсортировать их и собрать в один список. Также в Stream API есть версия стрима, которая работает с лонгами, тем самым хранит в себе не ссылки, а примитивы, к тому же обладает рядом дополнительных методов. К слову, такая версия сортирует лонги методом быстрой сортировки (в то время как объектный стрим сортирует так же, как Collections.sort()), и мы можем наблюдать, как решение ломается (или чинится) из-за того, что мы всего лишь поменяли местами две строки:
boxed() — запаковывает стрим примитивов в объектный (LongStream -> Stream<Long>)
sorted() — собственно, сортирует стрим

Думаю, нулевая версия, основанная на интах, никому не будет интересна, вот все последующие версии:
Array TL: 12608743
Array AC: 12608824
Stream TL: 12609313
Stream AC: 12609319

Версия автора (C++): 6814439
Он использовал std::sort. Практически полный аналог моего первого решения.

Что я вынес из этого и хочу сказать вам:

Если у вас есть риск влететь в ТЛ и в коде есть сортировка, при этом у вас есть запас по памяти и эту сортировку можно выполнить методом сортировки подсчётом, используйте его. Вы съедите немного больше памяти, но зато будете уверены, что если ваш алгоритм не заходит, значит дело, скорее всего, не в сортировке. Да и это к тому же сортировка за O(N + макс. значение N) без единого сравнения.

Всем, кто дочитал, спасибо. =)

UPD 1: Как правильно заметил Gassa, вывод получился не совсем такой, какой я собирался вынести в начале написания этой статьи, поэтому добавлю:

• Проблема: в Java встроенная сортировка примитивных типов может работать за квадрат.
• Стандартное решение: использовать сортировку объектов за O(N log N).
• Предлагаемое решение: использовать сортировку подсчётом там, где это будет быстрее. (Кстати, в очень многих задачах)

Также аналогичное обсуждение, оказывается, было здесь: link

Недавно сделал удобную утилиту для слежения за изменениями рейтинга участников на Codeforces через API (не думаю, что кому-то нравится обновлять свою страницу каждую минуту в ожидании обновления рейтинга после контеста). Всё было хорошо до одного момента. Вчера вечером утилита начала выдавать варнинги об изменении данных пользователя изменения чуть ли не каждую секунду. До сегодняшнего дня дебажил всё это дело, ничего не нашёл. Решил напрямую через браузер обращаться к API Codeforces, и вот что заметил: информация показывается то старая, то новая. Кто не понял, в чём суть, попробуйте отправлять этот запрос в браузере и заметите, что поля контактная информация (email напр.) то показываются, то нет.

Можете вбить свой хэндл , затем в настройках аккаунта поставить/убрать галочку "Скрывать контактную информацию" и отослать этот запрос несколько раз, вы должны увидеть этот хаос.

Что такое стало с КФ, было ли такое раньше и если было, кто как с этим боролся? Или придётся просто ждать, пока администрация КФ починит это дело?

Update 1: 14.07.2015: Всё это добро начало повторяться. MikeMirzayanov, что с сервером?