Hello, Codeforces!

A year ago we talked about our educational project EPIC Institute of Technology. Details can be found here.

Now we are pleased to announce that we are starting the admission campaign for the 2023-2024 academic year!

EPIC Institute of Technology is more than just an educational institution; it's a hub of innovative ideas and brilliant minds coming together! Here we make a difference and create a point of rapid growth for talented and driven individuals, leveraging the truly global leadership position of EPAM. EPIC Institute of Technology is committed to establishing and maintaining the highest standards by bringing together bright professionals to share Deltix unique expertise with the best students. We hold firm to our belief that this approach will raise a new generation of highly skilled young professionals with a broad vision and highly competitive skills.

EPIC Institute of Technology is online and entirely free institute. We offer four programs: Complex Logic, Real-Time Backend, Time-Series Analysis и Real-Time Frontend. The training will last one year and consist of two semesters. Groups for each program will be formed based on the results of the entrance exams. To study at our institute, you must be registered on our website for one of the specialties.

EPIC Institute of Technology is a place where you can meet familiar faces such as gepardo, who is taking Advanced Programming Languages and Operating Systems, Glebodin, who is enrolled in Networks & Clouds and Systems Architecture, peltorator, who is pursuing Algorithms & Data Structures, and vilcheuski, who happens to be the coordinator of this institute.

We conduct entrance exams in a group on Codeforces, you can join the group at the following link. The first entrance exam is June 30!

Also in the Codeforces group you can find the entrance exams of the last year, solve them and evaluate your strengths.

Successful graduates, and even current students, will have access to the power and resources of EPAM and an incredible chance to jumpstart their career by just using their talent and skill. We will offer our students a unique and straightforward path to the most challenging and exciting projects on a global scale, and an opportunity to learn from and work with industry-leading professionals.

Please visit our website to learn more about EPIC Institute of Technology and our programs. Also, basic information about the institute will be published in our Telegram channel.

UPD: The third entrance exam will be held on August 11th at 16:00 CET! Detailed information can be found at this link.

If you have any questions, you can quickly ask them in our chat.

Hello, Codeforces!

We are excited to announce the grand opening of EPIC Institute of Technology! EPIC Institute of Technology, a part of EPIC — EPAM Product Innovation Center, is truly a unique educational organization driven by the Deltix team under the EPAM Systems umbrella.

EPIC Institute of Technology is online and entirely free institute. We offer three programs: Complex Logic, Real-Time Backend, and Time-Series Analysis. The training will last one year and consist of two semesters. Groups for each program will be formed based on the results of the entrance exam, which will be held in the end of May/beginning of June 2022. The exact dates will be provided in the near future.

Successful graduates, and even current students, will have access to the power and resources of EPAM and an incredible chance to jumpstart their career by just using their talent and skill. We will offer our students a unique and straightforward path to the most challenging and exciting projects on a global scale, and an opportunity to learn from and work with industry-leading professionals.

Most recently, we told you that we can offer paid part-time jobs for those who are interested. To our and your happiness, the offer is still valid! Fill out the following form for teaching and we will contact you.

Please visit our website to learn more about EPIC Institute of Technology and our programs. Also, basic information about the institute will be published in our Telegram channel.

UPD: We are pleased to announce that the first entrance exam will be held at Codeforces on June 11th. The detailed information about the competition and access to it will be shared a few days before the exam.

We remind you to register on our website to take the exam. There you can also find some tasks to practice.

UPD: You can now join our group on Codeforces to stay in tune with all our activities, contests, and exams.

We would like to ask you to fill out your personal information in your Codeforces profile for quick identification. Register in the group. Confirmation of your registration is not automatic and may take some time. Please be aware, that all entrance exams will also be held in this group and you must be registered to take part.

In Contests tab, you can find a trial competition for you to get familiar with the testing system and the types of problems that may be a part of the entrance exam. Please register for the contest to be able to submit your solutions.

If you have any questions, you can quickly ask them in our chat.

We are excited to announce a new educational resource that is coming soon under the Deltix umbrella. Here is a list of paid part-time positions for teachers who want to join our rock star team:

