(this was originally intended as a comment to another post, but it turned out very lengthy, so I separated it into its own post)

As it's often in debates, I think in this one there is too much polarization on both sides (people just attack each other), and a lot of ambiguity. I think there are some points to be made.

Premise

1. Let's be kind to each other. Like it or not, this is just a current trend in the history of Codeforces, and it too will pass. No need to attack anyone personally. If you want to criticize, let's provide constructive suggestions.

2. I've set contests before too, and I know that setting problems and coordinating is a very difficult job. It requires a lot of hard work, skill, experience, and patience. So like Anton's and other coordinators' style or not, let's not forget that they have done a lot of work, and let's thank them for that. Thank you!

3. It's also very mean to single out one person for the possible issue. While Anton may have a lot of impact here, there are many moving factors at play, and let's consider it as a "trend", and not particularly tie it to a single person. Let's discuss the "trend" itself and how we can possibly make thing better if needed. I also personally enjoy a lot of Anton's problems too, even though I find them maybe too much math/adhoc/etc heavy (especially when there are several in a row). But let's discuss this in depth below.

4. I also don't find comparison to Atcoder fully valid. If you look at ABC and ARCs, you will find plenty of algorithms, data structures, and so on. Sure, AGC may be skewed towards adhoc and math, but that's not only what Atcoder is.

5. Some fun observation: I find a lot of very high rated people really enjoy AGCs, and adhoc/constructive/etc problems. I personally can't really appreciate AGC beauty myself (probably because I am less skilled and don't usually get to problem C/D), and I think similar thing happens here. Very high skilled people may like adhoc/etc more for different reasons (for example, they may find a lot of DP/etc very standard. It's probably easier to come up with a fresh adhoc than with a fresh DP problem), but let's not forget about other 95% of population. For a lot of them, even something like manipulating things in a set may be exciting (especially with a great real life statement). So I think when asking for opinions like in Anton's post, it's important to include a great range of people with different skills; similar thing applies to setting contests.

Defining a problem

1. For the lack of clarity, people use a lot of words to describe the recent trendy problems. Ad-hoc, math, constructive, etc, etc. Let's not pick on these words ("hey, it's not constructive at all!"), because I feel they are used interchangeably for the lack of a clear concept. So what is the current "trend"? I feel there are several things to describe it (only some of them may apply):

   • It's very observation oriented (you consider problem on paper or computer to find some patterns, etc). After you notice something, it becomes easy.
   • It doesn't require much of well-known algorithms and techniques (including, but not limited to, dp, graphs, data structures, sets/maps, etc), and doesn't fit into these standard categories.
   • Often it feels like there is not much benefit from a computer, and implementation is light.
   • It could be purely math competition problem, or not too far from it.
   • I also notice that a lot of these problems have very artificial statement and setting (like you are given array/permutation and some weird limits/operations/structure, and you need to find something). For me, that indeed doesn't add beauty to the problem, and feels repulsive, but of course it's subjective.

2. Related to the previous point. A lot of people try to describe what they want, but do it poorly. They say: we want more data structures/dp/graphs/implementation/standard problems/etc etc. I think there is again a lot of ambiguity and a lack of clear concept, so let's not criticize it as "not every contest should have a DP/data structure problem", or "there shouldn't be standard problems" — this is clearly not what people actually want. Let's also not say that "ad hoc problems matter" or constructive problems are cool. That's also of course true, but I think that's not what this debate is about. So what is it about?

3. I think people generally don't fight against adhoc/constructive problems themselves. They fight against unbalanced distributions in a lot of recent contests, and I agree with them. When there are too many problems with a similar topic, it becomes boring. If the recent trend was "2-3 binary search problems in every contest", then people would fight against binary search too. I think people don't mean "there shouldn't be adhoc problems", or "we want graph problems in every contest", or "DP never appears anymore" — they just say they see a big skew to adhoc problems recently, and it's a valid concern.

So what to do?

1. I think an important discussion would be what is a good problem distribution in a contest should be. Some points:

   • I think it's very possible to give "algorithms/data structure/implementation" problems even as div2 A-D. "Data structure" here can be something as simple as sorting, or using a set, or making elements unique, or a simple parsing. There are a lot of problems that can be set with these.
   • Implementation is also important. I, and I think a lot of other people, find implementation interesting too. Figuring how to best implement something that doesn't seem very elegant at first is a great problem as of itself in programming competitions.
   • Problems in a contest can be beautiful, but their combination can still be bad. I think Global Round 9 is a great example of this. When first 5-6 problems don't need almost any algorithms and are done as "play with a problem on paper, then code something trivial when done" – it gets boring.
   • Let's look at famous well prepared contests, like NEERC ICPC semifinals, IOIs (and other OIs), and Google Code Jam rounds. They often have a great distribution. If there were 50% of adhoc problems there, that would be weird, right?

2. So what is a great distribution for a contest? I may suggest doing something like this to get a good distribution.

   • Let's take a well prepared team contest (like NEERC ICPC semifinal), exclude everything that is team competition related and not suitable for individual contests (really hard data structures, hard geometry, etc), shrink number of problems to 5-6, and take that.
   • Or let's take 8-10 random problems from a good online judge (like Timus, or even CF archive itself), again throw away too hard or weird problems, and that should be good.
   • And anyway if more than 30% of your problems are on the same wide topic, or feel artificial, or something, you should reconsider it and mix things up.

What are your ideas for a good distribution? And what do you generally think on the debate?

Hello, Codeforces

Here is something I've been working on for a while now. It's still in beta, but I think it's in a good shape to share. I think it's relevant to CF community, but if not, sorry for the spam :)

