Insight Editorial TeamDisclaimer: The content on this website is strictly the property of Insight, IIT Bombay. Content here cannot be reproduced, quoted or taken out of context without written permission from Insight. If you wish to reproduce any content herein, please contact us:
Chief Editors: Ayush Agarwal (210100035@iitb.ac.in), Ishita Poddar (21b030016@iitb.ac.in)
Mail to: insight@iitb.ac.in
The following are purely the views of the authors and Insight neither endorses nor claims any responsibility for their veracity or nature. The content on this website is strictly the property of Insight and the Students’ Gymkhana IIT Bombay. If you wish to reproduce any content herein, please contact us:
Chief Editors: Mihir Kulkarni, Niranjan Thakurdesai
Mail to: insight@iitb.ac.inThis year, Team Code Templars from IIT Bombay, comprising of Navin Chandak, Nisheeth Lahoti and Vipul Harsh, CS students from the class of 2015, qualified for the world finals of the ACM ICPC. They write this post to describe their experiences in Morocco, and advise hopeful teams from IIT Bombay on the road ahead.
They can be contacted on gmail at : navinchandak92, nisheeth.lahoti and vipulharsh.iit respectively
ICPC, short for International Collegiate Programming Contest, is an algorithmic programming contest on an international scale: it’s about coming up with algorithms for well-specified problems and implementing them. It involves several stages, which have the same problem format, and differ only in difficulty and number of problems.
Three institutes conduct ICPC in India (IIT-K, IIT-Kgp and Amrita University). Each team can register for up to two of these three.
Stages of ICPC
The first stage of ICPC takes place online. Anyone (in teams of 3) can participate. The problems in this stage range from extremely easy (hello-world level) to one problem of the sort that about 3-4 teams from IITB typically solve. About 10 teams from insti qualify for the next stage.
The second stage has around 10 problems, each of higher difficulty than those from the first, to be solved in a fixed duration, typically 5 hours. You need a combination of both algorithmic and coding skills to crack this round.
About 5-6 teams from India get selected every year to participate in the international level of the contest (with at most one team from each college). For the past 3 years, one of those teams has been from IITB (You need to continue the trend!)
It is easiest to qualify for the second round via Amrita University, because they take a higher number of teams. IIT-K on the other hand, takes just one team per college. For selections to the world finals, qualifying from IIT-K is easier if your primary skill is algorithms rather than coding, and Amrita University otherwise. We didn’t apply for IIT-Kgp because we found that the previous years’ problem sets were coding-intensive and focussed less on algorithms.
Preparation for ICPC
There are several online coding platforms : TopCoder, Codechef, Spoj, Hackerrank, Codeforces. These have a lot of ICPC-like questions, with their difficulty levels clearly mentioned. Some websites provide solutions sometimes, and if not, a quick Google search can usually bring up blogs explaining the solutions. It would be a good idea to appear for TopCoder SRMs, Codechef long challenges and cook-offs, and other contests regularly so that you improve on your coding and contest-taking skills. Besides, previous years’ ICPC problems are available on the ICPC archive webpage.
[pullquote]For selections to the world finals, qualifying from IIT-K is easier if your primary skill is algorithms rather than coding, and Amrita University otherwise. [/pullquote]
The ranking of contestants is done in each round in the same way: they sort by the number of problems solved first. Among people with same number solved, they add up the submission time of each problem, with extra time (typically 20 minutes) added for each wrong submission.
There are two key factors for doing well during the contest : Accuracy and Speed, in that order (assuming you are all good with data structures and algorithms, which you will be, if you are an IITB team and have practised a lot of good problems).
Accuracy, in particular, is far more important than it looks. If you code up a problem correctly on the first go, then you’ll save up on a huge amount of person time and computer time, which often gets wasted in the process of debugging. It often is very tempting to think of a solution quickly and try to code it is fast as possible. But that often leads to two types of problems : you may code up wrong solutions (which includes coding up an entirely flawed algorithm, or missing some corner cases), or you make coding errors. And take our word for it; both these types of mistakes are super-costly. The total time which you possibly gain by trying to hurry is far outweighed by the expected cost of making these mistakes, since debugging takes a lot of human time and machine time (remember, you share a single machine between three people).[pullquote]If you code up a problem correctly on the first go, then you’ll save up on a huge amount of person time and computer time, which often gets wasted in the process of debugging.[/pullquote]
So it’s important that you think about a solution calmly, take a few minutes to verify that it actually works, think specifically about corner cases, and think of some sort of program structure before you actually take the machine and write down the code.
A few tips
1. It’s always good to discuss a problem which you have solved with one other member before coding it up to make sure that you have understood the problem correctly, solved it correctly and haven’t missed corner cases. This helps you save a lot of debugging (wasted) time.
2. Practise a lot as a team, in the exact format of the contest, and try various time-management strategies to see what fits you the best. For instance, we strictly followed this algorithm for person-time-management :
Check the number of questions you have found the solution to, but not coded yet. If there is just one such question (which is being coded currently), one person should code it and the other two should try to come up with algorithms for other problems. On the other hand, if there are some questions waiting to be coded, then two people should code the current question: one writing the code, and the other constantly watching out for errors and helping the coder. Only one person should look for new algorithms.
Now, it seems very wasteful on the first glance to have one person just looking at the code (And most of the time, we were indeed in that state of there being some questions waiting to be coded). But we found that it saved us enough time in debugging to more than make up for the supposed waste.
3. It’s sometimes very useful to just iterate over the algorithms which you know of, and try to apply them to the given problem. For instance, it is often not intuitively clear that a problem can be reduced to max-flow, but it reduces fairly easily once you think of ‘Max-flow’ explicitly.[pullquote]It’s always good to discuss a problem which you have solved with one other member before coding it up to make sure that you have understood the problem correctly, solved it correctly and haven’t missed corner cases. This helps you save a lot of debugging (wasted) time.
[/pullquote]
Also, segment trees are the answer to life, the universe and everything.
Our World Finals Experience
We qualified for World Finals via IIT Kanpur regional rounds. The World Finals during our year was in Marrakesh, Morocco. Our accommodation was in a brilliant resort (Amitabh Bachchan had stayed in it when he had visited Marrakesh), complete with a golf course. We had a grand opening ceremony, with a lot of Moroccan performances, and then dinner in a traditional setup.
The event was managed primarily by student volunteers from different universities in Morocco, and they handled it incredibly well, also mingling a lot with the participants in the process. Also, Bollywood films are very popular in Morocco, to the point that many Moroccans told us that they would support us the most (after their home team, of course) in the contest 🙂 .
The contest was in a grand auditorium, with rows after rows of systems put together. The contest went very smoothly. The problem set of this year was easier than other years. In fact, there was a team which solved all the problems, something that has never happened in the history of ICPC. However, our time-management in the world finals was significantly worse compared to the regionals, and we wasted quite some time within the contest, a situation which could have been avoided with a little more practice and alertness (and luck, maybe).[pullquote]The problem set of this year was easier than other years. In fact, there was a team which solved all the problems, something that has never happened in the history of ICPC.[/pullquote]
We got the 64th rank, which was jointly (with IIT-Roorkee) the best from India, but just 50 percentile in the world (Improve this in the years to come!). The contest concluded with a party involving games, barbecue, local street-food and artefacts,and dance (Nisheeth lost his phone while dancing). We went around Marrakesh and Casablanca for a few days after the contest, and it was a fun experience.
Final words
If you are participating in ICPC, and have to take one thing from this piece, it would be “practice”. Practice a lot of good problems, in the contest setup. Work on your accuracy too.
You can approach us for any help at any time. And if you are the team going for the World Finals, then definitely get in touch with us: we would be more than happy to give you detailed tips for the finals, based on all that we did right and, more importantly, all that we did wrong.
Wishing you luck!
Code Templars.