(this was originally intended as a comment to another post, but it turned out very lengthy, so I separated it into its own post)

As it's often in debates, I think in this one there is too much polarization on both sides (people just attack each other), and a lot of ambiguity. I think there are some points to be made.

Premise

1. Let's be kind to each other. Like it or not, this is just a current trend in the history of Codeforces, and it too will pass. No need to attack anyone personally. If you want to criticize, let's provide constructive suggestions.

2. I've set contests before too, and I know that setting problems and coordinating is a very difficult job. It requires a lot of hard work, skill, experience, and patience. So like Anton's and other coordinators' style or not, let's not forget that they have done a lot of work, and let's thank them for that. Thank you!

3. It's also very mean to single out one person for the possible issue. While Anton may have a lot of impact here, there are many moving factors at play, and let's consider it as a "trend", and not particularly tie it to a single person. Let's discuss the "trend" itself and how we can possibly make thing better if needed. I also personally enjoy a lot of Anton's problems too, even though I find them maybe too much math/adhoc/etc heavy (especially when there are several in a row). But let's discuss this in depth below.

4. I also don't find comparison to Atcoder fully valid. If you look at ABC and ARCs, you will find plenty of algorithms, data structures, and so on. Sure, AGC may be skewed towards adhoc and math, but that's not only what Atcoder is.

5. Some fun observation: I find a lot of very high rated people really enjoy AGCs, and adhoc/constructive/etc problems. I personally can't really appreciate AGC beauty myself (probably because I am less skilled and don't usually get to problem C/D), and I think similar thing happens here. Very high skilled people may like adhoc/etc more for different reasons (for example, they may find a lot of DP/etc very standard. It's probably easier to come up with a fresh adhoc than with a fresh DP problem), but let's not forget about other 95% of population. For a lot of them, even something like manipulating things in a set may be exciting (especially with a great real life statement). So I think when asking for opinions like in Anton's post, it's important to include a great range of people with different skills; similar thing applies to setting contests.

Defining a problem

1. For the lack of clarity, people use a lot of words to describe the recent trendy problems. Ad-hoc, math, constructive, etc, etc. Let's not pick on these words ("hey, it's not constructive at all!"), because I feel they are used interchangeably for the lack of a clear concept. So what is the current "trend"? I feel there are several things to describe it (only some of them may apply):

   • It's very observation oriented (you consider problem on paper or computer to find some patterns, etc). After you notice something, it becomes easy.
   • It doesn't require much of well-known algorithms and techniques (including, but not limited to, dp, graphs, data structures, sets/maps, etc), and doesn't fit into these standard categories.
   • Often it feels like there is not much benefit from a computer, and implementation is light.
   • It could be purely math competition problem, or not too far from it.
   • I also notice that a lot of these problems have very artificial statement and setting (like you are given array/permutation and some weird limits/operations/structure, and you need to find something). For me, that indeed doesn't add beauty to the problem, and feels repulsive, but of course it's subjective.

2. Related to the previous point. A lot of people try to describe what they want, but do it poorly. They say: we want more data structures/dp/graphs/implementation/standard problems/etc etc. I think there is again a lot of ambiguity and a lack of clear concept, so let's not criticize it as "not every contest should have a DP/data structure problem", or "there shouldn't be standard problems" — this is clearly not what people actually want. Let's also not say that "ad hoc problems matter" or constructive problems are cool. That's also of course true, but I think that's not what this debate is about. So what is it about?

3. I think people generally don't fight against adhoc/constructive problems themselves. They fight against unbalanced distributions in a lot of recent contests, and I agree with them. When there are too many problems with a similar topic, it becomes boring. If the recent trend was "2-3 binary search problems in every contest", then people would fight against binary search too. I think people don't mean "there shouldn't be adhoc problems", or "we want graph problems in every contest", or "DP never appears anymore" — they just say they see a big skew to adhoc problems recently, and it's a valid concern.

So what to do?

1. I think an important discussion would be what is a good problem distribution in a contest should be. Some points:

   • I think it's very possible to give "algorithms/data structure/implementation" problems even as div2 A-D. "Data structure" here can be something as simple as sorting, or using a set, or making elements unique, or a simple parsing. There are a lot of problems that can be set with these.
   • Implementation is also important. I, and I think a lot of other people, find implementation interesting too. Figuring how to best implement something that doesn't seem very elegant at first is a great problem as of itself in programming competitions.
   • Problems in a contest can be beautiful, but their combination can still be bad. I think Global Round 9 is a great example of this. When first 5-6 problems don't need almost any algorithms and are done as "play with a problem on paper, then code something trivial when done" – it gets boring.
   • Let's look at famous well prepared contests, like NEERC ICPC semifinals, IOIs (and other OIs), and Google Code Jam rounds. They often have a great distribution. If there were 50% of adhoc problems there, that would be weird, right?

2. So what is a great distribution for a contest? I may suggest doing something like this to get a good distribution.

   • Let's take a well prepared team contest (like NEERC ICPC semifinal), exclude everything that is team competition related and not suitable for individual contests (really hard data structures, hard geometry, etc), shrink number of problems to 5-6, and take that.
   • Or let's take 8-10 random problems from a good online judge (like Timus, or even CF archive itself), again throw away too hard or weird problems, and that should be good.
   • And anyway if more than 30% of your problems are on the same wide topic, or feel artificial, or something, you should reconsider it and mix things up.

What are your ideas for a good distribution? And what do you generally think on the debate?

Hello, Codeforces

Here is something I've been working on for a while now. It's still in beta, but I think it's in a good shape to share. I think it's relevant to CF community, but if not, sorry for the spam :)

