How to prepare for ACM ICPC?

Revision en1, by harrypotter0, 2016-10-12 14:32:00

Well I would suggest you to check out Programming Competition,Programming Contest,Online Computer Programming. Here is the details about as the codechef team promote the students for ACM-ICPC or you can also check out the actual university site which conduct ICPC The ACM-ICPC International Collegiate Programming Contest

And to practice problems you can 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

Good Luck...

for the details about ACM-ICPC 2015 you can read the details ACM ICPC 2015 | CodeChef. I hope you'll find most of the things... Here are some steps to get started and be good at it.

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 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) andHackerEarth.

To begin with, start with simple problems that typically require transformingEnglish to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.

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.

1) Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.

2) Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.

3) Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.

3) Greedy: Standard problems such as Activity selection.

4) Search techniques: Binary search, Ternary search and Meet in the middle.

5) Data structures (Basic): Stacks, Queues, Trees and Heaps.

6) Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.

7) Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.

8) Computational geometry: Graham-Scan for convex hull, Line sweep.

9) 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.

You can find description and implementation of standard algorithms here

Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.

Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challengesor Codechef contests.

Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.

Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.

Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.

Do not spend too much time if you are not getting the solution or are stuck somewhere.

After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.

Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.

Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.

It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here. 76.7k Views · View Upvotes Upvote1.2kDownvoteComments7+ Share Viktória Nemkin Viktória Nemkin, studies software engineering at Budapest University of Technology and Economics. Updated Jan 20 · Upvoted by Jessica Su, CS PhD student at Stanford Originally Answered: Should I get involved in competitive programming? How do I begin? You won't regret if you do so. Doing competitive programming improves your problem solving skills (applies for any topic, not just algorithms), gives you persistence and makes you a lot more confident in yourself, also you can find quite a few nice people who will help you along the way.

You can do a few things to get started in competitive programming. I'm assuming you are a complete beginner, please correct me if this is not the case.

Mindset

This sounds off topic but please bear with me for a moment. What I struggle with a lot is essentially not doing what I know I should and want to be doing. My mind is not focused, I go watch a stupid video on youtube and the whole day is gone. It is really hard for me to get myself going. I don't know you, I don't know if you have the same struggles as I do but maybe some of this advice will help you stay focused if you need it.

Here are a few things I've learnt about doing competitive stuff:

You don't have to and you really shouldn't overwhelm yourself on the first time. Don't go to the bookstore and buy the heaviest, biggest book on Computer Science only to read the first few pages and realize you don't understand it and give up. I'm guilty of doing this a lot. Instead, try to find something that is not so into detail and easier to wrap your head around it. In the next steps I try to recommend you easy to understand tutorials online. Don't wait to get motivated. I find this advice really good because it is a great insight to how your mind actually works. I'm sure there are a few lucky people to whom this doesn't apply but for the rest of us, we are not going to feel like studying and practicing all the time. There will be days when we will get bored doing it. There will be days when we will want to go do other fun things. What makes successful people different from everybody else is that they can handle the boredom of doing the things they want to be doing for a long time. (I've read this here: How to Stay Focused When You Get Bored Working Toward Your Goals .) Don't try to completely change your schedule and study and practice in all of your free time. Completely changing everything is really hard and can easily overwhelm you and make you give up. Just like trying to get down to a healthy weight by eating 500 calories a day. You just can't stick to it in the long run. Instead, go for small changes, but do them regularly. Don't let other people's success demotivate you. You know how they say no matter how good you are, there is an Asian kid who is better than you? I'm no IOI medalist. I did compete in the country level qualifiers to get out but no success. I see famous people answering questions here on Quora and I'm really not one of them. But really, who cares? Feel proud of what you have accomplished so far and instead of comparing yourself to everybody else, try to outdo yourself. Generally, a lot of hard working famous people are also very humble and they will tell you they had their moments of giving up, failing and feeling bad about themselves. You only see their success but not how they got there. I hope this advice helps you stay on track. Now to the more technical stuff.

Knowledge in theory of algorithms and data structures

I started practicing for competitive programming with my teacher in school, the first few things we learnt were:

Data Structures: Topcoder tutorial Binary Search: Topcoder tutorial Sorting algorithms: Wikipedia list of sorting algorithms (They usually teach a few of them like these in this order: Bubble sort, Insertion sort, Merge sort, Heapsort, Quicksort and Bucket sort, a bit different. Look at visualizations too, like at sorting.at they are cool.) Greedy algorithms: Quora: What is an intuitive explanation of greedy algorithms? Backtracking: GeeksforGeeks: The Knight's tour problem, Sada Kurapati: N Queens problem Dynamic programming: Function Space: Fibonacci series and Dynamic programming (And I really like Jonathan Paulson's answer here.) Graph theory and some algorithms: Computer Science Source: Depth/Breadth First Search and Youtube video: Dijkstra's algorithm were the first for me. I think that's basically all I knew when I first competed. Probably other people will tell you a lot of other things, this is just how I started out.

Later, you can find a book that works for you and you can read it or watch an online course to get into the topic more deeply.

Here are some examples:

Quora: Computer Programming: What are the best books on Competitive programming out there?

Quora: What is the best set of algorithms books to read?

Topcoder Data Science Tutorials

Youtube playlist: MIT 6.006 Introduction to Algorithms, Fall 2011

Coursera: Princeton Algorithms course

Coursera: Stanford Algorithms course

Khan Academy course with Darthmouth college

A programming language

I like C++. It is fast, it has its Standard Template Library with plenty of cool stuff. For example if you need a good sorting algorithm you can just include the algorithm library and use one function. It is really useful because you don't want to waste your time on a competition to implement basic things like data structures and basic algorithms.

Some tutorials on STL:

Topcoder: Power up C++ with the Standard Template Library: Part 1

YoLinux: C++ STL Tutorial and Books at the end

And the reference site I use: cplusplus.com

Look up some Containers like vector, list, stack, queue and the sort algorithm I talked about.

Some argue that C/C++ are the only reasonable programming languages for competitive programming. I would say if you don't really like C, go for a high level language. It's better to be comfortable with the platform than to be miserable with C. A lot of good competitors use Java, and they say it is not a drawback for them. Look up similar libraries for your choice of language and try using them!

Practice, practice, practice. A lot.

It's one thing that you know how to solve stuff in theory. It's a completely different thing that you can code it, it compiles and runs, gives no errors, you made sure all variables are big enough so they will fit, it is fast enough and doesn't use too much memory.

You need to go sit down and solve exercises for yourself to be able to do it fast and with no errors on stage. When I'm out of practice I spend 10 minutes debugging a binary search because I just can't write it for the first time. It's not good to spend 10 minutes of your competition writing a binary search.

So doing exercises, not just in theory but finishing them with a tested, working code is really great for you.

Here are a few sites that host online competitions regularly:

Topcoder

Codeforces

Google Code Jam

Codechef

What's really great about these sites that you can post your code and they will test and score you for all the previous competitions. Even better, you can see what others have sent in. You can learn a lot from other people's codes. I've heard that some guys on Codeforces spend weeks optimizing their code, so they run faster than anybody else's.

If you check previous competitions on these sites, usually the first few problems in each of them are easy to solve and are aimed for beginners.

I hope this answer helps you get started. :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English harrypotter0 2016-10-12 14:32:00 13443 Initial revision (published)