Привет!

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

Ссылка на видео

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Если вы еще не видели, можете также посмотреть мое видео про disjoint sparse table тут.

Codeforces группа с контестом

Реализации можно посмотреть по ссылкам:

Поиск одномерных префиксных сумм

Префиксные суммы на структурах для поиска суммы на отрезке

Поиск двумерных префиксных сумм двумя методами: раз, два

Поиск одномерного разностного массива

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

The future is bulletproof
The aftermath is secondary
It's time to do it now and do it loud!

Привет, Codeforces!

Мы с 74TrAkToR рады пригласить вас на наш совместный Codeforces Round 705 (Div. 2), который пройдет в 06.03.2021 17:05 (Московское время). Обратите внимание на необычное время проведения раунда. Он будет рейтинговым для всех участников, чей рейтинг ниже 2100.

Мы уже проводили раунд и провели работу над ошибками:

• условия будут короткие и понятные
• мы постарались сделать претесты еще сильнее
• разбор будет опубликован сразу же после раунда

Мы хотим поблагодарить всех, кто оказал нам бесценную помощь в подготовке этого раунда:

• Нашего координатора KAN за великолепную координацию раунда.
• Наших тестеров Tlatoani, sava-cska, DIvanCode, BLIZZARD, Mlxa, plagues, voventa, hg333, malachi_toney_goat, kassutta за отличное тестирование и полезные замечания.
• MikeMirzayanov за прекрасные системы Codeforces и Polygon.

Вам будет предложено 6 задач. У вас будет 2 часа 15 минут на их решение.

UPD: Разбалловка $$$750-1250-1750-2250-2750-3250$$$.

UPD2: Разбор

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

Div. 2:

1. sawa855

2. A05

3. DeIeted

4. rainboy

5. scli_scj

Div. 1 + Div. 2:

1. neal

2. BigBag

3. fastmath

4. Sugar_fan

5. tute7627

Желаем всем удачи!

Привет, Codeforces!

В 02.03.2021 17:45 (Московское время) состоится Educational Codeforces Round 105 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

И снова отличные новости, Codeforces!

Мы особенно рады возможности чаще делиться своими стипендиями!

На этот раз, мы и OneRagtime снова открываем двери в увлекательный мир информационных технологий.

В партнерстве с OneRagtime мы предлагаем полную стипендию на магистратуру компьютерных наук в Harbour.Space, во время которого вы будете проходить стажировку на позиции full stack разработчика в OneRagtime!

О стипендии:

➡ Работа в одном из самых интересных технологических городов Европы
➡ Размер стипендии до 31 500 евро.
➡ Компенсация за стажировку в OneRagtime (800 евро в месяц)
➡ Возможность работать в OneRagtime на полную ставку по окончанию обучения

Преимущества работы в OneRagtime:

• Международная команда
• Постоянное развитие навыком
• Умопомрачительная атмосфера
• Погружение в европейскую технологическую экосистему
• Применение новых технологий в венчурном инвестировании
• Работа в самых интересных технологических городах Европы

Ранее мы сотрудничали с другими компаниями, такими как OneRagtime, Hansgrohe, Cohera и Remy Robotics, чтобы воплотить мечту молодых талантов по всему миру и помочь им построить свою карьеру. Мы уже заполнили несколько позиций в сотрудничестве с OneRagtime, в том числе:

• Разработчик Full Stack в OneRagtime награжден Алехандро Мартинес из Мексики
• Дизайнер UI / UX из OneRagtime награжден Давидом Петриашвили из Грузии

Мы всегда рады видеть членов сообщества Codeforces, которые присоединяются к семье Harbour.Space. Подайте заявку сейчас, чтобы получить шанс учиться у лучших в этой области и начать свою карьеру!

Следите за новостями в LinkedIn, чтобы не упустить новые возможности. А так же загляните в наш Instagram, где мы делимся событиями студенческой жизни и историями успеха наших учеников.

Удачи в вашем раунде и до встречи в следующий раз!

Harbour.Space University

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

Поздравляем лучших взломщиков:

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

UPD: Разбор опубликован

Hello Codeforces!

