Да-да! До финала чемпионата мира остались считанные дни! Команды уже собрались в Екатеринбурге, большинство зарегистрировались и смотрят матч Бельгия — Россия.

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

Мы внедрили API и хотим проверить перед предстоящим раундом, что все работает как надо.

Приглашаем вас принять участие в Testing Round 10. Старт состоится в традиционное время сегодня, 3-го июня. Раунд будет неофициальным, нерейтинговым.

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

Если вы видите какие-то изменения в функциональности, то пишите о них в комментариях.

Спасибо.

Общая информация

Саратовский государственный университет в первой половине августа проводит международную летнюю студенческую школу по программированию. Продолжительность школы — десять дней, школа пройдет с 4-го по 14-е августа 2014 года.

К участию приглашаются как команды из двух-трех человек, так и индивидуальные участники.

Школа пройдет в живописном месте, на одной из саратовских баз отдыха на берегу Волги. Участники будут расселены в уютных номерах по 2-4 человека и обеспечены трехразовым питанием. На территории базы имеется собственный пляж и спортивные площадки.

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

Похоже, это становится хорошей традицией. Центр олимпиадной подготовки Саратовского ГУ и в этом году успел сделать вылазку на природу перед сессией. Организовывать мероприятие мне пришлось в удаленном режиме (я был в отъезде), что добавило особый колорит к подготовке. Но, несколько писем, звонков, снова писем — и 18 мая мы уже на полигоне Задор, готовые к пейнтболу и высотным веревочным приключениям!

Этой вылазкой на природу мы закрыли наши регулярные лекции и тренировки. Теперь же мы встретимся после сессии на традиционных личных тренировках в июле. Как всегда потом большие планы — сборы Сазанке, командные локальные сборы в Дубках, для кого-то Петрозаводск. Красота!

С небольшой задержкой (но ведь Оскар тоже вручают весной, правда?) мы рады анонсировать лауреатов Медали Кормена за 2013-й год. В этом году мы решили опять немного обновить номинации, и в этом году Медаль Кормена вручается в двух номинациях:

• Прогресс года
• Лучший проблемсеттер

Прогресс года

Лауреатом Медали Кормена в этой номинации становится Скотт Ву (scott_wu, США). Обратите внимание на стремительный рост графика его рейтинга. Его достижения в 2013-м году не ограничиваются эффектным взлетом на Codeforces в десятку лучших участников: 5 место на IOI, победитель сезона 2013 соревнований USACO, отметка таргет на TopCoder! Мы поздравляем Скотта и желаем ему дальнейших успехов!

Лучший проблемсеттер

Для выбора победителя в этой номинации не пришлось долго ломать голову. Конечно, Медаль Кормена достается самому продуктивному и любимому многими автору 2013-го года Сергею Нагину (Sereja, Украина). Сергей подготовил и провел 7 раундов (все они Div1+Div2) на Codeforces. Задачи Сергея полюбились участникам соревнований Codeforces и мы будем рады видеть его контесты и впредь! Сергей уже был награжден медалью и почетной доской в феврале на Харьковских сборах.

Похоже, это становится доброй традицией. Лауреатам будет выслана книга Томаса Кормена (Introduction to Algorithms или Algorithms Unlocked) с подписью автора.

История

Напоминаем, что Медали Кормена присуждаются уже четвертый год. tourist (Геннадий Короткевич) три года подряд становился лучшим участником (все годы присуждения номинации). Alex_KPR (Александр Куприн) становился лучшим блоггером в оба года присуждения этой номинации. В моей любимой номинации «Лучший автор задач Codeforces» победителями становились: в 2010-ом году natalia (Наталья Бондаренко), в 2011-м году Ripatti (Артём Рипатти), а в 2012-м — witua (Виталий Герасимов). Кроме того, в 2012-м году была присуждена медаль "Codeforces Spirit of Community 2012", лауреатом которой стала Nickolas (Мария Михайлова).

https://get.google.com/albumarchive/pwa/114907919772955385569/2014CoderStrike?authuser=0&feat=directlink

Сегодня мы вновь хотим провести тестовый и нерейтинговый раунд по необычным правилам. Цель для нас — протестировать проверить новые правила, новый вид задач и работу Codeforces внутри тега <iframe>.

