I always was dreaming that one day competitive programming will become a real sport, not just activity for a small group of participants. Why? Because I don't really like working and my tries to do some science were totally unsuccessful. It would be cool to live just by doing what you like. Very childish, I know.

But this blog is not about if competitive programming is important or are there any ways to make it interesting to watch to wider audience. I am just trying to understand, is it currently moving toward real sport or away from it? And I get some mixed signals about that:

Bad signals:

• Big onsites (like GCJ or TCO) seem to cut the number of participants and the amount of prizes.

• Some onsite-finals are turning to online-finals. For example, several years ago we had Russian Code Cup onsite in Russia, currently RCC Finals is online.

• Some big companies are turning away from sport programming (IBM is stopping sponsorship of ACM ICPC).

Good signals:

• Some new finals were created during last years. For example, VK Cup in Russia, SnackDown in India or Code Festival in Japan (for students).

• Some small firms are holding rounds and even created their own little onsite finals.

• Sports programming (not in the financial part) seems to thrive. For instance, there are new platforms for training that were created just in the last year: like atcoder (for international participants) or csacademy.

So, what future will you predict for a competitive programming? Will it become a real sport? Or will it forever be just for fun and for students to get to the interview in a big company?

This article will be presenting a rather classical problem that can be solved using deques, along with an extension that allows you to solve the problem in its more general multi-dimensional case. I have decided to write this article after this discussion on 2D range-minimum query.

The article will be mainly based on this following problem:

You are given an array of numbers A[] of size n and a number k ≤ n. Find the minimum value for each continuous subarray of size k.

We will be now focusing on the linear-time solution to this problem.

Solution:

Consider sweeping from left to right through the array. At every moment we keep a list of "candidates" for minimum values throughout the process. That means that at each moment, you have to add one element to the list and (potentially) remove one element from the list.

The key observation is that, during the sweep line process, we find two values A[i] and A[j] which have i < j and A[i] ≥ A[j], then we can safely discard A[i]. That is because, intuitively, A[j] will continue to "live" in our sweep line more than A[i], and we will never prefer A[i] instead of A[j].

We should now consider pruning all the "useless" values ("useless" as in the statement above). It is easy to see now that doing this will lead to a strictly increasing list of candidates (why?). In this case, the minimum will always be the first element (O(1) query).

In order to insert an element to the back of the pruned candidate list, we will do a stack-like approach of removing all elements that are greater than it, and to erase on element, we just pop the front of the list (if it is not already removed).

This is a well-known approach for finding minima over fixed-size continuous subarrays. I will now present an extensions that allows you to do the same trick in matrices and even multi-dimensional arrays.

The multi-dimensional extension

Problem (2D):

You are given an matrix of numbers A[][] of size n × m and two numbers k ≤ n, l ≤ m. Find the minimum value for each continuous submatrix of size k × l.

Solution:

Consider the matrix as a list of rows. For each row vector of A, use the 1D algorithm to compute the minimum value over all l-length subarrays, and store them in ColMin[][] (obviously, ColMin[][] is now a n × (m - l + 1)-sized matrix).

Now, consider the new matrix as a list of columns. For each column vector of ColMin, use the algorithm to compute the minimum value over all k-length subarrays, and store them in Ans[][] (of size (n - k + 1) × (m - l + 1)).

The Ans[][] is the solution to our problem.

The following picture shows the intutition behind how it works for computing Ans[1][1] for n = 5, m = 7, k = 3, l = 4

The pseudocode is as follows:

def solve_2d(M, k, l):
  column_minima = {} # empty list
  for each row in M.rows:
    # We suppose we have the algorithm that solves
    # the 1D problem
    min_row = solve_1d(row, l)
    column_minima.append_row(min_row)
  
  ans = {}
  for each col in column_minima.cols:
    min_col = solve_1d(col, k)
    ans.append_col(min_col)
  
  return ans

