Hello, Codeforces!

I want to invite all of you to participate in HourRank 14.

There will be four problems to solve in ONE hour. I am the author of all the problems in this contest and I hope you will enjoy solving them. Also, I would like to say thanks to danilka.pro and Shafaet for helping with contest preparation.

The top 10 will get awesome HackerRank t-shirts.

Editorials will be available at the end as usual.

Good Luck and Have Fun! :)

Score distribution is the following: 25-40-60-80

UPD: Unfortunately, contest will be unrated! :(

I am sorry for everything bad happened during the contest.

Hello CodeForces Community,

I would like to invite you to participate in 101 Hack 41 will be held on Tuesday, 20 of September. The problems were set by me (Yury Bandarchuk) and josdas (Stanislav Naumov), tested by wanbo.

101 Hack is back with its 41st edition! Passionate programmers will enjoy solving algorithmic challenges. It's all about speed, accuracy and efficiency: 5 challenges in 120 minutes. Every second counts!

Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Hope, you will participate and enjoy the problems.

Good luck && have fun!

Пока у всех на слуху IOI, третья победа Гены и много много других новостей, футболки Google Code Jam уже начали приходить top-1000 из второго раунда.

Давайте делиться, кто уже получил футболку?!

Всем привет!

Не так давно я стал интересоваться работой с различными API и языком Java. После некоторого времени обдумывания я решил сделать небольшое приложение (CodeforcesSurfer), с помощью которого можно будет быстро получить интересующую информацию будь то о пользователе, соревновании или о чем-нибудь еще.

Решился на это дело я лишь сегодня :D Ноо, тем не менее, что-то уже успел написать...

Хочу подчеркнуть, что данное приложение (или, если так можно сказать, проект) создается для получения навыков работы с API, JSon, Java, Java GUI и т.д.

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

Проект лежит тута.

Буду рад любым комментариям и предложениям!

P.S. главное — не обращайте особого внимания на дизайн:D

Скачать текущую версию можно здесь .

P.P.S Выглядит это сейчас примерно так:

Hello everyone!

I am high school senior (will be freshman this fall) now. After some time of considering I decided to find some programming summer camp. Unfortunately, I met some difficulties with finding good camp. I think that maybe someone who is reading this post now knows about such programs in your college or university.

I will appreciate any help!

Thanks in advance!

Hello CodeForces Community,

I would like to invite you to participate in HackerEarth March Easy Round that will be held on Tuesday, 01 of March. The duration of the contest if 3 hours.

The problems were set by me (Yury Bandarchuk) and tested by RomaWhite (Roman Bilyi). The difficulty of this round will be like usual Div. 2 Round or a little bit easier.

As usual all the problems will have partial scoring.

In any case, Good Luck && Have Fun all of you! See you on round!

UPD: Contest is over! Congratulations to winners!

Also, sorry for bugs with problem "Benny and Triangle", but in any case I hope you liked the problems.

Hello CodeForces Community,

I would like to invite you to participate in 101 Hack Feb 2016 will be held on Sunday, 21 of February. The problems were set by me (Yury Bandarchuk) and tested by CherryTree (Siarhei Kulik) and wanbo. Also, I am so grateful to pashka for solving some problems on Java.

101 Hack is back with its 34th edition! Passionate programmers will enjoy solving algorithmic challenges. It's all about speed, accuracy and efficiency: 5 challenges in 120 minutes. Every second counts!

Top 10 winners on the leaderboard will receive a HackerRank T-Shirt.

Hope, you will participate and enjoy the problems.

Good luck && have fun!

UPD: Contest has ended! Congratulations to winners! Editorials for every problem are available now.

1. riadwaw

2. I_love_Tanya_Romanova

3. Errichto

Want to hear your feedback about the problems!

Всем привет!

Ну что же, вот и пришел сезон личных олимпиад в Беларуси. Совсем скоро, 12-13 января по всей Беларуси будет проходить областная олимпиада по информатике.

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

В прошлом году тоже было что-то похожее, кому интересно — вот ссылка.

Good luck && Have fun!

Day 1.

1. Тупая реализация! Главное, аккуратно чекать случай, когда есть ### и выстрел в центр.

2. A — массив ответ. A[1] = y. Дальше просто добавляем единичные биты в свободные позиции. Проверяем, что набралось N элементов — выводим ответ, иначе -1.

3. Дп F[pref] — ответ для префикса pref. left[x] — левая граница числа x, right[x] — правая соответственно, cnt[x] — количество. Пересчет

• f[pref] = f[pref — 1]
  • если pref == right[a[pref]], то f[pref] = max(f[pref], f[left[a[pref]] — 1] + cnt[a[pref]]

Ответ лежит в f[n].

1. Брут за N * K^2 довольно простой, фиксим позицию которая так и останется стоять (это N * K) а дальше смотрим как нужно повернуть минимально остальные диски.

По ограничению из условия — это 60.

Итого — 360 очень простых баллов.

Кто знает как решать 4-ую на сто?

Day 2.

1. Обычная потная реализация! (фу-фу-фу давать такие задачи два дня подряд).

2. дпшка f[i][j] — где i — последний чувак, которого мы поставили, j — сколько пьедесталов рассмотрели. f[i][j] — минимальная высота, на которой стоит i — парень.

3. дпшка f[i][j] — где i — последнее письмо, которое мы доставили, а j — сколько раз мы ходили вдоль домов. f[i][j] — максимальное количество писем, которые можно доставить с такими параметрами. Пересчет фенвиком, ибо думаю что ДО должно упасть.

4. Единственная задачка, которая требует чутка внимательности и соображалки. Ответ всегда 2!!! Исходя из этих соображений просто закидываем весь набор в сет пар (количество книг, тип книги). Дальше просто жадно берем первый и последний элемент. Они гарантированно замостят всю строку! Ну вот и все, генерим outputs и получаем 100 баллов.

Итого — 400 очень простых баллов :).

Задача A.

Все что нужно было сделать в этой задаче — разобрать несколько случаев. В силу того, что все числа были до 10⁸ вычисления проводить можно было в 32-битном типе данных.

Разобрать нужно было следующие случаи:

• Дом первый магазин второй магазин дом

• Дом первый магазин второй магазин первый магазин дом

• Дом второй магазин дом первый магазин дом

• Дом второй магазин первый магазин второй магазин дом

Асимптотика: O(1)

Задача B.

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

Затем нужно пройти по массиву и разобрать несколько случаев, предварительно нужно завести флажок для ответа Ambiguity:

Пусть текущий элемент массива — b_i

• Если существует более одного элемента, из которого можно получить b_i, то нужно поднять флажок, который отвечает за Ambiguity
• Если не существует ни одного элемента, из которого можно получить b_i, то нужно вывести Impossible
• Если элемент один, то просто заменяем b_i на число, из которого мы могли получить данное b_i

В конце, если флажок поднят, то нужно вывести Ambiguity, иначе Possible и полученный ответ.

Асимптотика: O(N)

Задача C.

Первым делом нужно понять, как выглядит оптимальный ответ.

Пусть H_i — отсортированная последовательность h_i. Пусть E — множество индексов последних элементов каждого блока. Тогда утверждается, что e E, отсортировав первые e элементов последовательности h_i получатся в точности e первых элементов последовательности H_j.

Тогда, нетрудно заметить, что размер E будет являться ответом на задачу.

Для начала нужно посчитать два массива: prefmax и suffmin, где prefmax_i — максимум из элементов a₁, a₂, ..., a_i, а suffmin_i — минимум из элементов a_i, a_i + 1, ..., a_n.

Чтобы получить ответ, нужно посчитать количество индексов i таких, что prefmax_i  ≤  suffmin_i + 1.

Асимптотика: O(N)

Задача D.

Будем решать задачу для n ≤ m, затем просто поменяем местами и выведем ответ. Нужно не учесть квадраты два раза!

Давайте воспользуемся следующей формулой для фиксированных n и m (n ≤ m) и чтобы вычислить x.

Если еще немного упростить, то получим

Затем применяем сумму квадратов и сумму первых k чисел для решения этой задачи.

Получаем 6x = 6n² * m - 3(n² + n³ - nm - n²) + 2n³ - 3n³ + n = 3 * m * n² + 3 * m * n - n³ + n

Так как мы решали для n ≤ m то 3n² * m =  ≈ n³, а это значит, что n можно просто перебрать до двух корней кубических.

Асимптотика:

Задача E.

Решение этой задачи — динамическое программирование.

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

Тогда, понятно, что ответ — это ни что иное, как f_{0, 2ⁿ - 1}.

Тривиальными будут состояния, где в маске только лишь один единичный бит. В таких случаях f_root, mask = 1.

Будем считать эту дп рекурсивно с запоминанием состояний. Чтобы сделать переходы, нам нужно выбрать какую-то маску newMask, которая обязательно является подмаской маски mask. Затем следует перебрать корень newRoot в маске newMask. Так же, для того, чтобы не посчитать одно и то же дерево несколько раз наложим условие на маску newMask. А именно, будем брать только такие маски newMask, в которых старший бит (не отвечающим за root) совпадает со страшим битом (не отвечающий за root) маски mask. После чего, нужно проверить выполнение всех условий на ребра и на lca. Если все хорошо, то обновить . Где — исключающее или.

Что касается проверки, на lca то ее можно делать за O(N²) — предварительно для каждой пары запомнив lca или в худшем случае за O(Q) просто пробегая по всем парам вершин, для которых какая-то вершина v является lca. В случае с O(Q) состояний достижимых не очень много и поэтому дпшка будет работать довольно быстро.

Асимптотика: O(3^N·N³) или O(3^N·N·Q)

Всем привет!

Совсем скоро, 20 ноября в 19:35, состоится Codeforces Round #332 (Div.2), автором которого являюсь я. Это мой второй раунд и я надеюсь, что не последний.

Спасибо Дмитрию Рожкову (rui-de) за прорешивание раунда и подготовку задач, а так же Владу Вишневскому (Vladik) за красивые картинки к задачам. Большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке раунда. И, как обычно, спасибо Марие Беловой (Delinur) за перевод условий на английский язык и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Контест будет длиться два часа. Что касается задач, то ни для кого не секрет, что на дне океана есть ананас Губки Боба и ресторан "Красти Крабс", уютный пляж и Медузные Луга ... Но Губке Бобу и его друзьям понадобилась помощь, помоги им!

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

Как обычно, разбалловка будет объявлена позже.

UPD: Разбалловка выглядит следующим образом — 500 — 1000 — 1500 — 2000 — 3000

Разбор задач.

Div. 2 Winners

jerjerismygf

rakhashov.maksat

jeremy624lolz

Div. 1 Winners

MrDindows

anta

ngfam_kongu

Congratulations!

Hi, guys! I need help with task on main.edu.pl in which I should write a library. I try to solve this task. So, How I can solve this task offline. (I want to use parallel binary search, but I don't know how to write such library.

Всем привет!

Совсем скоро, 13-14 января, пройдут основные туры областной олимпиады в Беларуси.

Предлагаю после туров обсуждать задачи и делиться результатами здесь!

GL && HF!

UPD: Ну что, как вам задачки первого тура?

Краткие соображения по решению задач (SPOILER) :

1. Тут все ясно, просто массив на сто элементов.

2. Перебираем R до корня, затем бинарным поиском ищем максимальное C. Не забыть лонги.

3. Два указателя + добавить спереди нулей, чтобы числа были одной длины. Не забыть при выводе убрать лидирующие нули. Не забыть лонги [2].

4. Дп по дереву: dp[ver][0] — максимальный путь до какого-либо из листов + мы не снимали налог ни с одной дороги, за которые отвечает вершина ver. dp[ver][1] — то же самое, только мы уже сняли один налог. Затем просто два максимума по детям dp[ver][1] и dp[ver][0].

Надеюсь это должно работать =)

Условия первого дня здесь.

Второй тур завершен. Мне задачи понравились :)

