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.

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 epic@epam.com 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 - A Stroll Around the Matrix

Let's try to solve the problem without asking for changes. Note that in the matrix constructed in this way for the move from (i, j) it is always profitable to go to the cell with the smallest number. This can be seen more clearly in the matrix of the first test case:

This allows you to solve the problem with complexity $$$O(n + m)$$$, but this is not enough for a complete solution. Let's introduce two new arrays of the difference between the adjacent elements of the arrays $$$da_i = a_{i + 1} - a_i$$$ and $$$db_i = b_{i + 1} - b_i$$$.

Note that our greedy decision turns right out of the cell $$$(i, j)$$$, when $$$da_i > db_j$$$. For clarity, below is an illustration of the turns:

Each time such a turn to the right in the cell $$$(i, j)$$$ decreases our total sum by $$$(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)$$$. Which is actually equivalent to the sum of $$$da_i - db_j$$$ for all $$$da_i > db_j$$$.

Such a sum can be considered by recognizing for each $$$i$$$ by a binary search the last $$$db_j$$$ for which the expression $$$da_i> db_j$$$ is true. This allows us to solve the problem in $$$O(n \cdot log(m))$$$ using the prefix sums of the $$$db$$$ array.

Now let's get back to change requests. Because the size of the $$$da$$$ array is small enough, then we can change the values of its elements by a simple. To store the $$$db$$$ array, you will need to use a segment tree supporting the following operations:
- Adding a number at the suffix (since we are working with an array $$$db$$$, not $$$b$$$, then all elements will change by one number equal to the step of the arithmetic progression).
- Sum of array numbers on array prefix so far $$$element_i < X$$$. ($$$da_i$$$ will act as $$$X$$$).

Prepared by Vladik.
Total complexity: $$$O(q \cdot n \cdot log(m))$$$.

Prepared by budalnik.

Hi, Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

• aggregation, storage, and processing large volumes of time-series data
• data modeling
• testing and deployment of quantitative models

In our team we value such skills as:

• knowledge of algorithms
• high-performance coding
• low latency data streams processing

We are excited to announce that we have released TimeBase Web Admin Community Edition.

More about DELTIX

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the third installment of our rounds (joined Div1 и Div2) Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on Nov/28/2021 17:35 (Moscow time). It is an open and rated round for both divisions.

We have prepared the following trophies for you:

1st place: Samsung Galaxy Z Flip3
2nd place: Samsung Galaxy Tab S7+
3rd place: Samsung Galaxy Watch4
1-100 places: branded t-shirts

Another 100 t-shirts will be distributed randomly between participants outside the top-100 but within the top-1000 and who participated in rated Codeforces rounds before.

Problems, except the last one, have been prepared by members of our team: Vladik, 4llower and AleXman111.

We would like to say a word of appreciation to:

• KAN and budalnik for the round management
• extra thanks to budalnik for creating one of the problems
• all the testers: 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 and anegelytor.
• and also MikeMirzayanov for Codeforces and Polygon systems

We will offer participants 8 problems and 150 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in employment opportunities or would like to speak with recruiters or members of our team.

UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2750 — 3000 — 3250 — 3750.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. tourist
2. gop2024
3. xtqqwq
4. Maksim1744
5. VivaciousAubergine
6. maroonrk
7. jiangly
8. Rewinding
9. QAQAutoMaton
10. PubabaOnO

We were especially delighted with the result tourist, who was able to solve all 8 problems, congratulations!

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.

Hi Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

• aggregation, storage, and processing large volumes of time-series data
• data modeling
• testing and deployment of quantitative models

In our team we value such skills as:

• knowledge of algorithms
• high-performance coding
• low latency data streams processing

We are excited to announce that one of our products TimeBase Community Edition joined a FinTech Open-Source Foundation (FINOS) on the 14th of July.

TimeBase is a multi-faceted, open-source data-streaming powerhouse, combining a time-series database, message broker, data modeling, and a well-optimized serialization framework. Originally, TimeBase was designed to address use cases in the financial domain. Nevertheless, we take on new challenges in other areas such as IoT, cloud computing, clustering, high-performance computing, parallel data processing, and Big Data to name a few.

Learn more about DELTIX

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the second installment of our rounds (joined Div. 1 and Div. 2) — Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on Aug/29/2021 17:35 (Moscow time).