• Math & statistics
• Algorithms & data structures
• Data science
• Advanced programming languages
• Systems architecture
• Networks and clouds
• Practical time-series analysis
• Machine learning
• Security
• Real-time backend (architecture)
• Operating systems
• Product strategy, vision, marketing and innovation

Each discipline will include lectures and practical exercises. Some of them will also offer mentorship for the final project.

Our resource will not be publicly available.

Excited about the opportunity? Complete the form at https://forms.gle/spXr3DaSYmRYePER9 and we will get back to you with further information.

Fill free to drop us a line at [email protected] if you have any questions.

Prepared by Vladik.
Solution: 137274527

Prepared by AleXman111.
Solution: 137274647

Prepared by AleXman111.
Solution: 137274769

Prepared by 4llower.
Solution with $$$O(n \cdot log(n))$$$: 137274837

Prepared by AleXman111.
Solution: 137274954

1609G - Прогулка по матрице

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

Это позволяет решать задачу за $$$O(n + m)$$$ простым обходом, но для полного решения этого не достаточно. Давайте введем два новых массива разницы соседних элементов массивов $$$da_i = a_{i + 1} - a_i$$$ и $$$db_i = b_{i + 1} - b_i$$$.

Обратим внимание, что наше жадное решение поворачивает направо из клетки $$$(i, j)$$$, когда $$$da_i > db_j$$$. Для наглядности ниже приведена иллюстрация поворотов:

Каждый раз такой поворот направо в клетке $$$(i, j)$$$ уменьшает нашу общую сумму на $$$(da_i - db_j) + (da_{i + 1} - db_j) + \dots + (da_{n - 1} - db_j) = (\sum_{t=i}^{n - 1} da_t) - db_j \cdot (n - i)$$$. Что на самом деле эквивалентно сумме $$$da_i - db_j$$$ для всех $$$da_i > db_j$$$.

Такую сумму можно считать узнавая для каждого $$$i$$$ бинарным поиском последнее $$$db_j$$$ для которого выражение $$$da_i > db_j$$$ верно. Что позволяет нам решать задачу за $$$O(n \cdot log(m))$$$ используя префиксные суммы массива $$$db$$$.

Теперь вернемся к запросам изменения. Т.к. размер массива $$$da$$$ достаточно маленький, то мы можем производить изменение значений его элементов простым обходом. Для хранения массива $$$db$$$ необходимо будет использовать дерево отрезков поддежривающее следующие операции:
- Прибавление числа на суффиксе массива (т.к. мы работаем с массивом $$$db$$$, а не $$$b$$$, то все элементы будут изменяться на одно число равное шагу арифметической прогрессии).
- Сумма чисел массива на префиксе массива пока $$$element_i < X$$$. (в качестве $$$X$$$ будет выступать очередной $$$da_i$$$).

Итоговая сложность: $$$O(q \cdot n \cdot log(m))$$$.

Prepared by budalnik.

Привет, Codeforces!

Вас приветствует компания DELTIX. Мы были основаны в 2005 году и являемся одним из лидеров в разработке программного обеспечения для исследований в финансовом домене и продуктов, решающих различные задачи системной и алгоритмической торговли. В 2020 году DELTIX присоединился к EPAM. Основной нашей задачей является быстрая и эффективная реализация перспективных идей в прорывные продукты.

Мы являемся экспертами по следующим направлениям:

• сбор, хранение, обработка данных
• моделирование данных
• тестирование и внедрение математических моделей

Поэтому в нашей команде ценятся такие навыки, как

• работа с алгоритмами
• написание высокоэффективного кода
• обработка потоков данных с минимальными задержками

Мы рады сообщить о выходе TimeBase Web Admin Community Edition.

Читайте больше о нас

Ближайший год, раз в сезон, мы будем рады приглашать вас участвовать в DELTIX раундах на Codeforces. Присоединяйтесь к третьему из серии наших раундов — объединенному раунду Div.1 и Div.2 Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2), который начнётся в 28.11.2021 17:35 (Московское время). Этот раунд будет рейтинговым и открытым для обоих дивизионов.

Призы, которые мы подготовили для вас:

1 место: Samsung Galaxy Z Flip3
2 место: Samsung Galaxy Tab S7+
3 место: Samsung Galaxy Watch4
1-100 место: фирменные футболки соревнования