Старт запланирован на 22:30, появится специальная ссылка, чтобы войти в контест. Условия задач и интерфейс будут доступны только на английском языке. Продолжительность контеста составит 1.5 часа. Уверен, многие справятся быстрее.

Перейти к контесту →

В соревновании будет два вида задач: логические задачи и программистские задачи.

Логические задачи сделаны для того, чтобы их можно было решить без написания кода (но никто не запрещает его написать). Логическая задача состоит из нескольких тестов, каждый из которых стоит определенное количество баллов. Ответ на каждый тест может посылаться отдельно. Для ответа на тест логической задачи необходимо ввести ответ в соответствующее поле или выбрать один или несколько предложенных вариантов. Ответ можно изменять и посылать любое количество раз. По каждому тесту проверяется только последний ответ. Такие задачи проверяются после окончания соревнования.

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

Два участника в первую очередь сравниваются по количеству баллов. При равенстве и этих баллов сравнивается время последней попытки, которая увеличила количество баллов у участника. Для программистских задач будет использована посылка, набравшая наибольшее количество баллов. Если таких посылок несколько, будет использована самая ранняя. Для логических задач будет использовано время ответа на каждый из тестов.

Задачи будут относительно простые, но как небольшое развлечение — самое то!

Спасибо всем, кто присоединится. Ждем ваших отзывов в комментариях.

13-го апреля в 12:00 вас ждет не совсем обычный раунд. Дело в том, что впервые за долгое время Gerald почти не принимает участие в подготовке контеста. Раунд подготовлен мной (как же приятно сделать раунд!), Nerevar-ом, не обошлось без помощи Gerald-а и Fefer_Ivan-а. Маша, спасибо за переводы!

Вас ждут классические баллы за задачи: 500 — 1000 — 1500 — 2000 — 2500.

Добрый день.

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

Баг в g++, найденный недавно Gerald-ом и Nerevar-ом — еще один аргумент к такой стратегии.

Следим внимательно за руками, сейчас будет чудо: 

Some months ago we've found that YuukaKazami took part in contests using one more account. We've contacted him and he pleaded guilty and deplored about it. That acccount has been banned and YuukaKazami was disallowed to take part in rounds for two months.

Now he can take part and we hope to see him again in standings.

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

Java 8 (пока 1.8.0) была добавлена на Codeforces с теми же параметрами запуска JVM, как и другие версии Java: java.exe -Xmx512M -Xss64M -DONLINE_JUDGE=true -Duser.language=en -Duser.region=US -Duser.variant=US -jar %s.

В настоящее время поддержка Java 8 осуществляется в тестовом режиме, давайте вместе протестим её на задачах нашего архива.

В качестве примера новых возможностей — код, сортирующий заданный набор строк в порядке лексикографического невозрастания:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            List<String> lines = new ArrayList<>();
            while (scanner.hasNextLine()) {
                lines.add(scanner.nextLine());
            }
            lines.stream().sorted((a, b) -> b.compareTo(a)).forEach(System.out::println);
        }
    }
}

Ночью 2-го марта 2014-го года произошел серьезный технический сбой жестких дисков Codeforces и сопутствующей инфраструктуры. К сожалению, выяснилось, что в отличии от всех остальных компонентов, база данных Codeforces не реплицировалась должным образом. Полигон и файлы контестов из Тренировок не пострадали. Однако данные Codeforces оказались существенно повреждены.

Скорее всего, мы будем вынуждены откатить систему на состояние 7-го февраля. Таким образом, из жизни Codeforces выпадет 22 дня. Ближайшие усилия будут направлены на тотальное исключение подобных ситуаций. Это очень серьезная потеря для меня лично, в которой я могу винить только себя.

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

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

Что получится вернуть:

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

Приношу извинения за сложившуюся ситуацию.

Если вы не спите в час ночи и не знаете чем заняться, то у меня есть для вас хорошие новости. В час ночи 17-го января 2014 г. состоится Testing Round 9, цель которого протестировать хорошенько платформу перед завтрашним раундом. Мы порелизили большое количество внутренних изменений, которые не видны пользователям, но влияют на всевозможную функциональность системы.

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

Если вы видите какие-то изменения в функциональности, то пишите о них в комментариях.

Спасибо.

UPD. Контест закончен. Спасибо всем, кто принял участие.

Проснулись уже?

Открыта традиционная новогодняя опция. Спешите! Только до 10-го января вы можете изменить свой хэндл! Обратите внимание, что откатить изменения или изменить хэндл еще раз вы сможете только через год.

