Getting Started

So you want to do programming contests but don't know where to start? Well, it seems you do....since you're, well, here.

Story Time

Before we go any further...people often get frustrated with programming contests if they don't make progress early. I was the same way...Just reading inputs often stumped me. Take a look over here. Search for "Elkeka." You'll notice this team solved no problems in six attempts. Ouch. That was my team the first time I competed in ICPC. Now take a gander over here. Duke 0 won the contest and went to world finals with 5 problems. Turns out I was on Duke 0. The next year, Duke Lilike won the contest and went to finals. No, I wasn't on that team, but one of my Elkeka teammates was.

Moral of the story? We have at least two world finalists at Duke who started their careers in ICPC putting up a bagel.

You won't get zero right, because you're here and there are a lot of good resources on this wiki. I know what it's like to not know how to even get started on problems, but you will get better through patience and practice. Maybe you won't make it to world finals, but you'll be able to solve problems you couldn't before.

So when you're struggling, I can relate...I know, I've been there (check the proof above...), but know that maybe some day YOU will be teaching Dukies about programming contests!

Contests

Contests come in many shapes and sizes. Here are some of them

ICPC

The international collegiate programming contests is the largest contest for college programmers. It consists of two levels: regionals and world finals. We compete in the mid-atlantic regional. Generally the top two to three teams from each region are invited to world finals (though they can't be from the same school). World finals are often held in exotic places such as Phuket and Banf.

Contest Environment

For these contests you have teams of three individuals, but just ONE computer. There are generally 8-13 problems to solve in the 5 hours. Problems will always describe some sort of problem whose output will vary based on some input. While you are given some sample input and output, whether your algorithm is deemed "correct" is based on secret input that you are NOT given. Instead, you must submit your code, where a "judge" (i.e. some server running somewhere) will run your code against the secret input and compare your output with the correct secret output. Only if you get the secret output exactly correct will your submission get correct. Submissions must be in Java, C, or C++. Oh, and by the way, it has to run fast enough! Generally they tell you what the time limit is, but with practice, you'll know if a solution is fast enough by analyzing your algorithm vs the maximum size of the input.

Input and Output

You must write a standalone program (it will have a "main" method) which reads from standard input and writes to standard output.

Ranking

Teams who solve the MOST problems in the 5 hours are the winners. Tie breaking is done by your total penalty time, which is calculated as follows

• For any problem you solved, the number of minutes that have elapsed since the start of the contest when you solved it are added
• For any problem you solved, 20 minutes are added for each INCORRECT submission BEFORE you got the problem solved correctly

Codeforces

Codeforces is one of the best regular contests to help prepare you for ICPC. Their contests are run almost exactly the same as ICPC, but with individuals instead of teams. Keep an eye out for them, and know that you often have to register before the round starts. You will start in division 2, and will be promoted to division 1 when your ranking is high enough.

Topcoder

Topcoder is another hoster of regular contests. Their Single Round Matches (SRMs) are quick ways to practice.

Contest Environment

For these contests, you launch their "arena" and assuming you have registered for the contest, are placed in a room with ~20 other coders. When the contest starts, each of the three problems will be visible. When you open one, you will provided with a text editor. There is nothing stopping you, however, from using whatever editor you choose and copying the code in. Once you put the code in, you can compile and run a few example test cases to see if they pass, and finally submit. UNLIKE ICPC, however, you will not get your result. For now Topcoder will ASSUME your answer is correct and award you the points.

Challenge Phase

Once the coding phase has ended, you enter the challenge phase. Here you can look at the solutions of other people in your room. If you think they made a mistake, you can "challenge" their solution by providing an input you think their code will get wrong. You get points if you are correct, or lose them if you are not. Only one person can successfully challenge an incorrect solution, so be quick!

System Test

Lastly, the "judge" will run all the solutions against secret test cases, removing points which were awarded if the solution was deemed incorrect.

Ranking

Problems are each worth different point values (generally 250, 500 and 1000). When you FIRST open a problem, the clock starts ticking, and the more time you take to solve that problem is deducted from the amount of points it is worth. So if you end up taking a long time to solve the first problem, you might only get 150 points. At the end of the contest, your points from solutions (which passed system test) and from challenges are added, and the person with the most wins.

Input and Output

You are generally provided with a method signature which you must implement. You will not need a "main" function for these, as your code will just be included by some other program. The input will be the method parameters, and the output will be the return.

Starting to Practice

If you have NEVER solved a problem before, you're probably going to want to start with Kevin's trivial set. There you will find problems (which come from REAL CONTESTS) which will help you get your feet wet. You will need a login, so ask kevin for one.

Writing your First Solution

The first thing I do when I solve ANY problem (literally...any problem) is start with my template. It looks like this (for problem "a" from a set). Your template may vary slightly, but I recommend starting all your problems the same way! Just getting over the hump of getting SOMETHING down helps you get started.

import java.util.*;
public class a {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new a().go();
	}
	private void go() {
		// read input
		// do stuff
		// print output
	}
}

Input and Output

We have a great tutorial on Input and Output. It will be the first thing you have to do when writing your program. Without a great tutorial, I found it very frustrating, and often spent so much time on it I didn't even get to the algorithm! But heed the advice in the guide. I also recommend reading the input before necessarily thinking about how you will solve the problem, since how you solve the problem should have no bearing on how you read the input! In any case, the problems in the trivial set shouldn't have enough algorithmic complexity, so you should be able to just focus on getting some correct solutions.

