Всем привет.

Возможно, это будет не самое популярное изменение, но все-таки: у нас меняются правила подсчета голосов и голосования вообще. Почему? На то есть причины. Самое главное — мы решили отказаться от концепции +2/-1, как поощряющей авторов. Такой баланс отлично работал на начальном этапе развития Codeforces, сейчас же это приводит к тому, что слишком многие несодержательные посты набирают значительный плюс, да и оценка становится нерепрезентативной. Итак, теперь вес положительного голоса равен весу отрицательного, а знак суммарной оценки в самом деле характеризует отношение участников сообщество к посту или комментарию.

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

Внедрены дополнительные fraud detection эвристики (некоторые уже были), которые свели на нет разнообразные случаи мошенничества, кровную месть, усложнили reverse engineering системы и подобную ерунду. Точные детали правил подсчета голосов не распространяются, но все основные принципы изложены выше.

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

UPD. После исправления некоторых замеченных багов пересчет был запущен по-новой. Неправильно работала одна из эвристик (в частности, поэтому у dolphinigle были проблемы, его заминусовали) и были проблемы с отображением новых +/- (спасибо комментаторам).

Всем привет!

Я автор сегодняшнего раунда.

Друзья, всем привет!

Всем привет!

3-го января в 19:00 (московское время) состоится очередной Codeforces Testing Round #4. Конечно, результаты на этом раунде не повлияют на ваш рейтинг, а его проведение — это тест системы перед ответственным Codeforces Round #100. Раунд продлится всего час и будет содержать две задачи. Я не обещаю что-то интересное и захватывающее, но как небольшая разминка будет самое то :) Для нас же важно ваше участие, чтобы быть спокойными относительно недавних изменений.

Буду рад видеть вас на тестировании,
MikeMirzayanov

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

ссылка на оригинал

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

Как и в прошлом году, мы на десять дней открываем возможность смены хэндла, которая доступна из раздела «Настройки → хэндл» со страницы вашего профиля. Возможность смены хэндла будет закрыта 10-го января, так что не упустите момент.

С Новым Годом, с Новым Кодом!
MikeMirzayanov

Всем привет!

На календаре конец декабря — заканчивается 2011 год. Для нас это было очень насыщенное и захватывающее время. Ниже вы найдете итоги года в картинках в сравнении с 2010-ым годом. Если говорить коротко — у нас рост по всем фронтам! Такой результат — общая победа дружного коллектива. Особое спасибо хочется сказать компании ВКонтакте и лично Павлу Дурову, которым небезразлична судьба сообщества программистов. Спасибо авторам задач — это очень непросто подготовить соревнование. Вы оказываете существенную помощь как проекту Codeforces, так и всему сообществу в целом.

Итак, сравнение уходящего 2011 года и 2010 в картинках:

Рост числа пользователей за все время существования Codeforces (по месяцам)

Всем добрый день.

Новый год — время чудес и подарков! Совершенно случайно 100-й раунд Codeforces совпал с этим замечательным моментом.

Итак, 4-го января в 19:00 (Московское время) состоится юбилейный раунд Codeforces Round 100. Да, мы прощаемся со словом Beta в названии раундов :)

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

Самое главное: лучшие сто участников по результатам 100-го раунда получат по юбилейной эксклюзивной футболке Codeforces!

Счастливого нового года!
Команда Codeforces

Привет.

Сегодняшний раунд подготовил я. Меня зовут Михаил Тихомиров, я студент 4 курса мехмата МГУ, помимо этого работаю в Яндексе разработчиком-исследователем.

Хочется сказать спасибо Артему Рахову (RAD) за значительную помощь и грамотную координацию, Марии Беловой (Delinur) за традиционно качественный перевод условий, а также MikeMirzayanov за то, что все мы здесь сегодня собрались. =)

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

Разбалловка:

Div1: 500-1000-2000-2000-2500.

Div2: 500-1000-1500-2000-3000.

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

Пожалаем проекту удачного развития в следующем году и долгих лет существования.