Касательно необдуманных хэндлов я всегда вспоминаю такую историю. Мне как-то написал пользователь с просьбой: "Прошу сменить мой хэндл с I_love_Valya на I_love_Sveta, так как Валю я больше не люблю..."

С новым годом!

Доброго вам предновогоднего дня!

На часах без пары суток Новый Год, а значит самое время подводить итоги прошедшего. У меня нет спич-райтеров для слов в стиле "то, что совсем недавно казалось почти невозможным, становится фактом нашей жизни", поэтому коротко. Всем спасибо! Ваш негаснущий интерес и постоянная помощь вдохновляют команду Codeforces на новые свершения! Гениальные авторы, бойцы невидимого фронта тестеры, неутомимые и жадные до знаний участники раундов и тренировок — все вы помогаете сделать Codeforces лучше!

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

• Простой способ добавить соревнование из Polygon в Codeforces::Тренировки. Недавно появился подробный туториал (спасибо, elena!)
• Черновики, встроенные в текстовые поля форм в проектах Codeforces и Polygon.
• Множественные улучшения интерфейса участника соревнований.
• Множественные улучшения библиотеки Testlib.
• Улучшена производительность Polygon на больших ручных тестах.
• Неоднократно обновлялись версии компиляторов до свежих.
• Поддержаны языки: MS C#, Python 3, Go, JavaScript V8.
• Обновлены тестирующие серверы Codeforces и внедрены в работу.
• Polygon переведен на использование HTTPS.
• Проведён первый сезон еженедельных тренировок Codeforces (12 эпизодов).
• Поддержаны организации в профиле и рейтинг организаций.
• Добавлены многочисленные контесты в Codeforces::Тренировки. Наверное, самое ценное — большое количество контестов Андрея Станкевича.
• Внедрены тесты для чекеров и валидаторов в Polygon.
• Внедрена поддержка макро-языка в скрипты генерации тестов в Polygon.
• На Codeforces появились группы, с контестами и блогами.
• Внедрена возможность составления мэшапов — контестов для личных и групповых тренировок.

Кроме того, за 2013-й год мы провели не только 64 классических раунда, но и несколько турниров:

• Чемпионат КРОК 2013
• MemSQL start[c]up
• ABBYY Cup 3.0

А еще мы успели оказаться пресс-партнером финала ACM-ICPC 2013!

И как детективный сюжет не может обойтись без погони, так и годовой отчет не может обойтись без веселых картинок. Вот пачка наглядных картинок роста Codeforces:

Был такой пост Timus и BigInteger.isProbablePrime. В нем описывалась проблема и ее решение от команды Тимуса.

Напомню суть. Класс SecureRandom для своей инициализации должен взять откуда-то неожиданные данные, которые злоумышленнику тяжело угадать. JRE для этого использует /dev/random. В Linux это такой специальный поток, в который драйверы выводят шум от разных устройств. В результате значения там в самом деле удачно подходят для инициализации криптографического генератора случайных чисел.

На Windows происходит всё примерно так же, но шум берется из разных мест. В результате, если запустить процесс из-под ограниченного пользователя, то чтобы взять этот шум процесс начинает инициализировать профиль пользователя в системе, что требует времени. В зависимости от характера песочницы, вероятно, из некоторых мест процесс и не сможет взять энтропию. Например, на Timus это приводило к вердикту Restricted Function.

На Codeforces это приводило до недавнего времени скорее к Time Limit Exceeded, так как загрузка профиля требовала дополнительного времени.

Олимпиадникам обычно этот SecureRandom и даром не нужен, но стандартная реализация BigInteger.isProbablePrime(BigInteger) использует его.

Команда Timus предложила такое решение. Они похачили стандартную библиотеку, заменив реализацию BigInteger и, видимо, подложив её в rt.jar. Короче, теперь пользовательские решения запускаются у них с измененной стандартной библиотекой.

Мне кажется это так себе решение:

• возможно, что SecureRandom используется еще в каком-то полезном месте (или будет использоваться после апдейта);
• тяжело обновлять JRE на тестирующих машинах — ведь нельзя просто так подложить rt.jar из прошлой версии, придется хачить новый rt.jar;
• решение требует дополнительной настройки окружения, что всегда плохо (например, какой-нибудь portable timus tester либо не будет делать песочницу вообще, либо будет иметь эту проблему, либо большую инструкцию в стиле «не забудьте пропатчить Java!»).