А также 100 футболок достанутся случайным участникам (из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces), не вошедшим в топ-100, но попавшим в топ-1000.

Все задачи раунда, кроме последней, были подготовлены нашей командой: Vladik, 4llower и AleXman111.

Мы благодарим:

• KAN и budalnik за координацию раунда
• двойная благодарность budalnik за задачу, которая нашла уютное место в нашем наборе задач :)
• всех-всех тестировщиков раунда: Sugar_fan, 244mhq, Geothermal, andrew, aSmallTyphoon, _Time_Lord_, Hec, GustavoMG, phattd, ptd, kartel, mtw, avoronoi, fixikmila, kartikeyasri23, Whiplash99, Ghazoo, Jon, asitnikoff, Zayadi, Ahmad7_7, Omar_Elaraby, Kart, Java и anegelytor.
• а также MikeMirzayanov за системы Codeforces и Polygon

Участникам будет предложено 8 задач и 2.5 часа на их решение. Желаем всем успешного раунда и повышения в рейтинге!

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

UPD: Разбалловка для задач: 500 — 1000 — 1500 — 2000 — 2750 — 3000 — 3250 — 3750.

Спасибо всем за то что приняли участие. Желаем приятного дорешивания! (разбор)

Также хотим поздравить всех победителей раунда:
1. tourist
2. gop2024
3. xtqqwq
4. Maksim1744
5. VivaciousAubergine
6. maroonrk
7. jiangly
8. Rewinding
9. QAQAutoMaton
10. PubabaOnO

Prepared by AleXman111.

Prepared by AleXman111.

Prepared by Vladik.

Prepared by Vladik.

Prepared by netman.

Prepared by netman.

Prepared by netman.

Prepared by 300iq.

P.S. Editorial for problems E and G will appear a little later.

Привет, Codeforces!

Вас приветствует компания DELTIX. Мы были основаны в 2005 году и являемся одним из лидеров в разработке программного обеспечения для исследований в финансовом домене и продуктов, решающих различные задачи системной и алгоритмической торговли. В 2020 году DELTIX присоединился к EPAM. Основной нашей задачей является быстрая и эффективная реализация перспективных идей в прорывные продукты.

Мы являемся экспертами по следующим направлениям:

• сбор, хранение, обработка данных
• моделирование данных
• тестирование и внедрение математических моделей

Поэтому в нашей команде ценятся такие навыки, как

• работа с алгоритмами
• написание высокоэффективного кода
• обработка потоков данных с минимальными задержками

Мы рады сообщить, что с июля 2021 года один из наших продуктов TimeBase Community Edition является частью open source сообщества FINOS.

TimeBase — это многофункциональная система потоковой передачи данных с открытым исходным кодом, сочетающая в себе базу данных по работе с временными рядами, брокера сообщений и фреймворк по моделированию данных и сериализации. Первоначально TimeBase был разработан для работы в финансовой сфере. Тем не менее, мы не останавливаемся на достигнутом и беремся за новые амбициозные задачи в других областях, таких как IoT, облачные вычисления, кластеризация, высокопроизводительные вычисления, параллельная обработка данных и big data.

Читайте больше о нас

Ближайший год, раз в сезон, мы будем рады приглашать вас участвовать в DELTIX раундах на Codeforces. Присоединяйтесь ко второму из серии наших раундов — объединенному раунду Div.1 и Div.2 Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2), который начнётся в 29.08.2021 17:35 (Московское время). Этот раунд будет рейтинговым и открытым для обоих дивизионов.

Призы, которые мы подготовили для вас:

1 место: MacBook Air
2 место: iPad Pro
3 место: iPad Air
1-100 место: фирменные футболки соревнования

А также 100 футболок достанутся случайным участникам (из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces), не вошедшим в топ-100, но попавшим в топ-1000.

Все задачи раунда, кроме последней, были подготовлены нашей командой: Vladik, netman и AleXman111.

Мы благодарим:

• KAN и budalnik за координацию раунда
• 300iq за задачу, которая нашла уютное место в нашем наборе задач :)
• всех-всех тестировщиков раунда: antontrygubO_o, 244mhq, andrew, Mediocrity, Vaseline_Warrior, g1phy, nweeks, ptd, phattd, dmitriyklebanov, Alladdin, wxhtzdy, Shinchan01, Fasys и sovspace.
• а также MikeMirzayanov за системы Codeforces и Polygon

