How to improve and how to train: My personal experience and humble request

Hello @all,

Following the series of tutorials I have been writing, I decided I would do something different this time, but equally important! I’m talking about analyzing the “lower-bound” of programming competitions, taking Codechef and some of its most famous users as an example (mainly because it’s the resource I use the most myself to learn new techniques and where I’ve learnt more on my first year as a more regular “competitor” and where I actually started learning new things).

  • Foreword on Codechef Long Contests structure

From my personal experience, both as a competitor and as a problem setter on Codechef’s long contests, I think that the structure they follow is actually a great structure for people who are on a beginning to intermediate level (like me) to learn new techniques AND successfully apply them on live contests.

This contrasts greatly with the structure of Cook-off contests or with the structure of usual Codeforces rounds.

Even though it’s not fair to compare both structures from a learning-concepts-point-of-view, I personally prefer the Long contest format for a multitude of reasons:

  • There is no time pressure for me at all;

  • I can focus on writing clean code and organizing my ideas as I develop an algorithm;

  • There are always 1/2 problems I can usually solve, so this keeps me motivated;

  • There is the Challenge Problem;

  • There are very advanced concepts on some problems;

Those are the main reasons why I prefer the Codechef Long Challenges to any other programming competition out there and as things seem to remain stable, I believe it will be so for while I am interested in Algorithms (which will be always!!).

With this said, this contest structure is wonderful for people who are only now starting to learn new things and I really encourage it to stay as it is!!

Now, I will analyze the structure in more depth!! :slight_smile:

  • 10 problems, 10 days: A multitude of challenges

According to the page for the Problem Setting guidelines, here is a translation of the section where the problems are characterized by its level of difficulty:

Difficulty Levels

Long Contest Problems

We use six different types of problems of varying difficulty in our Long Contests:

1 CAKEWALK: The problem should be solved by someone who knows any programming language and basic data structures like arrays and lists. No further knowledge should be considered mandatory to solve these problems.

2 SIMPLE: These may or may not require some algorithms but whatever is required should be immediately obvious from statement, similar solution idea should be easily available in any text book, easily searchable, and more importantly should be very easily implementable. Almost zero genius is required.

2 EASY: This should be fairly easy for most of the contestants to solve this problem without too many optimizations. A novice programmer should be able to solve it within his/her knowledge of programming. May not require knowledge of advanced data structures.

2 MEDIUM: These problems should require some more work for anyone to solve them. Advanced programming concepts like DP, Graphs, Trees or Mathematics etc, may be needed to solve them. May also require knowledge of advanced data structures. However it should not involve looking into research papers for the problems to be solved. Not easy to make. A novice programmer should not be able to solve them without putting in lot of effort.

2 HARD: These are the hardest to make. They should be able to challenge the best programmers out there for a 10 day contest. The idea to solve should be hard to come up with even with the knowledge of most advanced algorithms. Often, Problem Setters have made use of problems in research to get ideas regarding such problems.

1 CHALLENGE: All the above problems are binary problems (Either they give a full score of 1 or none 0). They are typically optimization problems (maximize or minimize). The best submission gets a score of 1 while the rest get scores relative to the points of the best submission. The difficulty of getting an accepted solution on the challenge problem should not exceed “Medium”. Ideally it should lie between “easy” to “medium”.

For each problem that is received for selection, the difficulty level is initially suggested by the problem creator itself on the annoucment e-mail. Something in the lines of:

Problem name: XYZ, Difficulty: EASY, Contest: AUG13

On each contest, and based on the general concept that is needed to solve a given problem, the problem tester will suggest any last minute changes and will actually make some very brief comments on the general ideas needed to solve the problem and suggest any changes… More importantly, he/she will adjust the difficulty level of the problem, if necessary to “respect and follow” the general guidelines.

I believe this is good, as it allows the contests to be kept relatively uniform in terms of difficulty from month to month (especially because testers ocasionally change from month to month) and it ensures something in the lines of: cakewalk problem is really cakewalk, hard problem is really hard.

As such, when we, as contestants, attend several contests, we sometimes are able to immediately identify a given problem as Cakewalk, Simple or Hard and it allows us to use our time on the best way we understand to improve our performances.

However, I believe that somehow, or somewhere along the way, the guidelines were a bit forgotten, or at least, tester’s for a given month apparentely find EASY problems to be considered SIMPLE and other things like that.