I am an ex-Google software engineer, and I wrote down almost everything I know about interview preparation, and launched a small website. It is something of a preparation course and guide at the same time.

Here is what's inside:

• 40+ articles about everything from resume to algorithms to compensation.
• Selected leetcode problems with hints, solutions and such.
• Code examples and explanations of common algorithms and techniques.
• A place where you can track your interview preparation progress.

Please take a look and let me know what you think. Hopefully, you will find it useful in your own preparation!

Link: https://interviews.school/

P.S. I would appreciate any feedback. Feel free to point to any errors you will find. And what else can I add?
P.P.S I think some articles there will be relevant to people learning competitive programming as well. For example, you can check out articles on sorting, dynamic programming, heaps, and graphs.

Hello, hope you all are well and doing fine!

Recently, I've been solving some old AtCoder problems that are only available in Japanese (with Google Translate and a lot of guessing). Problems are really nice, so I decided to put short English translations of them on GitHub. Nothing fancy, just several sentences describing the core part of each problem. There are 10 translated problems so far:

https://github.com/ADJA/AtCoderTranslations

(current problems are in the 2100–2400 difficulty range)

Contribute?

How you can help: There are ~382 untranslated problems from the early AtCoder Beginner and Regular contests left, so I encourage you all to contribute! No Japanese required.

It takes about 5-10 minutes for each problem (please solve the problem first if you don't speak Japanese), and can be done right from the GitHub web interface.

Please see contributing section in the README for more information: https://github.com/ADJA/AtCoderTranslations#contribute

I think with enough contributors, all problems can be translated just in several weeks. Plus, solving the problems is a good training too. Isn't that a time well spent in the quarantine? :)

Hello, CF community.

About a year ago I wrote and shared a blog post about my approach to interview preparation that helped me get offers from Google, Facebook, Uber and Amazon. I thought that I can share this here too – I have a long experience with competitive programming, and hopefully other people here can find something useful for them:

http://adilet.org/blog/your-ultimate-guide-to-interview-preparation/

Let me know if this helps, and thanks for reading! All questions are welcome :)

Hello, CF community.

I am writing about algorithms for fun and to spread the knowledge.

Please read my new article about stress testing – a useful technique to automatically find bugs in your solution: http://www.algos.school/stress-testing

Would you be interested in the future algorithm articles like this? Please follow algos.school on facebook, twitter, or telegram.

Thanks!

Hello, CF community.

I am starting to write about algorithms for fun and to spread the knowledge. Please read my new article about sparse table – a cute data structure to find range minimums in an array:

http://adilet.org/blog/sparse-table/

P.S. A little bit about myself: I was active in the competitive programming a while ago, especially during my two ACM ICPC World Finals in 2014 and 2015. Currently, I am working for Google and trying to revive some old algorithms knowledge :)