Сегодня я нашел значительно лучшее решение, которое и накатил на Codeforces. Для JRE существует системное свойство, которое указывает откуда надо читать энтропию: -Djava.security.egd, которое по-умолчанию равно в Windows значению file:/dev/random

Так вот оказывается возможно брать энтропию из обычного файла, для этого достаточно передать -Djava.security.egd=file:имя-файла. Проблема решена. (Конечно, я сначала попробовал передать file:/dev/urandom, но это не помогло)

Напоследок, напомню, что на Timus для того, чтобы добиться повторяемости при rejudges пошли на беспрецедентный шаг и в пропатченной версии BigInteger используют Random c фиксированным randseed. В данном случае, надо просто в качестве -Djava.security.egd указывать какой-то фиксированный файл. Если хочется иметь каждый раз разное значение, то можно создать случайный файл в директории запуска решения и использовать его.

Конечно, этот трюк полностью разрушает криптостойкость SecureRandom, но в случае запуска решений участников это допустимо.

Дошли руки и до поддержки столь модного сейчас JavaScript. Выбрана реализация V8, как наиболее трендовая и развиваемая. С помощью бубна и литра колы я скомпилировал V8 под Windows. Забавно оказалось — я всё думал, что придется городить workaround, чтобы поддержать чтение в JavaScript из консоли. Оказалась, что d8 сам всё умеет. Вот пример для нахождения A+B:

var line = readline().split(' ')
print(parseInt(line[0]) + parseInt(line[1]))

Было замечено, что если не поставить перевод строки в конце ввода, то readline вернет undefined. Еще один аргумент в пользу того, что все строки должны заканчиваться переводом.

В качестве небольшого исследования и чтобы потешить свою уверенность в мнении, что все языки без статической типизации бесконечно медленны, я написал реализацию HeapSort на С++, Java и JavaScript для сортировки 10⁷ значений от 0 до 9999999. Видимо, этот бенчмарк неплохо показывает как быстро будут работать ваши решения, если вы пишите их в стиле старого доброго Pascal (всё на массивчиках, без выделений памяти и без мощных встроенных библиотек). Результаты для меня оказались неожиданными:

Отставание-то всего ничего! Я конечно понимаю, что такой код можно заанализировать и jit-ом прям в нативный закомпилить, но все же. Впечатляет. Кстати, а Java с её хваленным и нахаченным JIT не на высоте.

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

• С++
• Java
• JavaScript
• Pascal
• Python 2
• Python 3
• Ruby
• Scala
• Go
• D
• C#

Вы можете оставлять в комментариях ссылки на pastebin или сабмиты в систему. Конечно, будут удобнее пулл реквесты прямо в проект.

Если будете писать свою реализацию, то постарайтесь написать аккуратно и опрятно. Пожалуйста, максимально придерживайтесь вариантов для C++, Java и JavaScript.

UPD 1: С помощью alexei-zayakin добавил Pascal.

UPD 2: С помощью gchebanov Wizmann и juancate добавил Python 2, Python 3, Ruby, Scala, Go.

UPD 3: Вот скомпилированный для Window V8.

UPD 4: Обновил версии некоторых компиляторов, обновил результаты.

UPD 5: Добавил D. Спасибо, Gassa.

UPD 6: Добавил C#. Спасибо, gmogelashvili.

Прямо сейчас идет этап Открытого кубка, подготовленный силами СПбГУ. Этап стартанул с некоторым опозданием в 12:25. Текущие результаты доступны по ссылкам:

• Div 1
• Div 2

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

Разбор задач подготовили: Fefer_Ivan, NALP.

371A - K-периодичный массив

Для того, чтобы массив был периодическим, элементы 1, 1 + k, 1 + 2 * k, ... должны быть равны. Также, элементы 2, 2 + k, 2 + 2 * k, ... должны быть равны. И так далее до k. То есть существует k групп элементов, таких что каждый элемент принадлежит ровно одной группе. Каждая группа может рассматриваться независимо. Рассмотрим группу в которой a единичек и b двоек. Все элементы в одной группе должны быть равны. Для того, чтобы этого достичь необходимо либо все единички сделать двойками (что потребует a операций изменения), либо все двойки сделать единичками (что потребует b операций изменения). Для того, чтобы решение было оптимальным, необходимо выбрать способ, который требует наименьшее количество операций изменения.