I also believe that this is due to the community and to the training that the people who attend this contest already have. Nontheless, to me, and the way I see it, the contest is getting harder in the long run.

For example, my problem CLMBSTRS, used in FEB13 Long Contest, was classified as SIMPLE and only having as a pre-requisite the topic Combinatorics.

Nontheless, on the Editorial (which, as I recall was largely based on the text I sent to Editorialist), I mentioned concepts such as:

  • Matrix Exponentiation;

  • DP/Memoization;

  • Actual Combinatorics for the formula deduction;

  • Conversion of a number to binary and count of the set-bits of that number;

Despite these somewhat advanced concepts being mentioned, the problem respects and correctly falls under the SIMPLE difficulty level… After all, Fibonacci numbers are a very well studied and highly spread topic, so it is thought that, in theory, a newbie should be able to come up with a solution with some research effort.

For me, this is what blows me away completely… I mean, the concepts I mention on the editorial are concepts which are taught (on my Computer Science course here in Portugal) on a Master’s level subject, called: “Advanced Algorithms”, and yet, this problem is classified as SIMPLE. Master’s subject is taken only after 3 years of studies in this course, with only two algorithm subjects being taught before that one: “Introduction to Algorithms and Data Structures”, where C language is used to teach basics of programming along with memory management and pointers (linked lists, Binary Search Trees and stacks design), Sorting Algorithms (all of them) and along with Graph Algorithms (however, these ones weren’t evaluated pratically, so we only read powerpoints with theory on them). I concluded this one with a grade of 16/20 and NOT knowing how to implement graphs algorithms and trees very well (I used Internet to do projects mostly).

The other subject is: “Analysis and Correctness of Algorithms” and from what I saw (I will only do this subject next semester) it will focus on Linear programming and more advanced graph concepts (like Kruskal’s Algorithm, MST, Dijkstra, Tarjan’s, etc) and on theory about complexity (Big Oh notation, Omega notation, etc).

I want to hear people’s opinion on this matter, explanations or justifications why this is so. Especially from @mugurelionut as I know he is a university teacher and does research in Advanced Algorithm topics.

Besides this HUGE disparity, which to be honest, literally blew me away in the beginning, we shall not forget about how HARD some problems really are, involving hard geometry algorithms, string-matching algorithms, concepts like, Gaussian Elimination, FFT, and a huge amount of other things which just make them on a level of a Master’s degree subject… Which for me, is very, very demotivating, as, as you all know, I have no previous experience on programming contests.

Some tips from the pros would be great.

What can people like me do, armed only with the small university subjects and short period experience, in order to get better on these contests?

I already understood that strong mathematical background is MANDATORY, but, is there any secret, or any approach one can take to “simulate” preparation for big competitions?

I know practice is key and focus on new concepts as well, but, I was looking past that with this post, I want to know how can such practice be done efficiently and what are some good ways of doing it… How do coaches of ACM-ICPC prepare students to attend these sort of events?

I guess there’s more to it that just “blindly” solving problems… What is the approach to take when one gets stuck on a concept? The teacher explains it better, review theory, etc?

Once again, if @mugurelionut and other usual seasoned pros could help me (us) out here, by providing us some tips, I would be deeply thankful =)

Best regards,

Bruno Oliveira

21 Likes

So I would like to share my opinion about this topic, because I’ve dedicated to contest programming for some years.

And I can say to you, that practice is a key. Nothing more and nothing less. Of course you need to know some bunch of classic algorithms and you can find it in books or anywhere on the internet. But as you said, only theoretical knowledge of some algorithm is useless, while you don’t implement this on your own. Even, when my team prepared for ACM-ICPC we mostly (all the time) solved old contests.

What I personaly do is competiting in as most contest as possible. Even Codeforces has perfect option to run old contest virtually. I try my best in that two/three hours. Than I look for some editorial or tutorial. Learn a new approach and try to code it (that time already out of competition). That’s I think is the best way to learn new things and improve yourself.

And lot of practice, can you take up really high in leaderboards. I know some people, who did it. But sadly, to be best, it’s not enough. Practice can really help you, but you can’t compare to people with gift. Also they need to practice too, but they are quicker, more receptive… And I mean people like tourist, Petr or ACRush. But don’t give up :slight_smile: Just try harder.

Last thing I can recommend to you is taking higher classes. I’m also studying computer science and I just finish my second year at bachelors studies and I’m already done some classes from Master. Because they are more fun, they are harder and they keep me busy. And so they improve my knowledge even better, because I must learn some new thing “on the fly” and by myself.