Would you be interested in the future algorithm articles like this? Follow me on twitter here: twitter.com/adiletzx

Better late, than never :) Almost a year have passed, but I finally finished a two-part blog post about our team's (Nazarbayev University from Kazakhstan) journey to ACM-ICPC World Finals 2015 in Morocco.

Here are the links. Enjoy!
http://adilet.org/blog/19-04-16/
http://adilet.org/blog/02-05-16/

It was a fun event, thanks to everybody who made it happen!
And good luck to all teams in Thailand soon ;)

P.S. You may also be interested in a blog post about ACM-ICPC WF 2014 here

550A - Две подстроки

Задачу можно решать разными способами. Авторское решение такое: проверим две возможности — когда подстрока "AB" идет первее "BA" и наоборот. Проверять можно следующим образом: найти самое первое вхождение "AB" в исходной строке и рассмотреть подстроки длины 2 правее. Если среди них встретилась подстрока "BA" — ответ "YES". Аналогично проверяется второй случай. Если оба варианта не выполнены, ответ "NO". Сложность решения — O(n), где n — длина исходной строки.

550B - Подготовка олимпиады

Задачу можно решить полным перебором всех подмножеств задач (всего 2ⁿ подмножеств). Для каждого из подмножеств проверим, удовлетворяет ли оно условиям задачи. Найдем сумму сложностей всех задач, входящих в подмножество, и убедимся, что она лежит в отрезке [l, r]. Найдем также разность между сложностями максимально сложной задачи и минимально сложной задача подмножества и убедимся, что она не менее x. Если подмножество задач удовлетворяет условиям — увеличиваем общий ответ на 1. Сложность решения задачи — O(2ⁿ·n).

550C - Делимость на восемь

Задачу можно решить как минимум двумя способами.

Первый — через "школьный" признак делимости на 8 (число делится на 8 тогда и только тогда, когда число, образованное его последними тремя цифрами, делится на 8). Таким образом, достаточно проверять на делимость на 8 все однозначные, двухзначные и трехзначные числа, образуемые из исходного вычеркиванием цифр. Это можно сделать за O(n³) вложенными циклами по цифрам числа, где n — количество цифр числа.

Второй способ использует динамическое программирование. Будем считать величину dp[i][j], 1 ≤ i ≤ n, 0 ≤ j < 8 — величину, равную 1, если из префикса числа длиной i цифр можно вычеркнуть несколько цифр так, что остаток от деления полученного числа на 8 равен j, и 0 в противном случае. Формулы для пересчета: пусть i-я цифра числа есть a_i, тогда dp[i][a_imod8] = 1 (по смыслу — однозначные числа), dp[i][(j * 10 + a_i)mod8] = max(dp[i][(j * 10 + a_i)mod8], dp[i - 1][j]) (по смыслу — дописывание текущей цифры), dp[i][j] = max(dp[i][j], dp[i - 1][j]) (по смыслу — вычеркивание текущей цифры), где 0 ≤ j < 8. Ответ "YES" будет в том случае, когда для некоторого i выполнено dp[i][0] = 1. Для восстановления ответа также нужно завести дополнительный массив prev[i][j], который будет хранить индекс k такой, что при подсчете dp[i][j] пересчет был сделан из dp[i - 1][k]. Сложность такого решения — O(8·n).

Решение с динамическим программированием:

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) (int) x.size()
#define all(a) a.begin(), a.end()
#define prev sadasdjksgjkasjdklaj
 
const int MAXN = 105;
 
string s;
int n;
bool dp[MAXN][8];
int prev[MAXN][8];
 
