Crack ACM ICPC 2022 in 1 year
What is my ACM ICPC story?
Did my team get a rank that is good enough to boast about on quora? Definitely not! But the experience surely is. I came to know about ICPC in my second semester of Engineering. I come from an IIT (Gandhinagar) which still does not have a great ‘coding culture’, at least not in Competitive Programming. But one of our professors is really passionate about CP, and she told us about it. One another thing that makes our team unique is that none of us are CS majors!
We started our preparation in the summer of the first year, although it was not much rigorous. We participated in the online rounds of the competition and managed to hit the first 3 problems in an hour. We were very close to the next two problems, but couldn’t solve it. However, we managed to qualify for IIT KGP regionals (perks of being at an institute where there are only 3 teams competing!, my friends from IIIT couldn’t qualify even after solving 5 problems :p). After qualifying for the regionals, we felt quite motivated and started preparing more rigorously, solving more problems on Online Judges. We also prepared the 25-page booklet.
Apart from preparation, the journey to IIT KGP was quite wonderful (and yes, it was funded from the institute, another perk you get when you have only 3 teams going to the regionals :p). We had a great experience meeting some of the finest coders from the country. The contest was good, and we managed to solve 2 problems (very close to the 3rd one) and got a rank of 40 among 80 teams. The last minutes were nerve-wracking, as we got our last problem submitted 100 seconds from the finish of the contest. It was one of the good problems from the problem set. Maybe, we spent way too much time on tough problems in the beginning. The food was good too. And, we also wandered through the city of Kolkata, which was quite a great experience!
Our neighbors (students from DAIICT Gandhinagar, Team - Fruit Salad) won the competition. Anup Kalbalia, the Tech Lead at Codechef gave many insights about the world of Competitive Programming, which were quite motivating.
We will try to be back next time, more strongly and firmly!
What is ACM ICPC
The ICPC formerly known as ACM-ICPC (Association for Computing Machinery - International Collegiate Programming Contest) is considered as the "Olympics of Programming Competitions". It is quite simply, the oldest, largest, and most prestigious programming contest in the world.
The ICPC is a multi-tier, team-based, programming competition. The contest participants come from over 2,000 universities that are spread across 80 countries and six continents.
In terms of prize money, the top team takes home $15,000 along with the ICPC Gold medal. Three other teams getting Gold Medal are awarded $7,500. Each Silver Medal team gets $6,000 and each Bronze Medal team is awarded $3,000. Courtesy of the UPE Computer Science Honor Society, the First Solution Award will be $1,500. For the other solved problems, The First to Solve Award will be $1,200.
And more important than all, the winners also get some super bragging rights and job offers from some of the top software companies in the world!
The contest consist of two rounds:
The regionals are organized by the local universities of different regions spread across the globe. The winners of these regional rounds of the contest get to represent the country in the ICPC World Finals. The Asia Regionals in India will be held at 4 sites viz. Amritapuri, Kolkata, Gwalior, and Kharagpur.
Every regional contest site gets a "slot," which is an invitation for the team to compete in the World Finals. Typically, all the "slots" are allocated by December 31 every year. Additional slots may also be allocated based on student and institution participation, geographic coverage, and team performance. A few bonus slots are allocated each year for growth, innovation, and hosting. So depending on the number of slots that each regional site gets, that many numbers of top teams it can send to the World Finals.
Also, each regional site can have multiple rounds to select the best teams amongst those who apply. Typically they have an online contest, out of which selected teams are called for the onsite contest. These contests happen from the month of October to December.
The pick of the crop from every regional site locks horn at the World Finals.
Contest Format:
It is a team contest.
Each team should have three members and one reserve (3 + 1).
Each team must be headed by a coach, who must be a university faculty or staff member.
The coach can head multiple teams
The contest can have several problems (8 to 10 in general), of varying difficulty levels and mostly being algorithmic in nature.
How should one start preparing for ACM-ICPC?
First of all, try to improve your individual skills in competitive programming, coding, algorithms, and data structures as a whole. There are lots of answers and references on this, so I will skip to the more overlooked parts.
ACM-ICPC is a team competition. You need to compete as a team and not 3 individuals. To improve in this department, do a lot of mock competitions.
You will need to solve problems medium-hard problems to be at the top positions. For this, divide the topics among the three team members, and practice solving hard problems in that area/topic.
There is a single computer provided to a team. Thus, you will need to improve your game on paper. For faster coding, prepare a good initial design of the program on paper such that you just have to type on the computer. For faster debugging, practice debugging and analyzing on paper, looking at the code for finding bugs, and testing on tricky/corner/big cases.
It is a 5-hour long contest. This requires that you have a practice of competing with full attention for 5 continuous hours. Personally, I lacked this.
Practice. Somewhere I read that you should practice every day as if it was the target examination. I cannot overstate the importance of this. The more and smarter you practice, the better you will gain. You will know about where you are lacking, what can you do to improve, what are some good ideas for final hours, what should you do in a crunch situation, and many more things that just cannot be all shared in one answer.
How do I prepare for ACM-ICPC in 1 year?
at First, start learning a programming language clearly like you can start with C or C++. Get comfortable writing code in either of one of these languages C, C++, or Java. Why only C, C++, or Java? Because these are the standard languages allowed in any programming competition.
If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).
Pick an online judge. Recommended ones are Topcoder and Codeforces. These sites have a high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ), and HackerEarth.
To begin with, start with simple problems that typically require transforming English to code and do not require any knowledge of algorithms.
At the early stages of programming, one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.
Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.
Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials or Introduction to algorithms.
Graph algorithms: Breadth-first search(BFS), Depth-first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.
Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication, etc.
Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.
Greedy: Standard problems such as Activity selection.
Search techniques: Binary search, Ternary search and Meet in the middle.
Data structures (Basic): Stacks, Queues, Trees, and Heaps.
Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.
Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.
Computational geometry: Graham-Scan for convex hull, Line sweep.
Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.
The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.
And to practice problems, you can refer following sites
1. http://codechef.com
2. http://spoj.com
3. http://hackerrank.com
4. http://codecademy.com
5. http://topcoder.com
6. http://codeforces.com
To be noted: as a problem solver you should not lose patience, never give up. It’s a long time process. Everything thinks easily and read others' code never do copy from others but learn from others' code.
Hope all your questions got answered!!