Note that the pseudocode is (deliberately) hiding some extra complexity of extracting rows / columns and adapting the 1D algorithm to the 2D problem, in order to make the understanding of the solution clearer.

The total complexity of the algorithm can be easily deduced to be O(n * m)

Multi-dimensional case analysis

The solution can be extended to an arbitrary order of dimensions. For a d-dimensional matrix of size s₁, s₂, ..., s_d, the time-complexity of the problem is O(d * s₁ * ... * s_d), and the memory complexity is O(s₁ * ... * s_d). This is much better than other algorithms that do the same thing on non-fixed size submatrices (e.g. multi-dimensional RMQ has O(s₁ * ... * s_d * log(s₁) * ... * log(s_d)) time and memory complexity).

Finding the best k minima

The deque approach itself is limited in the sense that it allows you to find only the minimum value over the ranges. But what happens if you want to calculate more that one minimum? We will discuss an approach that I used during a national ACM-style contest where we were able to calculate the best 2 minima, and then argue that you can extend to an arbitrary number of minimum values.

In order to store the lowest 2 values, we will do the following:

Keep 2 deques, namely D1 and D2. Do a similar algorithm of "stack-like popping" on D1 when you add a new element, but instead of discarding elements from D1 when popping, transfer them down to D2 and "stack-like pop" it.

It is easy to see why the lowest 2 elements will always be in one of the two deques. Moreover, there are only 2 cases for the lowest two elements: they are either the first two elements of D1, or the first elements of D1 and D2 subsequently. Checking the case should be an easy thing to do.

The extension to an arbitrary number of minima is, however, not so great, in the sense that the complexity of this approach becomes O(n * k²) for a n-sized array, currently bottlenecked by the number of elements you have to consider in order to find the first k minima. [Maybe you can come up with a cleverer way of doing that?]

Useful links

This is the problem I referred to above: http://www.infoarena.ro/problema/smax. I recommend trying to think it through and implementing it, and translating the statement via Google Translate or equivalent.

Hi everybody!

On Saturday, August 12, 2017, at 14:35 UTC Codeforces Round #428 will be held. As usual, Div.1 participants can join out of competition.

The problems are prepared by me(Sadegh Mahdavi) and NikaraBika(Majid GarooC). Great thanks to Arpa(AmirReza PoorAkhavan) and Livace(Alexey Ilyukhov) for testing the round, KAN(Nikolay Kalinin) for helping us preparing the round and MikeMirzayanov(Mike Mirzayanov) for the Codeforces and Polygon systems.

There will be 5 problems and 2 hours to solve. The scoring will be published later.

The main characters of this round are chosen from the game of thrones series :D

UPD : The scoring is : 500 — 1000 — 1500 — 2000 — 2500

UPD: The judges solutions for problem B incorrectly handled some case, so we are going to rejudge some of the hacks. The pretests are not affected, so the contest is going to be rated.

UPD : The round is finished. Congratulations to winners:

Div 2:

1.mama_budra

2.fatego

3.regmsif

4.Lyra

5.Illyasviel

Div 1:

1.dotorya

2.kmjp

3.I_love_Tanya_Romanova

4.Benq

5.Claris

UPD Editorial

On Sunday, August 6th, 22:00 IST, we will hold the 2nd elimination for IndiaHacks (some more details here). The top 900 individuals who qualified through previous rounds will have the opportunity to participate in this round. The top 25 global participants and top 25 Indian participants will advance to the final round. The link to the contest is here.

After the official round is over, the next morning, on Monday, August 7th, 11:35 IST, we'll hold an unofficial unrated mirror here on Codeforces. This mirror will have ICPC rules. For participants of the official round, please hold off on discussing the problems publicly until after this mirror is over.

I was the author of the problems in this set, and I hope you will enjoy the problems. I would like to thank zemen for testing the set, Arpa for writing editorials, r3gz3n for his help on the HackerEarth side, KAN for helping us set up the mirror contest, and of course MikeMirzayanov for the great Polygon/Codeforces platform.