Generally output is pretty easy, just printing single numbers, or each element in an array. Become familiar with printf (also in the tutorial), as it will be your friend! Sometimes you end up with rather complicated output. This is annoying, and some of the cases you will get better at handling with practice (such as printing out a path through a graph).

Do Stuff

This is the meat of the problem. This is what will challenge you once you move past the trivial problems. Hopefully through participating in programming contests you will learn new algorithms and data structures, and more importantly, be able to apply them to unknown problems. It turns out that skill is a MAJOR boost in coding interviews, as the problems and techniques you get are incredibly similar to what you might see in a programming contest.

Getting Better

If you head over to [:Category:Tutorials|Tutorials] or [:Category:Techniques|Techniques] you'll see a TON of different tricks that can be used to solve a problem. This may seem overwhelming at first, but over time, you will become more familiar with them. Ideally (in the future) I will have added pages that describe all of them.

Fortunately, there are a few "starter" techniques that are quite fundamental and show up time and time again.

Greedy

Greedy Solutions will have a simple rule that allows you to make decisions in the course of solving your problem. The classic case is making change. If you are trying to make change using the LEAST number of coins, use as many of the highest value coin as possible. Another example could be even simpler. To spend as little as possible on a round trip flight, you will pick the cheapest flight for each leg.

It often helps when solving a problem to see if you can come up with any greedy rule, even if it is wrong. Often figuring out why it is wrong will lead you to a better solution (generally Dynamic Programming).

Brute Force

In a brute force solution, you try all possibilities and pick the best one. As it would apply to making change, you might try EVERY combination of coins you have, and then pick the one that yielded the correct value with the fewest amount of coins. As you can imagine, this is quite slow. Often times thinking of a brute force solution is useful to ensure understanding of what the problem is asking. Brute force solutions, while generally yielding the correct answer, are usually too slow to run in time (Sometimes not, though, and as a rule it's good to try to think of one just to make sure it's NOT actually fast enough!)

Graphs

Graph problems are probably the single largest set of problems we see in contests. There are several useful graph algorithms, or ad-hoc techniques that we use. In the graph tutorial, we discuss some of the basics of just WORKING with graphs (which like input, can be overwhelming when starting out), as well as some of the more common algorithms that you often use on graphs.

Dynamic Programming

This is like greedy or brute force if it had gone Super Saiyan. It is a very flexible technique which generally yields very compact solutions (i.e. not a lot of code). The downside is it is often hard to wrap your head around when first learning, but once you get it, you'll be able to solve a lot of problems that most people can't.

Math and Geometry

These problems often don't fall into one of the standard techniques. They don't really want you to come up with some clever set of steps to take, but instead call on your mathy background to come up with clever manipulations to arrive at a solution.

Practice

I can't state enough that this is the ONLY way to get better. Doing scrimmages and contests, reading lots problems, solving lots of problems, etc. One of the mistakes I see is people thinking about a problem for a very short amount of time and "giving up"; either deciding it's too hard or simply reading the solution. This is NOT the thing to do. If you never stretch your problem solving skills, you won't improve your problem solving skills. Yes you may know every technique under the sun, but being able to ponder a problem and work through the permutations of all the techniques and problems you've seen before to come up with the RIGHT answer is an awesome skill, and you don't get it by not trying it.

When you come across a problem you don't know, I encourage you to not give up. Try this instead:

• Ask yourself "Is there some structure to this problem that i'm not using in my solution?"
• Think if any algorithm or technique ALMOST solves the problem, if not for some small hiccup, and can we use some other technique to alleviate that hiccup?
• Try to ask the question in a different way
• TALK with someone about it. Simply describing the problem to someone might trigger something
• Think about wrong solutions and why they're wrong. Only one of the following two things can be true if you have thought through every possible technique: all of them are wrong, or...the problem has a solution. We know the problem has a solution, so one of the techniques we thought through MUST be correct, despite us thinking it wrong. So don't be afraid to think through solutions you might think are wrong at first. "If I were to try to solve this problem using technique XYZ, how would I do it?" This often forces you to think in creative ways, and might lead you to a solution. Worst case, you've learned something
• Spend at least a week thinking. And I don't mean saying "this is hard" and forgetting about it....ACTUALLY thinking about it. Make it your desktop background or something. Think about it in the shower, while trying to fall asleep, while walking to class. Talking about it is a great way to force you to think about it. If you don't have practice thinking through problems every day, then how will you do it during a contest?

Reviewing Code

Most of the time, solutions should be relatively easy to write. If they're not, there MIGHT be a better way. Look at other people's solutions for that problem, Kevin to look at your code...knowing the algorithm is only half the battle...getting it into the computer is the other half!

Evaluating Runtime

One of the important skills we have to build is evaluating runtime. We have to be able to tell quickly whether a proposed solution will be fast enough. Getting good with big-Oh is a must. Knowing the time it takes to do operations on data structures is a must. Once you can evaluate the runtime complexity of your algorithm, you can plug in the maximum-size input (almost invariably given in the problem statement) into your runtime calculation. If the number yields something less than 500 million or so, you're probably alright.

Turns out the size of the input is helpful enough that we can often deduces what kind of algorithm we need. 24? probably brute force. 10,000? nlogn. 1000? n^2. It doesn't always work, but sometimes it helps.