On Feb/28/2021 16:35 (Moscow time) we will host Codeforces Global Round 13.

It is the first round of a 2021 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2021:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2021 supported the global rounds initiative!

The problems were written and prepared by 3.141592653, Widowmaker, Ynoi, errorgorn, oolimry, star_xingchen_c, syksykCCC.

We would also like to thank:

• Great antontrygubO_o for rejecting problems greatest coordination!
• tfg, dvdg6566, cjy2003, Tlatoani, purinliang, user14767553, bensonlzl, wlzhouzhuan, maomao90, huangqr, mollnn, malachi_toney_goat, b23v, qlf9, gamegame, Myrcella, 244mhq, Dormi, flaviu2001, karavaiev, wh0816, kdjonty31, socho, Karry5307, dXqwq, KagamineRin, hzkmd, syh0313, Nanako, sunsiyu, zkdxl, Pecco, ODT for testing the round and sticking on difficult problems providing valuable feedback to the problems.
• froggyzhang, paulzrm, mejiamejia for giving great rejected problems and many interesting ideas.
• MikeMirzayanov for great Codeforces and Polygon platforms!
• And You, for participating! Your participation in this round will allow our emperor Anton to reject more problems.

You will have 3 hours to solve 9 problems. We encourage you to read all the problems and solve them all.

One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

UPD1: Scoring distribution: 500-750-1000-1250-1750-2000-2250-3000-5000

UPD2: Tutorial published.

UPD3: System testing finished, congrats to the winners!

1. maroonrk
2. DmitryGrigorev
3. Petr
4. jiangly
5. RALZH
6. qazswedx2
7. sunset
8. ecnerwala
9. lumibons
10. p_b_p_b

Всем привет!

В этот вторник пройдет московская олимпиада школьников по программированию для 6-9 классов. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680).

Раунд состоится 23.02.2021 12:05 (Московское время). Вам будет предложено 5 задач и 2 часа на их решение. Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут написать контест вне конкурса.

Задачи соревнования подготовлены grphil, Jatana, rip, Sehnsucht, DebNatkh, KiKoS, wrg0ababd, V--o_o--V, voidmax, meshanya, vintage_Vlad_Makeev под моим руководством.

За координацию раунда спасибо adedalic, за перевод условий cdkrot и meshanya, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.

Также спасибо Noam527 за предоставление дополнительной задачи, которая помогла составить (я надеюсь) сбалансированный проблемсет для раунда.

Всем удачи!

Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.

UPD1: Спасибо LHiC, awoo, ScarletS, adarsh7777, kassutta, raj_mehta_ за тестирование.

UPD2:

Разбалловка: 500 — 1000 — 1500 — 2250 — 3000

UPD3: Разбор

UPD4: Победители!

Div. 2:

1. InternetPerson10
2. egor95123657
3. hhhyyyfff
4. xXx_KevinDu58_xXx
5. Flying2021

Div. 1 + Div. 2:

1. Um_nik
2. qazswedx2
3. 3.141592653
4. BigBag
5. InternetPerson10

Registration for International Data Analysis Olympiad (IDAO 2021) is open now. It’s being organized by HSE University and Yandex for the 4th time. Otkritie bank will be our platinum partner this year. The Olympiad will be convened by leading experts in data analysis and aims to bring together analysts, scientists, professionals, and junior researchers. Participation is free. Winners and prize-winners of IDAO 2021 will receive valuable prizes.

This year the online task is coming again from Physics. The task was given by the Laboratory of Methods for Big Data Analysis (LAMBDA, HSE University) together with CYGNO Collaboration (Italy).

The registration is open till March 12, 2021. The Olympiad includes two stages:

Online Stage (March 1-31):

• Track 1: Traditional machine learning competition on Yandex.Contest platform. You will need to make new predictions and upload them to the automatic verification system.
• Track 2: Come up with a solution for the same problem, keeping within a rigid framework of time and memory used.

Final (April 17-18):

• top 30 teams according to the Online Stage results will be invited to the Online final.
• In the final 36 hours of the competition, participants will try not just to train the model, but to create a full-fledged prototype, which will be tested both in terms of accuracy and performance.