The round will consist of 6 problems and you will have 3 hours to complete them. Please note that the problems will be randomly arranged in both rounds, since I couldn't figure out how to sort them by difficulty. Be sure to read all the problems.

UPD1: Updated time of official round and posted link to contest.

UPD2: We should have updated the leaderboard to accept solutions that followed the first version of the first problem. We have also increased the number of finalists to 60 total (30 global + 30 indian) based on this new leaderboard.

UPD3: Here is the list of qualifiers. Congratulations to everyone.

Hello Codeforces!

On August 3, 18:05 MSK Educational Codeforces Round 26 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Alexey Perforator Ripinen, Mike MikeMirzayanov Mirzayanov and me.

Good luck to all participants!

Don’t miss your chance to be a part of this leader board in the next ACM-ICPC World Finals by reserving your spot in the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC.

Check out the winning statics of Universities that participated in this special training — World Finals 2017 Results.

8 out of 12 prize-winners of the World Finals 2017 participated in Moscow Workshops ACM-ICPC!

Take a look back on our previous "Hello Barcelona ACM-ICPC Bootcamp, in collaboration with Moscow Workshops ACM-ICPC". Students and coaches from all over the globe gathered at our campus to learn from and work with the world’s top programmers, soak in the Barcelona sun, and share in the comradery built within the programming community. Harbour.Space University is looking forward to hosting again, this time at the beautiful and technologically mind bending Media-TIC building.

UPD: Editorial is available

Congratulations to the winners:

Congratulations to the best hackers:

1361 successful hacks and 513 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Hi everybody,

Less than in 30 minutes there will start a second round of IOI 2017. Yesterday all the students visited the sixth talles tower in the world named Milad Tower.

We wish all the contestants the good luck!

Some useful links (more to be added):

• First round discussion.
• Official rankings.- Таблица реузльтатов от неутомимого snarknews с множеством разной дополнительной интересной информации.
• Rankings by snarknews with lots of extra interesting information.
• List of the contestants according to the great IOI database.
• IOI website
• Post by SeyedParsa about the Olympiad.
• Mirror contest hosted by Yandex.Contest.

Hi!

On Monday, July 31, 2017, at 14:35 UTC rated Codeforces Round #427 for participants from the second division will take place. As always, participants from the first division can take part out of competition.

The problems for this round were prepared by me. Many thanks to Alexey Ilyukhov (Livace) for help in preparations of the round and testing the problems, AmirReza PoorAkhavan (Arpa) for proofreading the statements and testing the problems, Gaev Alexandr (krock21) for testing the problems, Nikolay Kalinin (KAN) for the round coordination and, of course, Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon platforms.

The round will last for 2 hours, and you will be given 6 problems. I recommend you to read the statements of all problems. I hope everyone will find an interesting problem!

Scoring will be announced before the round.

Scoring: 500 — 750 — 1250 — 1500 — 2250 — 2250.

UPD.

Thanks for participating!

The editorial is here.

Congratulations to the winners!

Div2:

1. ywwyww

2. nick452

3. JustAnAverageCoder123

4. cxt

5. wa1tz7I9

Div1:

1. dotorya

2. rajat1603

3. anta

4. Kaban-5

5. HellKitsune

Hello, fellow programming contest enthusiasts!

We are pleased to invite you to take part in the forthcoming Codeforces Round #426, which is going to be held at Sunday, 17:35 MSK. In case one of the things you fear most is a Codeforces round being authored by a purple guy, we've got some badgood news for you: this round will feature two CMs – me (xen) and GreenGrape – as its writers!

The classic Codeforces rules will be applied to this round. There will be five problems for each division, with three of them shared by both. The round will last for two hours. Forgoing a long-standing Codeforces tradition, we will not have the scoring disclosed until shortly before the contest.