Всем удачи. Желаю получить максимум удовольствия от сегодняшнего раунда и выступить на уровне.

И да, всех с наступающим! =)

UPD:

Раунд окончен. Всем спасибо за участие! Надеюсь, вам понравилось.

Победители.

Div1:

1. ivan.popelyshev

2. al13n

3. WJMZBMR

4. yeputons

5. romanandreev

6. dolphinigle

7. wata

8. Shef

9. shangjingbo

10. azizkhan

Div2:

1. s-quark

2. wayne-ho

3. emrevarol

4. agh

5. lzqxh

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

UPD2: разбор из ап.

A. Открытки и фотографии

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

Сложность решения O(n).

B. Перестановка

Посчитаем количество чисел от 1 до n, которые встречаются в последовательности хотя бы один раз. Тогда ответ есть n минус это количество.

Сложность решения в зависимости от реализации O(n) или O(n logn).

C. История

Отсортируем пары, заданные в условии по году начала события. Будем идти по массиву этих пар и поддерживать значение rg - самый поздний год окончания какого-либо из уже обработанных событий. Тогда если для текущего года окончания события - year, верно что year < rg, то нужно прибавить к ответу единицу, поскольку данное событие покрыто каким-то из ранее обработанных (поскольку все обработанные события имеют левую границу меньше нашей и какое-то из них имеет правую границу rg большую year). После этого пересчитываем rg следующим образом: rg = max(rg, year).

Сложность решения: O(n logn) - на сортировку и O(n) - на решение.

D. Палиндромы

Сначала сделаем небольшой предподсчёт: cnt[lf][rg] - наименьшее количество символов, которое мы должны изменить, чтобы подстрока [lf, rg] стала палиндромом. Это легко сделать за O(n^3) времени и O(n^2) памяти. Теперь будем считать динамику z[i][j] - наименьшее число изменений, которое мы должны сделать, чтобы разбить префикс длины i на ровно j палиндромов. Сначала весь массив заполним бесконечностями, а z[0][0] присвоим 0. Теперь будем делать переходы вперёд: переберём длину len очередного (j-го) палиндрома и сделаем обновление состояния z[i + len][j + 1] значением z[i][j] + cnt[i][i + len - 1]. Ответ есть минимум z[n][i], где n - длина строки из входного файла, а i отрезка [1, k]. Чтобы вывести ответ необходимо в дополнительном массиве сохранить предка для каждого состояния.

Сложность решения: O(n^3) по времени и O(n^2) по памяти.

E. Последний шанс

В этой задаче можно было подумать, что при фиксированном начале строки функция "хорошести" от конца строки монотонная, но это не так (хотя бы на примере строки baaab). Заменим все гласные из строки на число -1, а все согласные на число 2. Теперь легко понять, что подстрока [i, j] будет хорошей, если сумма в подотрезке [i, j] неотрицательна. Обозначим эту сумму sum[i][j]. Очевидно sum[i][j] = p[j + 1] - p[i]. Где p[i] - сумма первых i элементов. Теперь решение становится достаточно понятным. Одним из решений было следующее: отсортируем все частичные суммы вместе с индексом частичной суммы и заведём структуру данных над массивом индесов частичных сумм, позволяющую извлекать максимум на суффиксе, а также изменять значение в точке (в качестве такой структуры подойдёт дерево отрезков). Теперь будем пробегаться по массиву частичных сумм (отсортированных) и для текущего индекса частичной суммы (начала хорошей строки) найдём самую правую частичную сумму больше либо равную нашей. Пусть величина текущей частичной суммы равна s, а её номер - i. Найдём в массиве частичных сумм первую частичную сумму с величиной больше либо равной s. Найдём максимум на суффиксе найденной частичной суммы - это и будет позиция самой правой хорошей границы для i (если эта граница больше i). Для удаления нашей суммы из массива обновим значение в ней величиной отрицательной бесконечности. Таким образом легко найти не только максимальную длину хорошей подстроки, но и количество таких подстрок.

Сложность решения: O(n logn) по времени и O(n) по памяти.