Всем привет!

Скучали? Уверен, что нет! Но так или иначе, вашему вниманию представляется ещё один раунд, к подготовке которого я приложил руку. Добро пожаловать в мир безыдейных задач, заунывно длинных и скучных условий и плоских шуток в анонсах.

В этот раз раунд для вас готовили Ильдар Гайнуллин (300iq) и я (ну мне стыдно делать ссылку с этим цветом, сами знаете, кто). Мы хотим поблагодарить Владислава Исенбаева (winger), Константина Семёнова (zemen), Алексея Шмелева (ashmelev), Ивана Смирнова (ifsmirnov) и Александра Фетисова (AlexFetisov) за прорешивание раунда и помощь в подготовке. Также отдельная благодарность отходит Николаю Калинину (KAN) за его помощь в роли координатора и, конечно, MikeMirzayanov за polygon и codeforces.

Мы очень надеемся, что вам понравятся задачи, удачи на контесте!

UPD. Также спасибо akvasha за то, что любезно дополнил наш проблемсет своей задачей.

UPD 2. The contest is over, congratulations to winners!

Div. 1:

1. dotorya
2. Um_nik
3. Radewoosh
4. ainta
5. dreamoon_love_AA

Div. 2:

1. UoA_Kaori
2. noelnadal
3. mtw
4. Kroma
5. Yjsu

Here are editorials.

Всем привет!

На следующей неделе начнётся Moscow International Workshop ACM ICPC. Я буду вести на этих сборах лекцию по быстрому преобразованию Фурье, в связи с чем я подготовил конспект, в котором описал большую часть того, что нужно знать про него для использования в контестах. Даже если вы считаете, что знаете FFT, советую посмотреть, там всё ещё могут быть новые идеи для вас. Ближе к лекции также будет английский вариант :)

P.S. Пользуясь случаем, напоминаю о том, что я сейчас веду паблик вконтакте, в который выкладываю какие-то интересные и новые для меня идеи. Наиболее важные я дублирую в постах здесь, но всякая другая мелочь, не всегда связанная со спортивным программированием, остаётся именно на страницах паблика. В частности, часть конспекта сделана на основе материала, который я раньше выкладывал в него. В планах есть некоторое расширение, как перевод на английский и открытие канала в telegram.

UPD: Добавлена английская версия. Также в русской версии добавлен параграф про вычисление последовательностей методом разделяй и властвуй.

Hello CodeForces Community!

The clock is ticking and Chef is ready with Lunchtime meal of October. So get ready to knuckle down October Lunchtime and mark your calendars for below. Joining me on the problem setting panel, we have:

• Problem Setter: chemthan (Trung Nguyen)
• Problem Tester & Editorialist: adamant (Alexander Kulkov)
• Contest Admin: kingofnumbers (Hasan Jaddouh)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below after the contest.

So, note down the details and be there when the contest starts:

Time: 28th October 2017 (1930 hrs) to (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/LTIME53

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: * Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

Всем привет!

Я тут подал предложение о введение PBDS из SGI STL в российскую национальную рабочую группу по стандартизации С++. Кто не в курсе -- это проработанный концепт сбалансированных бинарных деревьев, с достаточно гибкой возможностью поддержки метаданных в вершинах (см. здесь). Для нас наиболее видная особенность -- наличие встроенных order_of_key и find_by_order, которые отсутствуют в set и map. В случае добавления pbds в стандарт мы также можем ожидать, что там, наконец, починят merge и split, которые сейчас работают за вместо заявленных .

Предлагаю сообществу codeforces поучаствовать в обсуждении данного предложения.

UPD: Предложение на std-proposals.

Hi everyone!

tl;dr. If you write the following code:

void dfs_sz(int v = 0) {
    sz[v] = 1;
    for(auto &u: g[v]) {
        dfs_sz(u);
        sz[v] += sz[u];
        if(sz[u] > sz[g[v][0]]) {
            swap(u, g[v][0]);
        }
    }
}

void dfs_hld(int v = 0) {
    in[v] = t++;
    for(auto u: g[v]) {
        nxt[u] = (u == g[v][0] ? nxt[v] : u);
        dfs_hld(u);
    }
    out[v] = t;
}

Then you will have such array that subtree of correspond to segment and the path from to the last vertex in ascending heavy path from (which is ) will be subsegment which gives you the opportunity to process queries on pathes and subtrees simultaneously in the same segment tree.

Inspired by Vladyslav's article and Alex_2oo8's problem Persistent Oak. You can find my solution to this problem here to learn how it can be used to maintain persistent hld over the tree.

Всем привет!

Я тут всё пишу разбор к June Challenge на Codechef. Задача Euler Sum может быть решена довольно интересной идеей, которой, как мне кажется, стоит поделиться. Спасибо I_love_natalia за то, что поделился. Собственно, вот:

Всем привет!

Мне понравилась идея тезисно излагать интересные вещи и идеи, как это было в предыдущем моём одноимённом посте. К сожалению, Codeforces не вполне предназначен для такого формата, так как подразумевает скорее редкие, но обширные и детализированные посты, чем относительно частые и короткие, что было бы удобнее мне. Но мне всё же захотелось попробовать писать в другом формате, поэтому я решил в тестовом режиме завести под это дело паблик вконтакте. Пока что там 10 постов, но в планах вести там активность регулярно. Надеюсь, будет интересно :)

