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!! 
- 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