Опять соображения :

1. Два указателя на концы строк и погнали.

2. Раскладываем на простые множители и каждый множитель доводим до степени, кратной трем. Это и будет ответ.

3. Посчитаем H[i][j] — количество спичек на одинаковых местах у чисел i и j.
Затем посчитаем такую динамику : dp[len][sum][eq], где len — длина префикса, который рассмотрели, sum — сумма спичек, которую набрали, eq — сколько на нормальных местах стоит, что не пришлось менять. Затем ответом будет просто сумма по всем dp[n][mySum][x], где mySum — x <= k. Ограничение по памяти не позволяло считать такую дп, поэтому считаем просто по слоям.

4. Первые 8 тестов — динамика за N^2 * K. Где dp[len][used] — минимальная стоимость, если мы уже набрали used групп, и последняя группа закончилась в позиции len. Предварительно нужно отсортить массив. 9-й тест — просто костыльный, там все тройки в инпуте. А в 10й написал жадность — сделал группы макс размера и следовательно остались ещё группы. Тогда уменьшаю самую большую группу и добавляю новую или добавляю в старую, но меньшего размера. Улучшаем пока улучшается.

Делитесь своими идеями и решениями, а я буду надеяться, что это все зайдет! =)

Кидайте резы по вашим областям мне в лс.