В общем, вот: https://vk.com/mindbun

Всем привет!

Любители ли вы задачи, которые расчитаны на Ad Hoc решение? Я — терпеть не могу! Поэтому я решил сделать подборку идей, которые могут быть применены к достаточно большому классу задач. Добавляйте ещё, если о чём-то забыл. :)

is it true that ?

Hi everyone!

23^rd edition of Week of Code will start soon. This time challenges were set by me (adamant) and tested by wanbo. Also thanks CherryTree for some help. This is first contest which entirely consists of my problems and I tried my best to make them interesting to you. Hope everyone will find at least one problem that matches ones taste :)

P. S. And some rules if you don't know them yet: Monday through Sunday, one new challenge will be unlocked each day for you to solve. The maximal score decreases by 10% at the end of every 24 hours. Your submissions will run on hidden test cases at the end of every 24 hours. Only the last submission time counts. And as usual, the top 10 hackers on the leaderboard win exclusive HackerRank T-shirts.

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

Hi everyone!

As you may know, it is possible to build a suffix automaton for a set of strings as well as suffix tree consisting of all suffixes of strings from the set. Question is as follows: for each string S_k consider set V_k of vertices/states of tree/automaton that corresponds to the substrings of S_k. Is it true that ? Can you prove it or make a counter-example?

Всем привет!

Да-да, вы всё правильно поняли, после долго перерыва в четыре месяца с того момента, как на codeforces был последний div. 1 раунд, не приуроченный к какому-нибудь соревнованию, вы вновь имеете уникальнейшую возможность поучаствовать в обычном codeforces-раунде. Да, именно то, что написано на упаковке.

Никаких футболок для top-x участников! Никаких многоуровневых систем отбора за право бороться за суперприз! Никаких эзотерических языков или оптимизационных задач! Да мы вам даже разбалловку до самого конца раунда не объявим! Всё будет именно так, как это было в старые добрые времена.

Итак, этот раунд для вас готовили Иван Смирнов (ifsmirnov) и я (adamant). Мы хотим поблагодарить Максима Ахмедова (Zlobober), Александра Фролова (fcspartakm), Эдварда Давтяна (Edvard) и Михаила Мирзаянова (MikeMirzayanov) за помощь в подготовке раунда, его прорешивание и дельные советы. Отдельно спасибо Edvard за то, что он выступил в роли координатора в этот раз и традиционно MikeMirzayanov за системы polygon и codeforces.

Всем удачи! Мы очень надеемся, что вы получите получите много удовольствия, участвуя в раунде :)

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

Div. 2: 500-1000-1500-2000-3000

Div. 1: 500-1000-2000-2000-3000

UPD. 2. Также спасибо большое Александру Фетисову (AlexFetisov). Прости, пожалуйста, совсем забыл тебя отметить :)

UPD. 3 Если вы пропустили разбор, то он здесь.

Всем привет!

Осенью на физтехе проходили сборы по программированию Moscow International Workshop ACM ICPC. На них мне довелось прочесть лекцию по суффиксным структурам (на самом деле, были затронуты только суффиксное дерево и суффиксный автомат). В связи с этим я хотел бы предоставить вашему вниманию конспект лекции. Собственно, вот русская и английская версии. Приятного просмотра и счастливого Нового года :)

P.S. любая критика, предложения, пожелания и вопросы всячески приветствуются.

P. P. S. Я попытался достаточно подробно описать доказательство линейности работы, но, скорее всего, оно до сих пор тяжело воспринимается. Вы получите +100 единиц кармы, если разберётесь в нём и предложите более простой для понимания вариант :)

UPD: Спасибо Burunduk1 за помощь в форматировании кода :)

UPD2: См. также статью на Википедии по этой теме. Я являюсь основным автором текущей (29 октября 2021) версии статьи.

Всем привет!

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

Итак, сама задача: дана строка S. Разбейте её на минимально возможное число палиндромов. Довольно незатейливо, не так ли? Задача довольно популярна. Её можно найти, например, здесь или здесь. Однако, где бы вы её не нашли, ожидаемое решение в лучшем случае будет квадратичным (а то и кубическим). Здесь же будет описано решение этой задачи за в онлайне относительно приписывания символа в конец строки (т.е. ответ будет получен для каждого префикса). Также будет рассмотрена задача разбиения строки на k палиндромов и её сведение к разбиению на минимальное число палиндромов.