I am an ex-Google software engineer, and I wrote down almost everything I know about interview preparation, and launched a small website. It is something of a preparation course and guide at the same time.

Here is what's inside:

• 40+ articles about everything from resume to algorithms to compensation.
• Selected leetcode problems with hints, solutions and such.
• Code examples and explanations of common algorithms and techniques.
• A place where you can track your interview preparation progress.

Please take a look and let me know what you think. Hopefully, you will find it useful in your own preparation!

Link: https://interviews.school/

P.S. I would appreciate any feedback. Feel free to point to any errors you will find. And what else can I add?
P.P.S I think some articles there will be relevant to people learning competitive programming as well. For example, you can check out articles on sorting, dynamic programming, heaps, and graphs.

Hello, hope you all are well and doing fine!

Recently, I've been solving some old AtCoder problems that are only available in Japanese (with Google Translate and a lot of guessing). Problems are really nice, so I decided to put short English translations of them on GitHub. Nothing fancy, just several sentences describing the core part of each problem. There are 10 translated problems so far:

https://github.com/ADJA/AtCoderTranslations

(current problems are in the 2100–2400 difficulty range)

Contribute?

How you can help: There are ~382 untranslated problems from the early AtCoder Beginner and Regular contests left, so I encourage you all to contribute! No Japanese required.

It takes about 5-10 minutes for each problem (please solve the problem first if you don't speak Japanese), and can be done right from the GitHub web interface.

Please see contributing section in the README for more information: https://github.com/ADJA/AtCoderTranslations#contribute

I think with enough contributors, all problems can be translated just in several weeks. Plus, solving the problems is a good training too. Isn't that a time well spent in the quarantine? :)

Hello, CF community.

About a year ago I wrote and shared a blog post about my approach to interview preparation that helped me get offers from Google, Facebook, Uber and Amazon. I thought that I can share this here too – I have a long experience with competitive programming, and hopefully other people here can find something useful for them:

http://adilet.org/blog/your-ultimate-guide-to-interview-preparation/

Let me know if this helps, and thanks for reading! All questions are welcome :)

Hello, CF community.

I am writing about algorithms for fun and to spread the knowledge.

Please read my new article about stress testing – a useful technique to automatically find bugs in your solution: http://www.algos.school/stress-testing

Would you be interested in the future algorithm articles like this? Please follow algos.school on facebook, twitter, or telegram.

Thanks!

Hello, CF community.

I am starting to write about algorithms for fun and to spread the knowledge. Please read my new article about sparse table – a cute data structure to find range minimums in an array:

http://adilet.org/blog/sparse-table/

P.S. A little bit about myself: I was active in the competitive programming a while ago, especially during my two ACM ICPC World Finals in 2014 and 2015. Currently, I am working for Google and trying to revive some old algorithms knowledge :)

Would you be interested in the future algorithm articles like this? Follow me on twitter here: twitter.com/adiletzx

Better late, than never :) Almost a year have passed, but I finally finished a two-part blog post about our team's (Nazarbayev University from Kazakhstan) journey to ACM-ICPC World Finals 2015 in Morocco.

Here are the links. Enjoy!
http://adilet.org/blog/19-04-16/
http://adilet.org/blog/02-05-16/

It was a fun event, thanks to everybody who made it happen!
And good luck to all teams in Thailand soon ;)

P.S. You may also be interested in a blog post about ACM-ICPC WF 2014 here

550A - Two Substrings