371B - Как лисица сыр делила

Из условия понятно, что лисица может производить над числами лишь три операции: поделить какое-то из них на 2, поделить на 3 или поделить на 5. Для начала, давайте представим оба числа в форме a = x·2^a₂·3^a₃·5^a₅, b = y·2^b₂·3^b₃·5^b₅, где x и y не делятся ни на 2, ни на 3, ни на 5. Если x ≠ y, то понятно, что как бы лисица не делила числа a и b, то сравнять она их не сможет, а значит, следует вывести “-1”. В противном случае, требуется сравнять степени чисел 2, 3 и 5 в разложениях, за наименьшее количество операций это делается так: от наибольшей степени отнимается единица, пока она не сравняется с меньше степенью. Таким образом, ответ равен |a₂ - b₂| + |a₃ - b₃| + |a₅ - b₅|.

371C - Гамбургеры

Для решения этой задачи будем использовать идею бинарного поиска по ответу. Предположим, что ответ равен x, необходимо убедиться, что Поликарп сможет собрать именно столько гамбургеров и не потратит больше денег, чем у него есть. Давайте для x подсчитаем, сколько будет стоит собрать эти гамбургеры.

Пусть для одного гамбургера требуется с_b кусочков хлеб, c_s колбасы и c_c сыра (эти данные нетрудно подсчитать из строки-рецепта “гамбургера от Поликарпа”). Тогда всего необходимо c_b·x кусочков хлеба, c_s·x колбасы и c_с·x сыра. За лишние ингредиенты Поликарпу придется заплатить, поэтому в сумме он отдаст в магазине max(0, x·c_b - n_b)·p_b + max(0, x·c_s - n_s)·p_s + max(0, x·c_c - n_c)·p_c рублей. Если это значение меньше, чем r, то Поликарп сможет сделать x гамбургеров, а иначе — нет.

С помощью бинарного поиска найдем такое максимальное x, что max(0, x·c_b - n_b)·p_b + max(0, x·c_s - n_s)·p_s + max(0, x·c_c - n_c)·p_c ≤ r, такое число и будет ответом на задачу.

371D - Сосуды

Наивное решение этой задачи работает следующим образом. Давайте хранить количество жидкости в каждом сосуде в массиве v. Тогда для ответа на запрос второго типа надо просто взять значение из этого массива. Для выполнения запроса первого типа (налить x жидкости в сосуд i) надо выполнить следующую процедуру:

1. Если x = 0 то вся вода уже использована, закончить процедуру.
2. Если i > n то вся оставшаяся вода будет разлита на пол, закончить процедуру.
3. Если x единиц воды помещаются в сосуд i, то прибавить x к v[i] и закончить процедуру.
4. Заполнить сосуд i полностью и вычесть использованное для этого количество воды из x.
5. Присвоить i = i + 1.
6. Перейти к первому шагу.

В худшем случае, такая процедура будет итерироваться по всем сосудам для каждого запроса. Например, если у нас есть n сосудов вместимости 1, то запрос вида 11n потребует O(n) времени на выполнение.

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

То есть вместо i = i + 1 присвоение должно выглядеть так i = найти_следующий_неполный_сосуд(i).

Для реализации этой функция существует множество структур данных. Например, можно использовать упорядоченное множество (set в C++, TreeSet в Java). Давайте поддерживать множество индексов незаполненных сосудов. Тогда для того, чтобы найти следующий сосуд после i-того необходимо найти наименьшее число в множестве, которое строго больше i. Для этого существуют встроенные методы (upper_bound в C++, higher в Java).

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

Теперь алгоритм выполняет не более, чем O((m + n)logn) операций для всех запросов. Во время каждой итерации процедуры наливания существует два варианта: либо сосуд будет полностью заполнен водой (а такое может произойти только n раз, так как у нас всего n сосудов), либо у нас закончится вода и процедура завершится. Таким образом в сумме будет совершено не более, чем O(m + n) итераций процедуры наливания. Каждая итерация требует не более одного запроса к упорядоченному множеству, следовательно решение работает за O((m + n)logn).

371E - Реформа метро

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