int main() {
 
    getline(cin, s);
    n = sz(s);
 
    memset(prev, -1, sizeof(prev));
 
    dp[0][(s[0] - '0') % 8] = true;
 
    for (int i = 1; i < n; i++) {
        dp[i][(s[i] - '0') % 8] = true;
 
        for (int j = 0; j < 8; j++) {
            if (dp[i - 1][j]) {
                dp[i][(j * 10 + s[i] - '0') % 8] = true;
                prev[i][(j * 10 + s[i] - '0') % 8] = j;
 
                dp[i][j] = true;
                prev[i][j] = j;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (dp[i][0]) {
            string ans = "";
            int curI = i, curJ = 0;
 
            while (true) {
                if (prev[curI][curJ] == -1 || prev[curI][curJ] != curJ) {
                    ans.append(1, s[curI]);
                }
 
                if (prev[curI][curJ] == -1) break;
 
                curJ = prev[curI][curJ];
                curI--;
            }
 
            puts("YES");
            reverse(all(ans));
            cout << ans << endl;
            return 0;
        }
    }
 
    puts("NO");
 
    return 0;
}

550D - Регулярный мост

Докажем, что если k — четное, то решения не существует. Пусть наш граф содержит мост(ы), k = 2s — четное число, степени всех вершин графа равны k. Дерево двусвязных (реберно двусвязных, далее слово "реберных" будет опущено для краткости) компонент исходного графа содержало компоненту, связанную с остальной частью графа только одним мостом (не несколькими мостами!) (на самом деле таких компонент как минимум две, но нам достаточно одной).

Рассмотрим эту компоненту. Удалим мост, связывающий ее с остальной частью графа. Тогда в ней будет всего одна вершина степени k - 1 = 2s - 1 и какое-то количество вершин степени k = 2s. Но тогда она будет содержать только одну вершину нечетной степени, что невозможно.

Построим такой граф для нечетных k. Пусть k = 2s - 1 — нечетное число. Рассмотрим отдельно случай k = 1, тогда, очевидно, подойдет дерево из двух вершин.

Для k ≥ 3 сперва найдем минимальное количество вершин искомого графа. Граф будет содержать как минимум один мост и как минимум две двусвязные компоненты, связанные с остальной частью графа одним мостом. Каждая из этих компонент содержит не менее k + 2 вершин (так как одна вершина связана k - 1 ребрами с другими, остальные имеют степень k = 2s - 1 — нечетное число, т.. количество этих вершин должно быть четным, в то же время оно не может быть меньше k = 2s - 1, то есть оно будет не меньше k + 1, что в сумме с одной вершиной степени k - 1 даст k + 2).

Следовательно, во всем графе будет не менее 2k + 4 вершин. Построим граф с таким количеством вершин.

Занумеруем вершины первой компоненты с 1 до k + 2, вторую компоненту построим аналогично первой. Пусть вершина 1 связана мостом с второй компонентой. Соединим ее k - 1 ребрами с вершинами 2, 3, ..., k. Вершины с номерами 2, 3, ..., k соединим между собой попарно и потом между каждой соседней парой, например 2 - 3, 4 - 5, ... (k - 1) - k, выкинем ребро. После соединим вершины 2, 3, ..., k с вершинами k + 1 и k + 2. Также соединим вершины k + 1 и k + 2 между собой. Тогда все вершины компоненты, кроме первой, будут иметь степень k. Точно так же создаем вторую компоненту и соединяем мостом с первой. Искомый граф построен и содержит O(k) вершин и O(k²) ребер.

Асимптотика решения — O(k²).

550E - Скобки в импликациях

Пусть дано выражение , a_i — 0 или 1 для всех i.

Покажем, что решения нет только в двух случаях.

1) a_n = 1.

Это следует из того, что , т. е. никакая расстановка скобок не сможет заменить самую правую 1 выражения на 0.

2) Выражение имеет вид или является его суффиксом, содержащим не менее 2 аргументов.

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

Покажем, что в остальных случаях решение есть.

1) Для выражения 0 ничего делать не надо — ответ 0.

2) Выражение вида . Можно не расставлять никаких скобок, так как значение такого выражения без скобок равно 0.

3) Выражение вида , где вторая опущенная часть состоит только из единиц. Тогда .

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

Привет, Codeforces!

Мы рады сообщить, что 4 июня в 19:30 MSK состоится раунд Codeforces #306, авторами которого являюсь я (Адилет Жаксыбай), и Тимур Сытдыков (Timur_Sitdikov). Раунд будет рейтинговым для участников второго дивизиона, участники первого дивизиона могут, как обычно, поучаствовать в нем вне конкурса.