Learn more: https://idao.world/

Привет, Codeforces!

Наконец-то я могу что-то вернуть этому прекрасному сообществу, поэтому я рад пригласить вас принять участие в Codeforces Round #703 (Div. 2), который состоится в 18.02.2021 17:35 (Московское время). Раунд будет рейтинговым для участников с рейтингом менее 2100. Участники из первого дивизиона могут принять участие в раунде вне конкурса.

Вам будет предложено 6 задач и 2 часа 15 минут чтобы их решить. Все задачи раунда придуманы и подготовлены мной. Одна из задач будет интерактивной, пожалуйста ознакомьтесь с гайдом для интерактивных задач перед контестом.

Я также хочу поблагодарить:

• antontrygubO_o за отличную координацию!
• Monogon, 3EVEHAR_KOAVA, Akulyat, Aleks5d, BRCode, Osama_Alkhodairy, PO3OBAR_Bblnb, arzhantsev64, bWayne, Aditya_Mittal_31, kassutta, kclee2172, kalki411, sdl за тестирование раунда и полезные комментарии.
• Aleks5d за предложение альтернативного решения для одной из задач.
• MikeMirzayanov за платформы Codeforces и Polygon!

Разбалловка: $$$500-1000-(750+750)-1750-2250-3000$$$.

Не забудьте прочитать ВСЕ задачи. Желаю вам удачи и высокого рейтинга!

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

UPD: Разбор

UPD: Winners and First to solve

Div1 + Div2

Div2

Первое полное решение

Например, для tourist, можно найти на странице его профиля:

Привет, Codeforces!

<almost-copy-pasted-part>

Привет! Во 16.02.2021 17:35 (Московское время) начнётся Codeforces Round #702 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

• принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
• не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz, Stepavly и sodafago

Спасибо MikeMirzayanov за платформы и координацию нашей работы. Спасибо darkkcyan, Sho, sodafago, budalnik, kocko, akagami_no_shanks, bugdone, iankury, Gassa, infinitepro, bfs.07 за помощь в подготовке и тестировании раунда.

Удачи!

</almost-copy-pasted-part>

UPD: Разбор появился!

Привет, Codeforces!

В Feb/15/2021 17:35 (Moscow time) состоится Educational Codeforces Round 104 (Rated for Div. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Отличные новости, Codeforces!

Как мы и обещали в прошлый раз, мы вернулись с новой возможностью получить стипендию!

Мы стали партнерами Coherra, чтобы открыть двери для увлекательной карьеры в сфере технологий для самых талантливых людей.

В сотрудничестве с Coherra мы предлагаем полную стипендию для обучения в магистратуре "Front End Development" в Harbour.Space, во время которого вы будете проходить стажировку на позиции front end-разработчика в Coherra!

О стипендии:

➡ Работа в самых интересных технологических городах Европы

➡ Размер стипендии до 22900 евро для обучения в Harbour.Space University

➡ Компенсация за стажировку в Coherra

➡ Возможность работать в Coherra полный рабочий день после окончания учебы

Ранее мы сотрудничали с другими компаниями, такими как OneRagtime, Hansgrohe и Remy Robotics, чтобы расширить возможности молодых талантов по всему миру и помочь им построить карьеру в сфере технологий. Мы уже заполнили несколько вакансий с нашими партнерами, в том числе:

• Место full stack разработчика в OneRagtime занял Alejandro Martinez из Мексики
• Место innovation designer в Hansgrohe занял Giorgi Zhuzhiashvili из Грузии

Мы всегда рады видеть членов сообщества Codeforces, которые присоединяются к семье Harbour.Space. Подайте заявку сейчас, чтобы получить шанс учиться у лучших в этой области и начать свою карьеру!

Следите за новостями в LinkedIn, чтобы не упустить новые возможности. А так же загляните в наш Instagram, где мы делимся событиями студенческой жизни и историями успеха наших учеников.

Удачи в вашем раунде и до встречи в следующий раз!

Harbour.Space University

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

Было сделано 90 успешных и 1286 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

UPD: Разбор опубликован