There are many ways to solve this problem. Author solution does the following: check if substring "AB" goes before "BA", and then vice versa, if "BA" goes before "AB".

You can do it in the following way: find the first occurence of "AB" then check all substrings of length two to the right of it to check if substring "BA" also exists. Then do it vice versa.

Complexity of the solution is O(n), where n is the length of the given string.

550B - Preparing Olympiad

Because of the low constraints, this problem can be solved by complete search over all problem sets (there are 2ⁿ of them).

For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most difficult and the easiest problems in linear time, iterating over the problems that we included in our current set/bitmask. If this problem set can be used, we increase the answer by one.

Complexity of this solution is O(2ⁿ·n).

550C - Divisibility by Eight

This problem can be solved with at least two different approaches.

The first one is based on the "school" property of the divisibility by eight — number can be divided by eight if and only if its last three digits form a number that can be divided by eight. Thus, it is enough to test only numbers that can be obtained from the original one by crossing out and that contain at most three digits (so we check only all one-digit, two-digit and three-digit numbers). This can be done in O(len³) with three nested loops (here len is the length of the original number).

Second approach uses dynamic programming. Let's calculate dp[i][j], 1 ≤ i ≤ n, 0 ≤ j < 8. The value of dp is true if we can cross out some digits from the prefix of length i such that the remaining number gives j modulo eight, and false otherwise.

This dp can be calculated in the following way: let a_i be ith digit of the given number. Then dp[i][a_imod8] = true (just this number). For all 0 ≤ j < 8 such that dp[i - 1][j] = true, dp[i][(j * 10 + a_i)mod8] = true (we add current digit to some previous result), dp[i][j] = true (we cross out current digit).

Answer is "YES" if dp[i][0] = true for some position i. For restoring the answer we need to keep additional array prev[i][j], which will say from where current value was calculated. Complexity of such solution is O(8·len) = O(len) (again len is the length of the original number).

Code for DP solution:

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) (int) x.size()
#define all(a) a.begin(), a.end()
#define prev sadasdjksgjkasjdklaj
 
const int MAXN = 105;
 
string s;
int n;
bool dp[MAXN][8];
int prev[MAXN][8];
 
int main() {
 
    getline(cin, s);
    n = sz(s);
 
    memset(prev, -1, sizeof(prev));
 
    dp[0][(s[0] - '0') % 8] = true;
 
    for (int i = 1; i < n; i++) {
        dp[i][(s[i] - '0') % 8] = true;
 
        for (int j = 0; j < 8; j++) {
            if (dp[i - 1][j]) {
                dp[i][(j * 10 + s[i] - '0') % 8] = true;
                prev[i][(j * 10 + s[i] - '0') % 8] = j;
 
                dp[i][j] = true;
                prev[i][j] = j;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (dp[i][0]) {
            string ans = "";
            int curI = i, curJ = 0;
 
            while (true) {
                if (prev[curI][curJ] == -1 || prev[curI][curJ] != curJ) {
                    ans.append(1, s[curI]);
                }
 
                if (prev[curI][curJ] == -1) break;
 
                curJ = prev[curI][curJ];
                curI--;
            }
 
            puts("YES");
            reverse(all(ans));
            cout << ans << endl;
            return 0;
        }
    }
 
    puts("NO");
 
    return 0;
}

550D - Regular Bridge

Let's prove that there is no solution for even k.

Suppose our graph contains some bridges, k = 2s (even), all degrees are k. Then there always exists strongly connected component that is connected to other part of the graph with exactly one bridge.

Consider this component. Let's remove bridge that connects it to the remaining graph. Then it has one vertex with degree k - 1 = 2s - 1 and some vertices with degrees k = 2s. But then the graph consisting of this component will contain only one vertex with odd degree, which is impossible by Handshaking Lemma.

Let's construct the answer for odd k. Let k = 2s - 1.

For k = 1 graph consisting of two nodes connected by edge works.

For k ≥ 3 let's construct graph with 2k + 4 nodes. Let it consist of two strongly connected components connected by bridge. Enumerate nodes of first component from 1 to k + 2, second component will be the same as the first one.

Let vertex 1 be connected to the second component by bridge. Also connect it with k - 1 edges to vertices 2, 3, ..., k. Connect vertices 2, 3, ..., k to each other (add all possible edges between them), and then remove edges between every neighbouring pair, for example edges 2 - 3, 4 - 5, ..., (k - 1) - k.

Then we connect vertices 2, 3, ..., k with vertices k + 1 and k + 2. And finally add an edge between nodes k + 1 and k + 2.

Build the second component in the similar manner, and add a bridge between components. Constructed graph has one bridge, all degrees of k and consists of O(k) nodes and O(k²) edges.

Complexity of the solution — O(k²).

550E - Brackets in Implications

Let input consists of , a_i is 0 or 1 for all i.

Let's show that there is no solution in only two cases:

1) a_n = 1.

, for all x, and no parentheses can change last 1 to 0.

2) Input has the form or its suffix with at least two arguments.