UPD: Есть резы Брестской, г. Минска, Гомельской области и Лицея БГУ и , скидывайте резы свои, жду!

Неполные результаты : Link.

UPD: Добавил Могилевскую область.

Всем привет! Совсем скоро, 29-30 ноября 2014 года состоится Пятнадцатая Всероссийская командная олимпиада школьников по программированию. Хочу поинтересоваться, где можно будет найти текстовую и видео трансляции?

467A - George and Accommodation

В этой задаче нужно было просто посчитать количество пар, у которых q_i - p_i ≤ 2

Асимптотика: O(N)

467B - Fedor and New Game

В этой задаче нужно было уметь считать количество различных битов в двух числах. Как вариант, можно просто побежать по битам и посчитать количество различных. Ещё, как вариант, если исходные два числа X и Y, то количество различных битов равнялось бы количеству единиц в числе X xor Y, где xor — операция исключающего или.

Асимптотика O(M·N)

467C - George and Job

Решение этой задачи — динамическое программирование. Изначально нужно посчитать psum_R, где psum_R — сумма на префиксе массива p длиной R.

Обозначим dp_i, j — максимальная прибыль которую может получить Юра, если мы уже выбрали i последовательностей и последний элемент в i-ой последовательности имеет индекс j.

Очевидно, что если i·m > j, то dp_i, j = 0. Иначе dp_i, j = max(dp_{i, j - 1}, dp_{i - 1, j - m} + psum_j - psum_j - m) Ответом будет dp_k, n.

