Datatähti Open 2021 is an open online contest based on the final round of the Finnish Olympiad in Informatics (Datatähti) 2021.

The duration of the contest is 4 hours, and you can start the contest at any time between 29 January 2021, 16:00 (UTC) and 31 January 2021, 16:00 (UTC).

Contest link: https://cses.fi/359/list/

The contest consists of six problems (from easy to difficult), there will be subtasks and full feedback, and the scoreboard will be published after the contest. You can discuss the problems here after the contest.

Today we have released a new version of the CSES Problem Set:

https://cses.fi/problemset/

CSES Problem Set is a collection of algorithmic programming problems that can be used to practice competitive programming. We have now added 100 new problems, and the total number of problems is 300. There are both easy and difficult new problems, and some of them cover advanced topics, such as treaps, suffix structures, and FFT.

In 2020, there were more than one million submissions to CSES, which is a new record. Thank you for your submissions and new test cases through hacking!

Our ultimate goal is to create a problem set of 1000 problems, so you can expect many new problems also in the future. If you have ideas on how to improve the problem set, you can discuss them here.

The Nordic Collegiate Programming Contest (NCPC) 2019 will be held tomorrow. It is the subregional ICPC contest for Denmark, Estonia, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 5 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

Do IOI medalists get money as a reward in your country? How much (bronze/silver/gold) and who pays it?