It is an open and rated round for both divisions.

We have prepared the following trophies for you:

• 1st place = MacBook Air
• 2nd place = iPad Pro
• 3rd place = iPad Air
• 1-100 = branded t-shirts

Another 100 t-shirts will be distributed randomly between participants outside the top-100 but within the top-1000 and who participated in rated Codeforces rounds before.

All problems, except the last one, have been prepared by members of our team: Vladik, netman and AleXman111.

We would like to say a word of appreciation to:

• KAN and budalnik for the round management.
• 300iq for creating a great problem that has naturally fitted in our set of problems for this round.
• to all testers: antontrygubO_o, 244mhq, andrew, Mediocrity, Vaseline_Warrior, g1phy, nweeks, ptd, phattd, dmitriyklebanov, Alladdin, wxhtzdy, Shinchan01, Fasys and sovspace.
• MikeMirzayanov for Codeforces and Polygon systems.

We will offer participants 8 problems and 150 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in employment opportunities or would like to speak with recruiters or members of our team.

UPD: After processing all testers' feedback, we decided to extend the competition by 15 minutes. The total duration is 150 minutes.

UPD2: The scoring distribution is 500 — 1000 — 1500 — 1500 — 2000 — 2500 — 3000 — 3500. Note the equal complexity of C and D.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. Rewinding
2. jiangly
3. Benq
4. Egor
5. TLE
6. ainta
7. Radewoosh
8. Golovanov399
9. ecnerwala
10. maroonrk

Prepared by Vladik.

Prepared by AleXman111.

Prepared by netman.

Prepared by Vladik.

Prepared by AleXman111.

Prepared by netman.

Prepared by Vladik.

Prepared by 74TrAkToR.

Hi Codeforces!

We are DELTIX. Founded in 2005, DELTIX is one of the market leaders in software development for financial research and products for systematic and algorithmic trading. In 2020 DELTIX joined the EPAM family. Our mission is to turn promising ideas into breakthrough products fast.

We are experts in:

• aggregation, storage, and processing large volumes of time-series data
• data modeling
• testing and deployment of quantitative models

In our team we value skills like:

• knowledge of algorithms
• high-performance coding
• low latency data streams processing

Learn more about DELTIX

Throughout the year, once per quarter, we will be inviting you to join DELTIX rounds at Codeforces. Today, we are excited to welcome you to the first installment of our rounds (joined Div1 и Div2) — Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2), that will start on May/30/2021 17:35 (Moscow time).

It is an open and rated round for both divisions.

We have prepared the following trophies for you:

• 1st place = the most desired console of 2021 — PlayStation 5!
• 2nd place = Nintendo Switch
• 3rd place = Nintendo Switch Lite
• 1-100: branded t-shirts

Another 100 t-shirts will be distributed randomly between 100 participants outside of top-100 and who have solved at least one problem and participated in rated Codeforces rounds before.

Problems have been prepared by our employees: Vladik, netman, AleXman111 and sdryapko.

We would like to say a word of appreciation:

• to KAN and budalnik for coordinating the round
• 74TrAkToR for the idea for one of the tasks, as well as its preparation
• to all testers: 244mhq, Tlatoani, gepardo, andrew, generic_placeholder_name, ajit, ptd, PurpleCrayon, 4llower, namanbansal013, coderz189, wxhtzdy, vineet16, kalki411 and viktoria.0907
• and of course, to MikeMirzayanov for Codeforces and Polygon

We will offer participants 8 problems and 135 minutes to solve them. We wish everybody good luck and high ratings!

Fill out a short contact form if you are interested in internship and/or employment opportunities or would like to speak with recruiters or members of our team.

UPD: The scoring distribution is 500 — 1000 — 1500 — 2250 — 2250 — 3000 — 3250 — 3250.

Thank you all for participating! (editorial)

Congratulations to the winners:
1. tourist
2. Radewoosh
3. Um_nik
4. maroonrk
5. ecnerwala
6. jiangly
7. SSRS_
8. Petr
9. scott_wu
10. Maksim1744

We would like to express our special congratulations to the top three leaders! We will try to send you your well-deserved prizes as soon as possible :) Unfortunately, we can not list the people who received 100 random T-shirts due to the fact that the search for cheaters is not completed.