Участникам будет предложено 8 задач и 2 часа 30 минут на их решение. Желаем всем успешного раунда и повышения в рейтинге!

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

UPD: После обработки всех отзывов тестировщиков мы решили продлить соревнование на 15 минут. Итоговая длительность — 2 часа 30 минут.

UPD2: Разбалловка для задач: 500 — 1000 — 1500 — 1500 — 2000 — 2500 — 3000 — 3500. Обратите внимание на равную сложность задачи C и D.

Спасибо всем за то что приняли участие. Желаем приятного дорешивания! (разбор)

Также хотим поздравить всех победителей раунда:
1. Rewinding
2. jiangly
3. Benq
4. Egor
5. TLE
6. ainta
7. Radewoosh
8. Golovanov399
9. ecnerwala
10. maroonrk

Подготовил: Vladik.

Подготовил: AleXman111.

Подготовил: netman.

Подготовил: Vladik.

Подготовил: AleXman111.

Подготовил: netman.

Подготовил: Vladik.

Подготовил: 74TrAkToR.

Привет, Codeforces!

Вас приветствует компания DELTIX. Мы были основаны в 2005 году и являемся одним из лидеров в разработке программного обеспечения для исследований в финансовом домене и продуктов, решающих различные задачи системной и алгоритмической торговли. В 2020 году DELTIX присоединился к EPAM. Основной нашей задачей является быстрая и эффективная реализация перспективных идей в прорывные продукты.

Мы являемся экспертами по следующим направлениям:

• сбор, хранение, обработка данных
• моделирование данных
• тестирование и внедрение математических моделей

Поэтому в нашей команде ценятся такие навыки, как

• работа с алгоритмами
• написание высокоэффективного кода
• обработка потоков данных с минимальными задержками

Читайте больше о нас

Ближайший год, раз в сезон, мы будем рады приглашать вас участвовать в DELTIX раундах на Codeforces. Присоединяйтесь к первому из серии наших раундов — объединенному раунду Div.1 и Div.2 Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2), который начнётся в 30.05.2021 17:35 (Московское время). Этот раунд будет рейтинговым и открытым для обоих дивизионов.

Призы, которые мы подготовили для вас:

1 место: Самая желанная консоль 2021 года PlayStation 5!
2 место: Nintendo Switch
3 место: Nintendo Switch Lite
1-100 место: фирменные футболки соревнования

А также 100 футболок достанутся случайным 100 участникам (из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces!), не вошедшим в топ-100, но решившим хотя бы одну задачу.

Задачи раундов были подготовлены нашими сотрудниками: Vladik, netman, AleXman111 и sdryapko.

Мы благодарим:

• KAN и budalnik за координацию раунда
• 74TrAkToR за идею для одной из задач, а также её подготовку
• всех-всех тестировщиков раунда: 244mhq, Tlatoani, gepardo, andrew, generic_placeholder_name, ajit, ptd, PurpleCrayon, 4llower, namanbansal013, coderz189, wxhtzdy, vineet16, kalki411 и viktoria.0907
• а также MikeMirzayanov за системы Codeforces и Polygon

Участникам будет предложено 8 задач и 2 часа 15 минут на их решение. Желаем всем успешного раунда и повышения в рейтинге!

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

UPD: Разбалловка для задач: 500 — 1000 — 1500 — 2250 — 2250 — 3000 — 3250 — 3250.

Спасибо всем за то что приняли участие. Желаем приятного дорешивания! (разбор)

Также хотим поздравить всех победителей раунда:
1. tourist
2. Radewoosh
3. Um_nik
4. maroonrk
5. ecnerwala
6. jiangly
7. SSRS_
8. Petr
9. scott_wu
10. Maksim1744

Особые поздравления хотим выразить первой тройке лидеров! Мы постараемся как можно скорей передать вам ваши заслуженные призы :) К сожалению, мы сейчас не можем отметить людей, получивших 100 случайных футболок, по причине того, что поиск читеров не завершен.