Posts

For an ACM-ICPC beginner, how should I start?

Most of the answers here point out places where one can solve problems. I'm going to describe an approach to approaching ACM programming contests which is a bit different. My definition of an ACM beginner is someone who has not done an ACM regional contest before and has essentially no competitive programming experience, so I will try to cover more of the details from starting on working ACM problems to competing in a regional contest. First, get comfortable with one of C++ and Java. You're allowed to use C, C++, or Java - using C is more likely to hinder you in the long run, so get acquainted with one of the other two languages. You should be comfortable enough with the language that you can do some simple things. In particular, you should be comfortable with the following: Reading in data from standard input (the console), or from a file. You  must learn how to do this, since that's how interaction with the program is done. Basic arithmetic operations with integer num...

Top mistakes of competitive programmers

Please note that this answer is dedicated to competitive programmers only, as well as some recommendations in it. Competitive programming is not about readability, but about being able to code and debug fast.And still, the mains problems that I've seen: laziness and do not caring about code style even a little. That's ok if your program gets Accepted on first try, but otherwise you're gonna have a bad time debugging it. In general. So, mistakes (all of them are real stories): 1)Focusing on easier and 'cooler' things (like using of bitwise operations a lot instead of straightforward mathmatical formulas) instead of making code simpler to read and debug. Not only for them, but for the one who will help them too. 2)Copy-pasting it all around. "We don't need no architecture, just a little hack here is not bad. Oh, and here is another one. And here. C'mon, I still can tell you how is this supposed to work, but it doesn't work somewhy, can you help me?...

Tips to be Competitive

General tips below: Tip 1: Type Code Faster! No kidding! Although this tip may not mean much as ICPC and (especially) IOI are not typing contests, we have seen Rank i and Rank i + 1 ICPC teams separated only by a few minutes and frustrated IOI contestants who miss out on salvaging important marks by not being able to code a last-minute brute force solution properly. When you can solve the same number of problems as your competitor, it will then be down to coding skill (your ability to produce concise and robust code) and ... typing speed. Try this typing test at http://www.typingtest.com and follow the instructions there on how to improve your typing skill. Steven’s is ∼85-95 wpm and Felix’s is ∼55-65 wpm. If your typing speed is much less than these numbers, please take this tip seriously! On top of being able to type alphanumeric characters quickly and correctly, you will also need to familiarize your fingers with the positions of the frequently used programming langu...

Introduction to Big O

Big O Notation Big O is defined as the asymptotic upper limit of a function. In plain english, it means that is a function that cover the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms. Growth Rate Name 1 Constant log(n) Logarithmic n Linear n log(n) Linearithmic n^2 Quadratic n^3 Cubic 2^n Exponential This is kinda abstract let’s see what it means in code: Growth Rate Name Code Example description 1 Constant a= b + 1; statement (one line of code) log(n) Logarithmic while(n>1){ n=n/2; } Divide in half (binary search) n Linear for(c=0; c<n; c++){ a+=1; } Loop n*log(n) Linearithmic Mergesort, Quicksort, … Effective sorting algorithms n^2 Quadratic for(c=0; c<n; c++){ for(i=0; i<n; i++){ a+=1; } } Double loop n^3 Cubic for(c=0; c<n; c++){ for(i=0; i<n; i++){ for(x=0; x<n; x++){ a+=1; } } } Triple loop...

The Further Steps – Contesting And Continuing Practice – Competitive Programming last part of series

The Further Steps – Contesting And Continuing Practice – Competitive Programming last part of series If you have followed the first three parts of the series, you’d now be very well acquainted with the world of Competitive Programming. By now, you’d have started competing already. So, what are the further steps you can take to become a kickass competitive coder? – Contest in all the contests that you come across – Continue the practice in various online judges Regarding the contest, here are the most popular places you can contest online. 1. Topcoder Topcoder is the best and the most popular online judge with respect to contests. They have a variety of contests going on every now and then. Their SRMs are the most popular ones. There are various categories of contests, and more so, the prize for the contest winner is money. Practicing with past SRMs and contesting in the new SRMs whenever they conduct these matches, in Topcoder especially, will give you a great edge...

Practice Guidance For Competitive Programming – Competitive Programming Series Part-3

Practice Guidance For Competitive Programming – Competitive Programming Series Part-3 If you haven’t read the first two parts of this series, you can read them from below posts. This part will lead you with the next step in your programming journey. This is the part where you actually start practicing problem-solving, competitive programming style. The following is the way I have found to be the most effective. 1. spoj.com The first step in your competitive programming practice, for it to be the most effective, choose these two websites. SPOJ is the best and the leading forerunner in terms of programming contest style questions. Their online judge is awesome. SPOJ engine is also used by CodeChef. The way to practice problems is this. You have to sort the problems in descending order of number of users who solved a problem. If it helps, here is the link for that – http://www.spoj.com/problems/classical/sort=6 – bookmark it. Also, go and check out ProjectEuler. Cr...

Competitive programming part-2

Problem Solving Using Algorithms and Data Structures – Competitive Programming Part-2 This part will deal with the next step in your journey – starting to solve problems using data structures and algorithms. There are many ways to do this. I have personally found going through a few things very apt in this process. This part will give you a step by step guidance. Once you have started learning algorithms and data structures, do it this way for the most effective experience. Learn algorithms according to a category, like sorting, searching, stacks, queues, etc,. Geeks For Geeks: Once you learn the data structure/algorithms in a particular category, head over to  Geeks For Geeks – Data Structure Problems . Solve all the problems in the category of data structures/algorithms that you have learned. Say, you learn all about stacks, stack operations. You then head over to geeksforgeeks and solve all the problems listed under stack. Before seeing the so...