Хочется выразить благодарность всем тем, кто помог нам с подготовкой раунда: Максиму Ахмедову (Zlobober), который помог нам с подготовкой задач, Бекжану Касенову (BekzhanKassenov) и Сергею Лазареву (SergeyLazarev), протестировавшим контест, и Марии Беловой (Delinur), которая перевела условия на английский язык. Отдельное спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание платформ Codeforces и Polygon.

Кстати, насколько нам известно, Timur_Sitdikov — первый участник с Узбекистана, принявший участие в подготовке Codeforces раунда. Мы надеемся, что все пройдет хорошо :)

Всем удачи!

UPD Разбалловка будет динамической.

UPD2 Разбор можно найти здесь.

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

1. mff

2. I_Love_Nodir.Daminov

3. tun

4. I_love_Ngoc_cmn_Thuy

5. goodhope

Раунд закончен, спасибо всем, кто принял участие!

Привет, Codeforces!

Меня зовут Адилет Жаксыбай, и вместе с Бекжаном Касеновым (BekzhanKassenov) мы являемся авторами раунда Codeforces #294, который состоится 28 февраля в 16:00 MSK. Это наш первый раунд Codeforces, и мы рады пригласить всех поучаствовать в нем. Раунд будет рейтинговым для участников второго дивизиона, участники первого дивизиона могут, как обычно, поучаствовать в нем вне конкурса.

Насколько мы знаем, это будет первый раунд на Codeforces, полностью подготовленный участниками из Казахстана. Мы очень рады, что нам выпала такая честь, и надеемся, что все пройдет хорошо. Мы призываем всех других участников из нашей страны тоже стать авторами раундов — уверен, вы сможете подготовить множество отличных задач. Сделать раунд Codeforces — реальность ;)

Хочется выразить благодарность всем тем, кто помог нам с подготовкой раунда: Максиму Ахмедову (Zlobober), который помог нам с подготовкой задач, Нурлану Канапину (kt-9) и Мансуру Кутыбаеву (mexmans), протестировавшим контест, и Марии Беловой (Delinur), которая перевела условия на английский язык.

Отдельное огромное спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание платформ Codeforces и Polygon. Мы бы хотели поздравить Codeforces с недавно прошедшим пятилетием. Нам, авторам раунда, невероятно повезло начать заниматься олимпиадами по программированию, когда сайт Codeforces уже существовал, и он внес невероятный вклад в наше развитие!

Нам очень нравится, когда авторы задач пишут в анонсе немного о себе (призываем всех авторов поступать также) — это дает лучше почувствовать, что за задачами стоят реальные люди. Поэтому напишем немного о нас. Мы являемся студентами Назарбаев Университета (nu.edu.kz) — нового университета с английским языком обучения в столице Казахстана, Астане. В ACM-ICPC наш университет участвует лишь с 2012 года, но тем не менее команда с NU уже два раза проходила в финал в 2014 и 2015 году. Мы надеемся и в будущем держать планку спортивного программирования на высоком уровне.

Всем удачи!

UPD Разбалловка будет стандартной (500 — 1000 — 1500 — 2000 — 2500)

UPD2 Разбор можно найти тут

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

1. AkashiSeijuro

2. fmzbtf937

3. mxh3777

4. IGandWFin2019

5. ruozha2 & i_hate_t0nzuk

Раунд закончен, спасибо всем, кто принял участие!

Новая структура данных для решения задач, связанных с подпалиндромами в строках:
http://adilet.org/blog/25-09-14/

Спасибо пользователю droptable, который поделился этой информацией!

Немного впечатлений со стороны участника:
http://adilet.org/blog/30-06-14/
http://adilet.org/blog/02-07-14/

Спасибо всем организаторам и волонтерам, благодаря которым этот финал состоялся!

Всем привет!

В процессе подготовки к финалу ACM-ICPC 2014, наша команда NU 1 собрала (и продолжает собирать) коллекцию полезных алгоритмов под названием Algos. Сегодня мы решили поделиться ей с сообществом Codeforces.

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

Работа над библиотекой ведется в репозитории на гитхабе. Мы будем рады, если вы захотите внести свой вклад!

Все предложения, замечания и указания на ошибки приветствуются в комментариях :)

'Algos' algorithm collection.

Github repository.

Какие еще алгоритмы вы бы хотели увидеть в списке?