Кодер Арсений

Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных). Сегодня я принял виртуальное участие в Educational Codeforces Round 138 (Rated for Div. 2). Это я могу назвать достаточно неудачным соревнованием. Первая задача Условие Решалась она просто: если n = m, то выводим "NO", иначе выводим "YES"...

Всем привет, у клавиатуры Кодер Арсений. Не так давно я узнал о прекрасной альтернативе префиксному массиву - дерево отрезков. Сегодня именно о нём и пойдёт речь. Теория Картинки взяты со статьи на Хабре. Как и сам массив. Приведу простую задачу, с помощью которой чаще всего объясняется дерево отрезков. У нас есть массив чисел, затем вводится огромное количество запросов l, r. Задача в ответ на каждый запрос вывести сумму чисел на подотрезке [l:r]...

Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, мне попалась задача, которую я решил одним способом. После этого в разборе задач я увидел как раз технику "Contribution to the Sum" (перевод - "Вклад в сумму"), о которой я и хотел бы рассказать в данной статье. Перед прочтением желательно иметь хотя бы базовое представление о теории вероятностей. Теория Математическое ожидание Мат. ожидание E(x)- среднее значение случайной величины. Считается как сумма произведений возможных значений на вероятность этих значений. Приведу пример: у нас есть монеты 10 копеек, 50 копеек, 1 рубль, 2 рубля, 5 рублей и 10 рублей...

Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных). Сегодня я принял виртуальное участие в Educational Codeforces Round 137 (Rated for Div. 2). Первая задача Условие Если посмотреть на ограничения, то можно сделать вывод, что задачу можно решить перебором. Можно и комбинаторикой, но зачем? Я долго тупил, поэтому 9 минута, Python...

Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных). Сегодня я принял виртуальное участие в Codeforces Round #776 (Div. 3). Соревнование было достаточно простым и состояло из задач, которые я могу назвать классическими. Первая задача Условие Решение слишком простое: символ должен стоять на нечётной позиции чтобы мы вывели YES, иначе выводим NO...

Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, мне попалась задача, в ходе решения которой я узнал о DSU. Эта вещь очень сильно помогает при решении задач, поэтому я решил изучить её поподробнее. Теория DSU - это структура данных, которая позволяет администрировать множество элементов, разбитое на непересекающиеся подмножества. При этом каждому подмножеству назначается его представитель — элемент этого подмножества. У этой структуры данных есть 3 функции: Чтобы реализовать подобную структуру наиболее эффективно, нам нужны деревья...

Всем привет, у клавиатуры Кодер Арсений. Проходя одно из соревнований, у меня возникли трудности при работе с побитовой операцией XOR. Я сделал вывод, что мне нужно освежить свои знания по теме побитовых операций, т. к. эта тема часто встречается в задачах и нуждается в глубоком понимании. Чтобы понять эту тему, я зашёл на LeetCode, где зашёл в список задач и вбил XOR. Задача решить 3 задачи Easy и 1 Medium. Теория Побитовые операции - это операции над числами в двоичной системе счисления, где мы поочередно работаем с каждым битом...

Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных). Сегодня я принял виртуальное участие в Codeforces Round #812 (Div. 2) Первая задача Условие Решение этой задачи быстро пришло мне в голову, здесь стоит использовать просто жадные алгоритмы. Если движение идёт только вдоль одной оси, то максимальная длина будет |Xmax| * 2...

Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных). Сегодня я принял виртуальное участие в Codeforces Round #832 (Div. 2). Первая задача Первая задача была на первый взгляд неприятная: был дан массив чисел arr, который надо было разбить на два подмассива arr_1 и arr_2 так, чтобы |sum(arr_1)| - |sum(arr_2)| было максимально возможным...