5 Likes

i had to add something to the question. i wished to know , whether it is ok to start with CLSR , being new to coding,coz , the competitions which i have yet participated in, and the problems which i have yet solved, need implementation , rather than the deep analysis of the algorithm we are using… so can anyone suggest some good offline source which i can refer for being good at implementation part or should i go on with the CLSR?

I think that there is a rather large difference nowadays between what is being taught in universities (at bachelor and master level) and what is expected from a competitor participating in programming contests. To be more precise, in order to do really well in programming contests you need to know a lot more than what you might learn in university (note that I’m not saying that the base algorithms used in programming contests are not taught at university level, but it is very unlikely that all of them are taught in the same university; usually, at university level, there are only a few algorithm and data structure classes and the teacher can only fit so much content in these classes; moreover, some of these classes are only basic classes and they need to teach the basic concepts and only very few of the more advanced topics).

I think that there is something similar going on at high school level. For instance, the International Olympiad in Informatics (IOI) has an official syllabus: http://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf Have a look at the syllabus and then tell me how many of those topics you studied during high school classes :slight_smile: Or, even if you studied them, you probably did not work through too many applications so even if you know the basic concept you might have troubles applying the concept in a more complex problem.

Thus, it seems that in order to do well in programming competitions (starting from high school olympiads and beyond) a lot of practice and learning on your own is required. However, this is not always enough for everyone (or it may not lead to a fast enough progress). In Romania, at least, pupils participating in high school olympiads search for private tutors (usually successful former contestants) in order to get a more focused training (training specific to programming competitions, unlike the kind of stuff you would learn in high school or university classes, which do not have programming competitions in mind).

I will try to write some more on this topic later on, when I will have some more time (including my own experience with teaching a Data Structure class and trying to use Codechef long contests in order to motivate students to learn more :slight_smile: )

17 Likes

Hello @mugurelionut,

Thank you very, very much for your reply :slight_smile: It goes exactly on the direction I thought it should go: that the university curriculum is not (and better, not even close) good enough to help one doing well on these sort of competitions…

As far as my own experience on these sort of competitions goes, I never attended any High School programming competition (mainly because I had no interest back then) and, as such, I can say that I started coding quite later, at least, for someone so interested as I am…

Regarding Portugal’s performance on ACM-ICPC this year, I believe we had a team attending there, but, I don’t think we did that well…

I also know some guys in my university which were participants at an older IOI event and which are studying CS like me… I tried to talk to them to get some more insights, but, all they say is that their preparation during High School to attend IOI with coaches and with focused training was actually the key step in the build-up of their knowledge nowadays… Unfortunately, I can’t have any sort of coach or private tutor to guide me, which is also why I am trying to “make up for it” by being more proactive and trying to attend more contests here on Codechef… I just fear that being “alone” or without any support might hinder my own learning process… (much like what happens with jogging with the wrong training sneakers: we can go far with lots of training and effort, but, if we change shoes we see improvements much faster… I might be with the wrong sneakers at this moment)

Besides all of the above, based on the Syllabus link you just showed me, I see that actually, from all the huge amount of topics covered, only the most basic topics are addressed (much more focus is given on how to work with Linux and command-line and how to compile programs and write Makefiles, etc) and no advanced topics are actually covered, which once again leads us to the fact that university curriculum is not enough…

Best regards,

Bruno

4 Likes

i had to add something to the question. i wished to know , whether it is ok to start with CLSR , being new to coding,coz , the competitions which i have yet participated in, and the problems which i have yet solved, need implementation , rather than the deep analysis of the algorithm we are using… so can anyone suggest some good offline source which i can refer for being good at implementation part or should i go on with the CLSR?

being a beginner myself, can’t wait to get to read valuable answers here.

2 Likes

Thank you very much for your answer @michal27!!

It’s what I’ve been doing myself, train hard everyday, read lots of texts, write tutorials, etc, but, getting these sort of answers can also help me a lot I think :smiley:

Doing CLRS is good for the theory, and indeed solving the exercises does help think about algorithms etc. Its not good for implementation definitely, but I don’t think there are any offline sources for teaching implementation of algorithms; at least not as well as you’d get online.

To answer your question specifically, yes, do go on with CLRS. Don’t spend all your time on it though: keep practicing problems from Online Judges as well.

1 Like