This can be proven by induction. For input there is no solution, for longer inputs any attempt to put parentheses will decrease the number of 1s in the beginning by one, or will introduce 1 in the last position (which will lead to case one).

Let's construct solution for all other cases.

1) For input 0 we don't need to do anything.

2) For input of the form we don't need any parentheses, the value of this expression is always

3) Expression in the form (where second missed part consists of ones only). Then .

Complexity of the solution is O(n).

Hello, Codeforces!

We are glad to announce that on 4th of June at 19:30 MSK Codeforces Round #306 will be held. Authors of this contest are me (Adilet Zhaxybay) and Timur Sitdikov (Timur_Sitdikov). The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Bekzhan Kassenov (BekzhanKassenov) and Sergey Lazarev (SergeyLazarev), who tested the round, and Maria Belova (Delinur), who translated problem statements. Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon.

By the way, as far as we know, Timur_Sitdikov is the first participant from Uzbekistan, who took part in the preparation of Codeforces round. We hope that everything will go well :)

Good luck to all!

UPD The scoring will be dynamic

UPD2 Editorial can be found here

UPD3 Congratulations to winners!

1. mff

2. I_Love_Nodir.Daminov

3. tun

4. I_love_Ngoc_cmn_Thuy

5. goodhope

Round is over, thanks to everybody, who took part in it!

Hello, Codeforces!

My name is Adilet Zhaxybay, and together with Bekzhan Kassenov (BekzhanKassenov) we are authors of Codeforces #294, which will be held on 28th of February at 16:00 MSK. This is our first Codeforces round and we are happy to invite all of you to participate in it. The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

As far as we know, it is the first Codeforces round, which was completely prepared by the authors from Kazakhstan. We are very honored by this fact and hope that everything will go great. We are encouraging other participants from our country to join us — I am sure, that you can prepare a lot of very nice problems. Preparing Codeforces round is possible ;)

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Nurlan Kanapin (kt-9) and Mansur Kutybaev (mexmans), who tested the round, and Maria Belova (Delinur), who translated problem statements.

Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon. We want to congratulate Codeforces with its fifth anniversary. We, authors of the round, were very lucky to start competitive programming at the time, when Codeforces already existed, and it helped us really a lot!

We love, when authors of the round write a bit about themselves (we encourage everybody to do so) — this helps to feel that there are real people behind the problems. Thus, we will write a bit about ourselves. We are students from Nazarbayev University (nu.edu.kz). NU is a new university with English as a language of teaching, which is located in the capital of Kazakhstan, Astana. Our university participates in ACM-ICPC only from 2012, but the team from NU already qualified to World Finals twice — in 2014 and 2015. We hope that we will do only better in the future!

Good luck to all!

UPD Score distribution will be standard (500 — 1000 — 1500 — 2000 — 2500)

UPD2 Editorial is available here

Congratulations to winners!

1. AkashiSeijuro

2. fmzbtf937

3. mxh3777

4. IGandWFin2019

5. ruozha2 & i_hate_t0nzuk

Round is over, thanks to everybody, who took part in it!

New data structure for solving problems involving palindromes in the strings:
http://adilet.org/blog/25-09-14/

Thanks to droptable for sharing it!

Some impressions from a contestant's point of view:
http://adilet.org/blog/30-06-14/
http://adilet.org/blog/02-07-14/

Thanks to all organizers and volunteers who made this World Finals possible!

Hello!

As a part of preparation for ACM-ICPC 2014 World Finals our team NU 1 prepared (and continues preparing) Algos — collection of some useful algorithms. Today we decided to share it with Codeforces community.

For the ease of use of Algos, all algorithms (with very rare exceptions) can be compiled and executed as is. Moreover, in order to verify the correctness of code and to help understanding the purpose of algorithm, the source code of every algorithm is based on some reference problem (on which the link is provided). Short description and time complexity are also available for every algorithm.

Algos is originally based on the repository on Github. You are very welcome to fork and contribute!

Requests, bug-reports and just feedback are welcome in the comments :)

'Algos' algorithm collection.

Github repository.

Which other algorithms you would like to see there?