Можно сказать, что предыдущая часть. Даже если вы считаете, что знакомы с суффиксным деревом, рекомендую просмотреть код внизу.

Всем привет! Наконец, я до него добрался :)

В данной статье я хотел бы избежать длинных и сложных теоретических выкладок, которые долго отпугивали меня от данного алгоритма. Так что сразу к делу. Доказательств приводить не буду, а больше внимания уделю особенностям реализации. Доказательства поищите где-нибудь на stackoverflow (лично я черпал знания об алгоритме именно оттуда) или на wiki-конспектах ИТМО или в книге Гасфилда или в конспекте Юрия Лифшица... Или ещё где-нибудь, где таким любят заниматься.

Всем привет!

Недавно на тренировочных сборах MIPT: The Fall на контесте от Александра Milanin была задача с Petr Mitrichev Contest 7. Суть её заключалась в том, что нам был дан граф и множество запросов вида "допустим, мы удалили из графа k ≤ 4 рёбер. Остался ли он связным?" Я не знаю, какое решение предполагалось автором (буду благодарен, если кто-то расскажет или скажет, где его можно найти, говорят, там что-то красивое :), но далее я хочу рассказать о решении более общей задачи, когда рёбра произвольно добавляются и удаляются, за в оффлайне. Первый алгоритм с такой оценкой был получен Дэвидом Эппштейном в 1992 году сведением к fully dynamic minimum spanning tree problem, однако здесь речь пойдёт о более простом алгоритме, предложенном в 2012 году Сергеем Burunduk1 Копелиовичем.

Всем привет!

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

Всем привет!

Как некоторые уже знают, на этих летних сборах в Петрозаводске droptable презентовал новую структуру данных, а именно дерево палиндромов. Я имел честь поучаствовать в изучении структуры за полгода до этого, о чём и хочу теперь рассказать :)

Всем привет!

Сегодня начались летние петрозаводские сборы. Надеюсь, не нарушу никаких негласных запретов, написав о них :)

Если вы, как и я, входите в группу людей, которые не имеют возможности участвовать в этом празднике жизни, можете следить за ходом сборов и "болеть" за любимые команды, например, на SnarkNews или на acm.math.spbu.ru.

Всем привет!

Некоторые из вас могут помнить мою статью про policy based data structures. Кроме обзорной статьи на эти структуры, я также хотел написать про возможность использования самописного Node_Update в структуре. Тогда мне так и не удалось выделить на это достаточно времени, однако теперь я могу и хочу наверстать упущенное и поделиться с вами новыми знаниями.

Всем привет!

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

Всем привет!

Буду краток. Возможно ли искать число K-инверсий быстрее, чем за ? Если да, то как? Если нет, то почему?

Всем привет!

Ни для кого не секрет, что в спортивном программировании достаточно часто приходится работать с графами^{[источник?]}. Зачастую нам для наглядности приходится эти графы ещё и рисовать. И, возможно, некоторые пользователи уже знают, что с этим делом необычайно хорошо справляется пакет утилит для визуализации графов GraphViz, который парсит код с уже упомянутого мной языка DOT в наглядную картинку с соответствующим графом.

Пример графа, который можно получить с помощью graphviz — сжатое суффиксное дерево для строки abaabbaaa. Да, граф содержит небольшую ошибку, но это не главное :)

Теперь, собственно, к теме. Как вы относитесь к тому, чтобы поддержка языка DOT была добавлена в редактор codeforces? Лично я считаю, что это было бы круто, а вы? :)

P.S. Полезные ссылки по теме:

• Статья, в которой описываются основные методы языка DOT, с примерами
• canviz — библиотека на javascript для рендера графов с языка DOT

Всем привет! Недавно меня заинтересовала такая задача: дано дерево с корнем в вершине 0. Поступают запросы двух видов.

1. Добавить к вершине k сына.
2. Выдать номер предка вершины k, у которого высота равна h.

Вершины пронумерованы в порядке добавления.

Пока что я знаю только два метода решения:

1. Двоичный подъём. Ну тут всё очевидно, времени и памяти.
2. С помощью индексированного двоичного дерева поиска (например, неявная дерамида) поддерживаем эйлеров обход графа. Далее либо сводим к k-ой порядковой статистике на префиксе, либо храним для каждой высоты список вершин и находим нужную бинарным поиском. Это потребует O(n) памяти, но времени (возможно, при грамотной реализации можно и , но я точно не знаю), ещё и с большущей константой.

Интересно то, что оба метода подозрительно похожи на LCA. В связи с этим возникает вопрос — может, задачу можно как-то свести к LCA непосредственно? Ну и, конечно, интересно, какие ещё есть способы решения этой задачи, в том числе и в оффлайне.