Сначала давайте отсортируем все станции по их координате. Главная идея в этой задаче заключается в том, что выбранные k станций обязательно будут следовать подряд в этом отсортированном списке. Ограничения не позволяют делать это “в лоб”, поэтому нам необходимо решение быстрее.

Определим функцию f(i, k) — попарное расстояние среди k подряд идущих в отсортированном списке станций, начиная с позиции i. Для начала, давайте подсчитаем f(0, k) (здесь и далее будем использовать 0-нумерацию). Это делается несложно за линейное время: по определению f(0, 0) = 0, а по значению f(0, i) найдем значение f(0, i + 1):

,

где функция sum(l, r) означает сумму x_i, где l ≤ i ≤ r, значения этой функции легко считаются за O(1) с помощью частичных сумм.

Теперь научимся считать по значению f(i, k) значение f(i + 1, k): для этого необходимо исключить из набора координату x_i и добавить x_i + k. Аналогично выше рассуждениям: f(i + 1, k) = f(i, k) - (sum(i + 1, i + k - 1) - x_i·(k - 1)) + (x_i + k·(k - 1) - sum(i + 1, i + k - 1)).

Таким образом считаются значения f(i, k) для любых корректных значений i. Найдем минимальное значение, где оно достигается и выведем ответ. Решение работает за линейное время.

Обратите внимание на некоторые изменения в расписании. Дважды.

Доброго времени суток, сообщество Codeforces!

Рад Вам сообщить, что мы в очередной раз делаем раунд из задач одной из олимпиад для саратовских школьников. На этот раз — раунд для второго дивизиона. Раунд начнется в необычное для Codeforces время: 7 декабря в 11:00 MSK

Задачи были подготовлены большим коллективом сотрудников и студентов Центра олимпиадной подготовки программистов Саратовского государственного университета.

Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.

Наш текущий план: разбаловка задач будет динамической.

UPD: Перенесли с 13:00 на 11:00 из-за Kotlin Challenge.

UPD 2: Опубликован разбор задач.

Завтра (1-го декабря) в 10:00 стартует полуфинал NEERC чемпионата мира по программированию ACM-ICPC.

Болеть за участников можно будет по этой ссылке.

Соревнование будет одновременно проходить в Санкт-Петербурге, Барнауле, Тбилиси и Ташкенте. Судя по результатам пробного тура всего за право выйти в финал поборются 235 команд.

Полуфинал NEERC проводится с 1996-го года. Вот список чемпионов NEERC прошлых лет.

Желаю участникам продемонстрировать завтра все свои сильные стороны на поприще соревнований по программированию. Удачи!

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

P.S. Соревнование закончено. Поздравляю победителей:

• 1 место: SPb SU 4 (Kunyavskiy, Egorov, Suvorov)
• 2 место: Moscow SU 1 (Pyaderkin, Evstropov, Omelyanenko)
• 3 место: Saratov SU 1 (Agapov, Fefer, Kudasov)

С полными результатами можно ознакомиться по ссылке.

Добро пожаловать на 2013-2014 CT S01E012: Codeforces Trainings Season 1 Episode 12. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

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

Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.

Пожалуйста, не решайте этот контест, если вы уже решали эти задачи ранее.

Удачи!

Добро пожаловать на 2013-2014 CT S01E011: 2013-2014 ACM-ICPC East Central North America Regional Contest (ECNA 2013). Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

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

Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.

Пожалуйста, не решайте этот контест, если вы уже решали эти задачи ранее.

Удачи!

Добрый день.

Наверняка кого-то расстрою, кого-то обрадую: мы вынуждены немного перенести вперед Раунд 210. Раунд будет перенесен на полтора часа вперед и начнется в 21:00. Я понимаю, что участникам с восточной части страны и мира будет менее удобно.

На самом деле для меня причина приятная — просто время проведения раунда со снайперской точностью пересеклось во временем празднования дня рожденья (сегодня ей уже 2 года!) моей доченьки. Дело в том, что за последнее время было внедрено несколько важных улучшений в глубине тестирующей системы (изменен механизм кэширования), поэтому мне бы не хотелось в случае каких-либо сложностей встать перед выбором: сорвать раунд или сорвать семейный праздник.

Наверняка, есть и те, кому новое время покажется более удобным.

До встречи на раунде!

Добро пожаловать на 2013-2014 CT S01E09: 2011 German Collegiate Programming Contest (GCPC 2011) + GCJ 2009 R3 C-D. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

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

Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.

Удачи!