Ещё нужно было не забыть использовать long long при вычислениях.

Асимптотика: O(N·K)

467D - Fedor and Essay

Первое, что нужно сделать, чтобы облегчить себе работу — перевести все строки в нижний регистр. Затем словам дать номера. Различным словам дать различные номера, а одинаковым — одинаковые.

Затем, из всех строк нужно построить граф. Пусть каждое слово — просто вершина. А пара слов синонимов X и Y — ребро между вершинами, которые отвечают за данные слова. Ребра ориентированные. Также, для каждого слова мы должны хранить его длину и количество букв «R». Будем использовать номера, данные словам, для построения графа.

После создания графа, у нас мог быть петли, кратные ребра, циклы. Поэтому нужно сжать все сильно связные компоненты в одну вершину. После чего задача состоит в том, чтобы посчитать dp_ver — пара, отвечающая за минимальное количество букв «R» и минимальную длину слова с минимальным количеством букв «R», которым можно заменить слово, за которое отвечает вершина ver.

Пересчет очевиден — dp_ver = max(dp_nextVev, dp_ver), где nextVer — все вершины, в которые можно пойти из ver. Максимум из двух пар берется как у pair в C++.

Затем нужно пройти по всем словам текста, получить номер вершины, который соответствует нужному слову. Пусть это ver. Тогда к ответу нужно прибавить dp_ver.

Также, важно было не забыть использовать long long при вычислениях.

Асимптотика: , где w — множество всех слов, которые есть в тексте и в словаре.

467E - Alex and Complicated Task

Данная задача решалась жадно.

Алгоритм решения такой:

Набираем числа из массива a по очереди, пока в последовательности набранных чисел(далее G) не найдется нужная нам четверка. Напоминаю, что нужная четверка чисел имеет вид: [c₁, c₂, c₃, c₄] = [x, y, x, y]. Если набрали такую четверку чисел, то добавляем в ответ. Очищаем G и v (далее будет описано, что такое v).

Очевидно, что этот алгоритм оптимален.

Для удобности сжимаем числа в массиве a. То есть каждому числу присваиваем его порядковый номер в отсортированном списке всех уникальных чисел из массива a. Это делается, потому что в дальнейшем нам удобнее использовать числа порядка O(N). Теперь как быстро узнать, что в G найдется нужная нам четверка.

Давайте для каждого уникального числа X хранить список его позиций в G. Назовем этот список v_X. Теперь просто можно обработать операцию добавления числа в G. Пусть добавляемое число — это X. Добавим число X в список G. Пусть i — позиция добавленного числа в список G.

Теперь давайте добавим позицию i в список v_X.

Можно заметить такой факт:

Если размер списка v_x равен 4, то мы нашли нужную нам четверку.

Можно заметить ещё один факт:

Если до добавления мы не нашли нужную четверку чисел, а после добавления нашли, то последнее добавленное число является последним в четверке. То есть наше последнее добавленное число равно c₄. Значит мы знаем позицию последнего числа из четверки. Давайте переберем позицию числа c₂. Всего возможных позиций числа c₂ не больше двух, так как всего позиций, на которых стоит число c₂, не больше трех (смотреть предыдущий факт). Одна позиция уже занята числом c₄. Итого остается максимум две позиции. Пусть мы проверяем, то что c₂ имеет позицию L, а c₄ имеет позицию R. Остается только проверить существование таких c₁ и c₃, что c₁ = c₃ и их позиции P и Q соответственно. P и Q должны удовлетворять следующим условиям: 1 < P < L, L < Q < R. Это очень легко проверить. Давайте заведем массив T. T_i =  максимальное j, что G_i = G_j. Поддерживать такой массив не составляет труда. Теперь проверка будет требовать только одного запроса: Максимум на отрезке [1, L - 1] в массиве T. Пусть результат запроса равен Z. Если он удовлетворяет условию L < Z < R, то четверка существует. Этим запросом мы нашли позицию числа c₃ в списке G. По этим данным мы можем восстановить четверку.

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

Итоговая асимптотика: .

Всем привет!

Совсем скоро, 18 сентября в 19:30 MSK, состоится Codeforces Round #267 (Div. 2), автором которого являюсь я. Это мой первый раунд и я надеюсь, что не последний.

Спасибо Феде Коробейникову (Mediocrity) и Леше Вистяжу (netman) за помощь в тестировании и подготовке раунда. Также хочу выразить благодарность Геральду Агапову (Gerald) за помощь в подготовке задач, Марие Беловой (Delinur) за перевод условий на английский язык и Михаилу Мирзаянову (MikeMirzayanov) за Codeforces и Polygon.

Я надеюсь, что каждый найдет себе задачу по вкусу, а также с головой окунется в студенческую жизнь.

Разбалловка стандартная.

Удачи! =)

Поздравляем победителей!

1)potaty

2)ryu0128

3)nisshy

4)fangpanyan

5)Bredor

Разбор задач

Всем привет! Только что закончился Russian Code Cup Qual 4. Предлагаю обсудить задачи здесь. P.S. что за 18-й тест в задаче D и как её решать?

Всем доброго времени суток! Я недавно начал изучать Java. Хочу затем использовать её на контестах, а для начала нужно набить руку:) Так вот начал я с тренировки http://codeforces.me/gym/100230 (задача B). Написал Дейкстру с кучей, ввод через BufferedReader, но все равно я получил ТЛЕ на 11-ом тесте((( Вот код: http://pastebin.com/R6zGCpPm Помогите чайнику в джаве) Заранее спасибо!

Всем привет! Хочу поучаствовать в tc. Зарегистрировался там я уже давно, пописал немного и забросил. Недавно узнал, что сегодня будет контест и решил его написать. ... Итак, я зашел в арену. Затем, когда выбрал контест и нажал Register, я получил сообщение: "You must be a registered competition user to compete in this round". Что мне делать??? Где я ещё не зарегистрировался?

Всем доброго времени суток! Недавно решал III (XIV) открытый командный студенческий чемпионат Поволжья по спортивному программированию, И у меня возникло пару вопросов. Вот один из них: Как найти в массиве два элемента xor которых минимален? Заранее спасибо!

Всем доброго времени суток! Посмотрел на сайте usaco.org, что завтра начинается фервальский контест. Мне бы очень хотелось принять в нем участие. Подскажите, как зарегистрироваться на контест и вообще весь процесс олимпиады. Заранее спасибо!

С 13 по 16 января проходила областная олимпиада по информатике. Предлагаю здесь делиться резами и обсуждать задачи:)

Доброе утро всем программистам! Я хочу узнать, что будет с решением задач...Вы спросите в каком смысле? Так вот, я хочу узнать, будет ли зависеть результат от времени сдачи той или иной задачи, будут ли штрафы за попытки и т.д.? Просто, что-то никак не могу найти про это информацию... Спасибо :)

Привет всем любителям и профессионалам олимпиадного программирования! Я учусь в 8-ом классе, занимаюсь программированием полтора года. Из языков знаю Pascal, частично С++. Недавно ездил на область, где взял третий диплом. Правда некоторые "дети" (шестиклассники) брали первые дипломы. Вообщем я хочу получить какую-либо программу или "путь", по которому можно быстро получить рост в программировании и главное, чтобы этот рост был виден. Вы уж помогите, заранее спасибо! P.S. мне в след. году респу брать надо. Вот уроки программирования http://znatok-pascal.ucoz.ru/publ/1 тут брал. Задачи на acmp решаю, тут решаю, может ещё чего-то не хватает??? Или же мне просто нужно каждый день решать задачи и не сбавлять обороты?