Some words of caution

First of all note that this course is still under construction. Feel free to give us feedback and report problem that you might encounter during your algorithmic journey with us. We really want our content to be as clear and easy to understand as possible so notify us with sections that are not so that we can improve them!

The goal of this course is to teach you algorithms for competitive programming. Even though it is designed for competitive programming, we believe that it will be interesting for any computer scientist wishing to improve his algorithmic and data structure design skills.

We will avoid going into deep theoretical proofs and focus on a more practical approach. There is already a lot of books and online material containing proofs that these algorithms are correct. We are hoping to explain them in a way that gives you the intuition of why they must be correct. We are not claiming in any way that intuition is a replacement for formal proofs. We encourage each one of you to dig deeper and formalize what we give you. This will only make you stronger when you have a new problem to solve.

Another goal of this course is to make you be able to implement all these algorithms and data structures. From our experience, most students learn a bunch of algorithms while studying to be computer scientists but then take forever to implement them.

This is not a course about software engineering so we will code in a way that is usually frowned upon by this community. Our goal is not to develop an algorithmic library so we will not focus on designing our code in a way that is reusable and general but rather we want to have a compact code that can easily be typed on a contest environment. Our goal is to write code that solves a specific problem and not a set of similar problems. Making the code more general usually makes it longer and thus you will loose time during the contest to type it. Actually, we encourage the students of this course to always type the solution of each problem from scratch. This will help you memorize the algorithms so that you don't forget how they work. It will also free some space on your cheatsheets!

However, if you wish to develop a state of the art algorithmic library, by following this course you will learn most of what you need. You will just have to rewrite the code in a way that it is less problem-oriented so that it can be used to solve several different situations.

The code in this course is written in Java. There is no reason for this except for personal preference. The language you use should also be the one with which you are the most familiar. Except for python, in today's contests judges make sure that any reasonable solution is accepted in all available languages. So even if Java is slower, any reasonable solution written in it will be accepted. Note that this was not always true so if you program in Java you will find some old problems where most Java solutions are too slow.

Any code provided here should easily be translatable in other languages as we are not going to use anything that is specific to Java (except for the syntax of course).

The general structure of a Java solution to a programming contest problem looks like this:

public class ProblemName {

    static int someProblemInput;
    static int[] anotherProblemInput;

    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        // read the input
        someProblemInput = reader.nextInt();
        // ...
        reader.close()
        solve();
    }

    static void solve() {
        // the code that solved the problem
        // ...
        // print the output
        System.out.println("The answer is 42");
    }

    static int someUsefulFunction() {
        // code
    }

    static class SomeUsefulClass {

        public SomeUsefulClass() {
            // code
        }

    }

}

You are free to not follow this template at all. Do not copy paste it! Write your own code! The goal is just to show that everything is usually coded statically.

New to programming contests?

If you are new to programming contests then welcome!

In a typical ACM-ICPC like contest you are given some number of problems and some time to solve as many problems as you can. The winner is the one with the most problems solved. In case of ties, they are broken by the total number of minutes used to solve the problem. To solve a problem, most systems allow you to submit a single file. This will then be compiled and ran on some number of predefined test cases. Then your answers will be checked to see if they are correct. If they are all correct, your solution is accepted. If any one of them is wrong you will get no points at all, even if you solve 99 out of 100 test cases.

Your solution is evaluated with respect to three aspects:

1. Whether the outputs that are produced are correct with respect to the problem specification.
2. Whether your algorithm is fast enough.
3. Whether your algorithm uses a reasonable amount of memory.

The verdicts you can receive are the following:

• Accepted: your solution passed all test cases.
• Wrong answer: your solution produced a wrong answer in at least one test case.
• Time limit exceeded: your solution exceeded the time limit set of the problem in at least one test case.
• Memory limit exceeded: your solution exceeded the memory limit while solving at least one test case.
• Compilation error: the code you provided does not compile.

A problem that some newcomers run into when participating in these contests is that they do not respect exactly the output specification of the problem. If the output asks for a single integer then you have to output a single integer. Any other character printed by your algorithm will produce a wrong answer. Also, always end your lines with '\n' (or println). Not all systems require this but most of them do so to be on the safe side just do it.

How is this course organized?

This course is composed by a serie of tasks. There are several kinds of tasks.

• Theory tasks: will usually contain some theory and end with a problem that is a direct application of what you just learned.
• Read tasks: these tasks, like this one, only contains material for you to read. Once you do, mark them as read so that you can more easily keep track of what you have already done.
• Problem tasks: a task with a problem that envolves any theory that was presented before. Depending on the difficulty it can involve several different fields.

Most task names start with a keyword that represents its topic. For instance: Graphs - Find a path will be a task about graphs. Some tasks like this one do not have one because they do not belong to a specific topic.

You are assumed to already know how to program. Therefore there is no topic for this.

The tasks should be done in order to try to make sure that you always have the prerequisites to solve it. We try however to make them as independent as possible. The course is still under construction and in the future it may start with another topic but in its current state it starts with graph theory as it is the most common topic in programming contests.

Each task starts with text explaining what has to be done. Then the input section will describe you the format of the input that you will be given. Follows an output section describing how your output should be formated. As we said above, you must follow the described format exactly. Then follows a section giving the problem size constraints. This is a very important section. Your solution has to be efficient but that depends on the size of the input. It gives you an hint on the maximum complexity that your algorithm can have. The last component of a task is a serie of sample test cases so that you can test your code before submitting.