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 MaGaroo(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.AngelMegumin

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.

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

First, you would jump the first task, which was an answer-only task and didn't fit you. Then you would have a wrong basic idea to the task, such as thinking that the answer would be to connect the points one by one when n = m.

Then you would spend some time coding a naive solution, which definitely would get wrong answer, and you would spend some time looking at your screen and not knowing what to do. Then you would start stress testing and found your hypothesis wrong.

Now, one and a half hours had passed and you would be worried. You would like to solve the task as soon as possible-----because it wasn't early now. However, you would have lost your wit due to your nervousness, so you would likely come up with other two wrong solutions.

It had been 3 hours since the beginning and you still wouldn't have any ideas. You would start looking all the subtasks, searching for some morsels of points that you could get. You found subtask2 easy. After coding it out, you would find the solution heuristic and finally found a correct solution.

You would get 100 at the 4-hour mark. You would not be satisfied with what you had done, and as a veteran Codeforces and Topcoder coder, you would ignore the answer-only task and run rashly for 100 on the third task.

After finding a plausible solution, you would think that you would solve it in 20min, and would still have time for the first time. However, the task didn't crack even when the contest ended, and you would end up getting 105.

On the second day, you would be even more nervous and want to get points as soon as possible. After getting 99.71 on the first task at a fantastic speed. You would start coding 100 points for the second task without any thinking on the third one.

However, your solution turned out to be wrong again. But you would soon find a new solution based on an arbitrary spanning tree. All that was left was a detail.

That detail proved to be your bete noire, and you would spend so much time on it without any progress. You would find the spanning tree special---all edges were from ancestors to descendants, and find a solution based on this feature.

However, your coding skill was too poor. Time was fleeting and your code was always a fixer upper. You would be so frustrated to find your solution was wrong again at the 4:30 mark.

The contest was extended by 30min and you would manage to get some subtasks done. Your efforts proved to be futile and you ended up being several places behind the gold medal.

You would receive many consolations from your friends. You would even wonder whether you were a shame to your country and school.

Your friend would even be cynical about your performance, saying that you had no experience on IOI-styled contests; that you should have submitted brute forces on all tasks in the beginning; that you shouldn't have rushed into 100 points solution on a random task directly and that you should always have been selecting the subtasks that fitted you most. These words were so true.

Those had been the strategies you had used for multiple competitions. If you had managed to solve some task when there was only a little time left, you would try to solve another and you had always just done it before the contest ended. You would never give up half way on a task, and would always do answer-only tasks after all other ones. You had won NOI2016 this way. Ironically, the first time these strategies failed altogether was in IOI.

More ironically, the first time you ever got a silver medal(you had been getting gold or bronze ones) was also in IOI.

You would try to list all kinds of alternate histories where you would get gold medals and how they didn't come true. You would still be stunned about what you had done and still wouldn't know why you had done it. You would find that you had so many missteps and that had you made one fewer misstep, you would have ended up gold. However, failing a contest is like rolling a snowball, which starts getting bigger since it is created. Therefore, you should not be surprised to find that your missteps came one after another.

This story is based on my experience in IOI2017. It was written when I was not in a good mood and might be somewhat illogical. Finally, thank those who encouraged me and gave me consolations.

UPD: just found that I was writing in so poor English and basically just putting random pieces of thoughts together. To be honest, I did think a lot after the failure and did not have a central idea about my thoughts. That may explain why this post seems so random.

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 (x3n) 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. peehs_moorhsum
4. SanSiroWaltz
5. W4yneb0t

Div. 2:

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

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.