In this round, you are going to assist Slastyona the Sweetmaid – a renowned lover of sweets, cupcakes, candies and all other kinds of confectionery! In her everyday life, Slastyona often faces challenging problems, some of which cannot be solved without your help.

Kudos to our testers: Kirill Seemann Simonov, Evgeny rek Tushkanov, Yegor Voudy Spirin, Evgeny WHITE2302 Belykh, Vladislav winger Isenbaev and Alexander AlexFetisov Fetisov. We would also like to thank Arthur tunyash Riazanov for his ideas on some of the problems. Thanks to the Codeforces coordinator Nikolay KAN Kalinin for his assistance in making this round happen (and for his patience, too), and, of course, to the one and only Mike MikeMirzayanov Mirzayanov for creating the magnificent Codeforces and Polygon!

You may ask: “Is it rated?” Well, for what's it worth, it seems it is, since we've commited all our passion and efforts to prevent the contrary :)

In any case, we wish you luck/bugfree code/high rating/whatever and hope that solving our problems would be a great pastime for you on this lovely Sunday evening.

UPD. The scoring is:
Div. 1: 500 – 1250 – 1500 – 2250 – 2500
Div. 2: 500 – 1000 – 1500 – 2250 – 2500

UPD 2. Our congratulations to the winners!

Div. 1:

1. Radewoosh
2. LHiC
3. VivaciousAubergine
4. SanSiroWaltz
5. W4yneb0t

Div. 2:

1. nguyenthibanh
2. ColdSu
3. LLX
4. EnjoyCallen
5. pr3pony

UPD 3. Editorial

artwork by Ilya Shapovalov

Hi everybody!

I am writing this post from a sunny Tehran where the 29th International Olympiad in Informatics is being held. Me and Mikhail Endagorion Tikhomirov are here as a part of Russian Federation delegation on the Olympiad.

In about four hours the first round of the main competitive programming school student event of the year starts. Russian Federation is presented by one of the youngest team ever in the history of Russia on IOI consisting of:
Vladimir voidmax Romanov, Denis Denisson Shpakovskiy, Alexandra demon1999 Drozdova and Egor Egor.Lifar Lifar.

In Russian version of this post me together with Endagorion are going to make a text coverage of what is happening on the contest. We will mainly concentrate on Russian delegation there, so we are not going to duplicate all the live information in the English version of the post, but we invite all of you who are interested in IOI to discuss the problems and the results in the comments section below.

SPOILER ALERT: the text of this post and the comments may possibly contain lots of spoilers to the competition problems, so if you are going to participate in any online mirror, or you simply want to solve the problems buy yourself then be careful.

PS Some photos with comments in Russian are available at the Telegram channel here.

Some useful links (more to be added):

• Rankings by snarknews with lots of extra interesting information.
• List of the contestants according to the great IOI database.
• IOI website
• Post by SeyedParsa about the Olympiad.
• Mirror contest hosted by Yandex.Contest.

Hello, Codeforces!

The latest innovation in Codeforces is introduction Google calendar with information about the upcoming contests. To view calendar you can visit tab "Calendar" in the top menu.

The Codeforces contests are adding in calendar automatically. Also you can add contests from the other programming platforms. Each red user has this option. In addition, we will grant the rights to edit the calendar to employees/enthusiasts of other popular platforms.

In the tab "Add" you can add information about upcoming contest. The form shown below will help you for this.

Please, add to the calendar classic algorithmic contests which duration does not exceed a day. Also the contest must be publicly available, i. e. had English statements and open for a wide range of participants. We ask you to use short names for competitions, as it is presented in the examples, for convenience and uniformity.

Also you can edit or remove information about upcoming events in corresponding tabs.

We hope that the calendar will be useful for you and will help to planning your time and learn about all upcoming programming events.

In our plans to expand the functionality of the calendar. Write about your ideas for improving it in the comments.