We are discussing whether IOI medalists should be rewarded in my country (at the moment they don't get anything), and it would be interesting to know about the situation in other countries.

I'm glad to announce that we have today released a new version of the CSES Problem Set. It has many new problems and a new feature: hacking. You can access the problems here:

https://cses.fi/problemset/

New problems

The problem set has now 200 problems — compared to the original problem set, there are over 100 new problems.

The problems are now divided into sections according to their topics, so it is easier to practice a specific technique. The last section contains more difficult problems that require creative problem solving skills.

Hacking

There is a new feature: you can now hack submissions and improve the quality of tests.

After solving a problem, you can view the solutions by other users and try to hack them by giving a test case where the solution fails. If your hack is successful, the new test case will be added to the test data and all submissions will be regraded.

Future plans

In the future, we will add many more problems, and our goal is to create a comprehensive problem set that has 1000 high quality problems. We will also gradually add model solutions that describe different ways on how to approach the problems.

The Nordic Olympiad in Informatics 2019 was held yesterday. The contest is an IOI style practice contest for students from Denmark, Finland, Iceland, Norway and Sweden.

This year's contest is now available as an open virtual contest at:

https://cses.fi/

The length of the contest is 5 hours, and there are 3 tasks. The contest follows the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

You can start the contest at any time between 7 March 2019, 9:00 and 10 March 2019, 15:00 (UTC). After that, the results will be published.

The final round of the Finnish Olympiad in Informatics (Datatähti) will take place tomorrow, and after the official contest, there will be an international online contest.

The online contest will be available at CSES:

https://cses.fi/

The length of the contest will be 5 hours, and there will be 7 tasks of varying difficulty. The contest will follow the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

The online contest will be a virtual contest, which means that you can start the contest at any time between 17 Jan 2019, 20:00 and 20 Jan 2019, 15:00 (UTC).

All CEOI contests from 2005 to 2018 are now available for practice here:

https://cses.fi/ceoi/list/

You can either join a virtual contest (5 hours like the original contest) or just upsolve tasks.

The Nordic Collegiate Programming Contest (NCPC) 2018 will be held tomorrow. It is the subregional ICPC contest for Denmark, Estonia, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 6 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

Almost a year ago, I released an online competitive programming book. Since then, the book has been downloaded over 500,000 times, and many people are already using it to learn competitive programming. I have also received a large amount of feedback, which has greatly improved the quality of the book. Thank you!

Now I have some news regarding the book. First, there is now a printed version of the book available with the title Guide to Competitive Programming, published by Springer. So if you want to buy a printed book and support my work, you can do it now. The book is available, for example, through Springer and Amazon.

How is the printed book different from the online book? Well, they are actually two different books. I have rewritten and restructured many parts of the book, and also added new material. The printed book discusses a selection of more advanced topics, such as suffix arrays, treaps, dynamic programming optimization, and parallel binary search. You can find a detailed table of contents here.

Note that the online version of the book will be freely available both now and in the future.

Then, there is also a new problem set called CSES Problem Set. It contains a collection of problems which can be used to practice the techniques explained in the books. The first version of the problem set is available here. New problems will be added every now and then; the goal of the problem set is to contain a comprehensive collection of "standard" competitive programming problems.

The final round of the Finnish Olympiad in Informatics (Datatähti) will take place tomorrow, and after the official contest, there will be an international online contest.

The online contest will be available at CSES:

https://cses.fi/

The length of the contest will be 5 hours, and there will be 6-8 tasks of varying difficulty. The contest will follow the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

The online contest will be a virtual contest, which means that you can start the contest at any time between 18 Jan 2018, 20:00 and 21 Jan 2018, 15:00 (UTC).

The Nordic Collegiate Programming Contest (NCPC) 2017 will be held tomorrow. It is the subregional ICPC contest for Denmark, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 7 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

A collection of old BOI contests is now available at:

https://cses.fi/boi/list/

At the moment all contests from 2005 to 2018 are available. There are two ways to practice: you can start a virtual contest which is like the original contest (5 hours time to solve the problems), or then you can just upsolve the problems without limitations.

Update Jul/15/2018: Years 2017 and 2018 have been added

Competitive Programmer's Handbook is a new book on competitive programming, written by me. The book is still in progress but almost ready, and I decided to release it now for a wider audience.

You can download the book here:

https://cses.fi/book.html

The book consists of 30 chapters and is divided into three parts. The first part discusses basic topics such as programming style, data structures and algorithm design. The second part deals with graph algorithms, and the third part introduces some more advanced techniques.

The book assumes that the reader knows the basics of programming, but no background on competitive programming is required. I think that the book is useful for future IOI participants, as the book covers most topics in the IOI syllabus.

The final version of the book will be ready later this year. The PDF version of the book will be available for free also in the future, and in addition, there will be a printed version that will cost something.

Before the final version, I will do small fixes, improve the language and add references. Of course, I appreciate all feedback on the book — you can send it to this blog or directly to me.

The final round of the Finnish Olympiad in Informatics (Datatähti) will take place tomorrow, and after the official contest, there will be an international online contest.

The online contest will be available at CSES:

https://cses.fi/

The length of the contest will be 5 hours, and there will be 5-7 tasks of varying difficulty. The contest will follow the IOI rules: full feedback and no penalty for multiple submissions. Available languages are C++, Java, Pascal and Python.

The online contest will be a virtual contest, which means that you can start the contest at any time between 19 Jan 2017, 18:00 and 22 Jan 2017, 18:00 (UTC).

Baltic Olympiad in Informatics 2016 will take place in Helsinki, Finland, May 11–15.

https://www.cs.helsinki.fi/group/boi2016/

Besides the official contest, there will be an online contest that will be open for everybody.

The format is like IOI: two contest days, five hours time to solve three tasks, full feedback.

On both contest days, the online contest runs simultaneously with the official contest, i.e., the contest times are:

• Contest 1: Thursday May 12, UTC 6:00–11:00
• Contest 2: Friday May 13, UTC 6:00–11:00

Link to the contest system is here:

http://cses.fi/

You can already register an account to the system. The link to each contest will be activated 15 minutes before the contest.

There are several programming contest books, but what do they contain and how good are they? Of course, it is difficult to know before buying and reading them. In this blog post I review programming contest books that I have read.

Do you know other books or have different opinions?

• Programming Challenges: The Programming Contest Training Manual
• URL: http://www.programming-challenges.com/
• Authors: Steven Skiena & Miguel Revilla
• Year: 2003
• Price (Amazon): 56.67 USD (paperback)

This is a classic book about programming contests, written more than ten years ago.

The book contains 14 chapters that discuss topics such as data structures, combinatorics, dynamic programming, and computational geometry. Each chapter begins with an introduction to the topic, followed by a collection of programming tasks.

A lot has happened in the world of programming contests during the last ten years. While many chapters of the book are still relevant in modern contests, a lot of important material is missing. For example, the segment tree data structure is not even mentioned in the book.

The text of the book is well written and easy to understand. However, the quality of the code examples is not good. For some reason, everything is coded using pure C, and many implementations are cumbersome and unnecessarily long. I was astonished to see implementations of Prim's and Dijkstra's algorithms with quadratic time complexities.

It is clear that the book is outdated, and mastering the techniques presented in the book is not enough today. Still, it is nice to read the book, and it contains some material that I have not seen in other sources.

• Competitive Programming 3: The New Lower Bound of Programming Contests
• URL: http://cpbook.net/
• Authors: Steven & Felix Halim
• Year: 2013
• Price (Lulu): 26.99 USD (paperback), 35.99 USD (hardcover)

This book is an introduction to data structures and algorithms that are needed in modern programming contests. The book is intended for readers who have some background in algorithm programming. Both basic and advanced techniques are discussed.

A lot of material is covered in the book. There are nine chapters, and the first three of them concentrate on problem solving and data structures. After this, the next chapters discuss graph theory, mathematics, string processing and computational geometry. Finally, there are two chapters that contain more advanced material.

The book is a good resource for getting a general picture of the topics that appear in programming contests. However, many algorithms are discussed so briefly that it can be difficult to really learn them from the book. So, while the book tells you what techniques you should learn, there are often better sources where you can actually learn them.

A general feeling when reading the book is that it is a draft of a book instead of a published book. The quality of the text and the pictures is often not good. In addition, there is too little empty space in the layout which makes the book difficult to read.

When I read the book for the first time, I suddenly noticed that I have read the same text before. Unfortunately, some content in the book is copied almost word for word from the USACO training pages without mentioning this to the reader.

While there are severe drawbacks in the current version of the book, it is still the best introduction to programming contests I have read. The authors know what they are speaking about, and the techniques discussed in the book are relevant in modern contests.

• Looking for a Challenge? The Ultimate Problem Set from the University of Warsaw Programming Competitions
• URL: http://www.lookingforachallengethebook.com/
• Year: 2012
• Price: 30 EUR (hardcover)

This book contains a collection of tasks from Polish programming contests organized by the University of Warsaw. The book is written by a group of authors who have studied and worked at the university. There are 53 tasks in total, and for each task, the book contains a task statement and a detailed analysis how to solve the task.

First of all, this is not a beginner's book. Most tasks are difficult, and the book assumes that the reader already has a strong background in programming contests.

An experienced contestant can learn a lot from the book. The analyses are very well written. Typically, an analysis begins with a history how the task was invented. After this, different ways how to approach the task are discussed. The analyses are mathematically rigorous but accessible.

The only drawback in the book is that it is difficult to obtain. It can be ordered through the website of the book, but this is not as easy as one could think. Tip: if you don't get a reply for your order, try to send another order.

By the way, many tasks from Polish contests are available for practice at http://main.edu.pl/. Polish tasks are usually both high-quality and difficult, so they are good material for practicing.

Here are my predictions for the IOI 2014 results. They were calculated using information from eduardische's IOI Database and Codeforces API.

Prediction 1 (current rating)

Prediction 2 (maximum rating)

Prediction 1 is based on contestants' current rating on Codeforces. If the rating is unknown, the default rating is 1500. The contestants are sorted according to the ratings, and then the IOI medal allocation algorithm is used. Prediction 2 is calculated in the similar way, but the ratings are maximum ratings.

There are some obvious weaknesses in the model (e.g. many ratings are missing, Codeforces is not IOI), but let's see how accurate the predictions are after the IOI...

Update: changes in teams from Colombia and Egypt

QBASIC is a very cool programming language, but I have never been able to use it in a contest. However, I noticed that in IOI'97 and before that QBASIC was one of the official IOI programming languages.

Have you used QBASIC in a contest? Is it a good language for contests? It would be interesting to hear your stories.

Unfortunately, it seems that neither QBASIC nor any other BASIC dialect is available on Codeforces...

However, I coded a QBASIC solution for a recent problem, and you can see it here:

DIM d&(2, 2000)
m& = 1000000007
INPUT n%, k%
FOR i% = 1 TO n%
    d&(1, i%) = 1
NEXT
c% = 1
FOR i% = 1 TO k%
    FOR j% = 1 TO n%
        d&(3 - c%, j%) = 0
    NEXT
    FOR j% = 1 TO n%
        FOR k% = 1 TO n% \ j%
            u& = d&(3 - c%, j% * k%)
            u& = (u& + d&(c%, j%)) MOD m&
            d&(3 - c%, j% * k%) = u&
        NEXT
    NEXT
    c% = 3 - c%
NEXT
s& = 0
FOR i% = 1 TO n%
    s& = (s& + d&(3 - c%, i%)) MOD m&
NEXT
PRINT s&
PLAY "cccedddfeeddc"

The segment tree is a nice data structure that often appears in programming contests. However, outside the contest world the segment tree seems to be unknown:

• There is no Wikipedia article about it (there is an article but it describes another data structure).
• I haven't seen any algorithm textbook that mentions it.
• I haven't found scientific papers that describe it.

So can you explain why the segment tree is so unknown? Or do you know sources outside the contest world?

Binary search is a very familiar algorithm to most people here. A typical implementation looks like this:

// x = array of numbers
// n = length of the array
// k = search key
// returns "true" if the key is found, "false" otherwise
bool search(int x[], int n, int k) {
    int l = 0, r = n-1;
    while (l <= r) {
        int m = (l+r)/2;
        if (x[m] == k) return true;
        if (x[m] < k) l = m+1; else r = m-1;
    }
    return false;
}

However, even if the idea is straightforward, there are often bugs in binary search implementations. How exactly to update the search bounds and what is the condition when the search should stop?

Here is an alternative binary search implementation that is shorter and should be easier to get correct:

bool search(int x[], int n, int k) {
    int p = 0;
    for (int a = n; a >= 1; a /= 2) {
        while (p+a < n && x[p+a] <= k) p += a;
    }
    return x[p] == k;
}

The idea is to implement binary search like linear search but with larger steps. Variable p contains the current array index, and variable a contains the step length. During the search, the step length is n, n/2, n/4, ..., 1. Finally, p contains the largest index whose value is not larger than the search key.

A similar idea can be applied to binary search variations. For example, the following code counts how many times the key appears in the array. After the search, [p+1..q] is the range with value k.

int count(int x[], int n, int k) {
    int p = -1, q = -1;
    for (int a = n; a >= 1; a /= 2) {
        while (p+a < n && x[p+a] < k) p += a;
        while (q+a < n && x[q+a] <= k) q += a;
    }
    return q-p;
}

Do you know other tips how to implement binary search correctly?