Welcome

Do you like programming, problem solving and free pizza? Join a programming contest!

Every semester, we host at least a few different competitions that are open for everyone. We aim for the contests we host at UiB to be accessible to every level of programmers, though we advice that you have enjoyed at least half an introductory course in programming prior to competing.

Upcoming

Past^*

* Contests without original problems, such as local recreational contests, warmups and practice sessions, are not listed. Also, contests prior to Fall 2015 are not listed.

UiB has been participating regularly in NCPC/Norwegian Championship since 1999, NWERC since 2006, and IDI Open since we can't remember when. We are also the host of the Norwegian Informatics Olympiad for high school students.

Tutorial

Never tried a programming contests before? It can appear like scary stuff, but it can actually be really fun regardless of what level you are. Let's get the basics going.

This tutorial is targeted for users familiar with the bash shell. If you prefer to use a different environment to run your programs (such as an IDE), you might need to adapt the instructions to fit your environment.

Let us solve the problem Oddities (read it before continuing). For this problem, devising an algorithm is not hard (a number x is even if x % 2 == 0, and odd otherwise). Yet, it poses some challenges to a newcomer: How do I find the input? How do I provide the output? The general answer is that input is provided on standard input and output should be provided on standard output. What this looks like is different from language to language (see examples). We explain the example in C++ below* **:

• C++
• Java
• Python 2
• Python 3

#include <bits/stdc++.h>
using namespace std;

int main() {
    int testcases;
    cin >> testcases;
    for (int i = 0; i < testcases; i++) {
        int x;
        cin >> x;
        if (x % 2 == 0) {
            cout << x << " is even" << endl;
        }
        else {
            cout << x << " is odd" << endl;
        }
    }
    return 0;
}

import java.util.Scanner;

class Oddity {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            System.out.print(x);
            if (x % 2 == 0) {
                System.out.println(" is even");
            }
            else {
                System.out.println(" is odd");
            }
        }
    }
  
}

def oddity():
    n = int(raw_input())
    for i in range(n):
        x = int(raw_input())
        if x % 2 == 0:
            print "{} is even".format(x)
        else:
            print "{} is odd".format(x)

oddity()

def oddity():
    n = int(input())
    for i in range(n):
        x = int(input())
        if x % 2 == 0:
            print("{} is even".format(x))
        else:
            print("{} is odd".format(x))

oddity()

We save the above as a file oddity.cpp, and we compile it with GNU C++ Compiler ($ g++ oddity.cpp). If this crashes for you, you are probably using clang as your compiler. See * below.

Once the program is compiled, we can test-run the program locally ($ ./a.out). The program will stare blankly at us, doing nothing but waiting for input; this is the correct behaviour. We can now enter input manually, e.g. by typing in the sample testcase.

Manual testing is a good first step, but to be sure that we have solved the sample cases correctly, we suggest downloading the sample testcases directly from Kattis via the link on the right side of the problem page, beneath the "Submit" button. Using this method, rather than copying the sample testcase by hand, ensures that you don't run into file encoding issues and different representations of newline symbols. Extract the samples.zip -file, and you will find two files sample.in and sample.ans. To check that your code works, we can pipe sample.in into our program ($ ./a.out < sample.in), and compare the output to sample.ans ($ cat sample.ans). The output of those two commands must (at least in this problem) be identical for us to get our solution accepted.

Rather than doing the comparison manually, though, it is better if we leave this to a program designed to check for differences: diff. It can look something like this:

$ ./a.out < sample.in > myanswer.ans
$ diff sample.ans myanswer.ans -s
Files sample.ans and myanswer.ans are identical
$

If the above command indeed confirmes that the two files are indentical, we have confirmed that our program works correctly for the sample testcase.

We are now convinced that our program works, so let us submit! Now that is was accepted, here are some more problems to get you thinking:

• Death Knight Hero
• Judging Moose
• Aaah!
• Bottled Up
• ICPC Tutorial
• Take Two Stones
• Solving for Carrots
• The Easiest Problem Is This One
• ACM Contest Scoring
• Troll Hunt
• Ants
• Dice Game
• Erase Securely
• Army Strength (Easy)
• Army Strength (Hard)
• Fast Food Prices

* If you are using C++: Note that there are some differences between the various compilers. Online judges usually use GNU Compiler Collection (gcc), but if you are working on a Mac, you probably are using clang. The differences are not usually significant; however, clang does not understand the line #include <bits/stdc++.h> in the example above. To be able to compile our program locally you will need to either do the required includes from bits/stdc++.h directly yourself (in the sample solution you only need #include <iostream> ) or make your own bits/stdc++.h as explained here (this is a one time operation per computer).

** If you are using Java: Note that the Scanner class can be quite slow if you need to read lots of input, and the normal System.out.println() can be quite slow if you're printing lots of output. Consider using faster I/O methods, such as Kattio, which is available here.

Learn more

Courses at UiB

If you enjoy competitive programming, UiB offers several courses which will help you do even better. Most prominently, INF237 Algorithms Engineering is a course which is tailored specifically towards competitive programming, and it runs every spring semester (check out previous years). Other useful courses are INF102 Algorithms, Data Structures and Programming, INF234 Algorithms, and the killer course INF334 Advanced Algorithms.

External resoruces and online judges

There are some excellent course materials available at Bjarki Ágúst Guðmundsson's web page, and the Stanford course CS 97SI: Introduction to Programming Contests is also a nice resource.

Hordes of practice problems are available at online judges such as Kattis, Codeforces and many others.

Blog posts by our students

• Binary index trees by Kristoffer Æsøy (2021-12-18)
• Tires by Petter Daae (2021-11-23)

Common techniques

There are many techniques to master for the ultimate programming champion. You can learn about most of them in one of the courses mentioned above. By popular request, we have collected some example problems from different categories. Be warned, we can not give any guarantees on the difficulty. Also note that the problems are only guaranteed to be solvable in C++ and Java (most are also solvable in Python, but not all).

There is also a searchable archive of problems annotaded with keywords at Torstein Strømme's webpage.

• Simulation
  Train Passengers Logo Statistics Bounding Robots Toilet Seat Disastrous Downtime Mosquito Multiplication Turtle Master Semafori Riječi Height Ordering
• Sorting and priority queues
  Moving Pianos Sticky Situation Assigning Workstations Nested Dolls Compass Card Opening Ceremony Phone List A Classy Problem Boiling Vegetables Juice Knigs of the Forest Cookie Selection Chopping Wood Shopaholic
• Queues and stacks
  Working at the Restaurant Trending Topic Even Up Solitaire Integer Lists Symmetric Order Riječi Card Trick
• Greedy
  Get to Work Doorman Bell Ringing Virus Replication Cryptographer's Conundrum Entertainment Box Hyacinth Enemy Division
• Mathematics, combinatorics and number theory
  Falling Mugs Fleecing the Raffle Exponial Catalan Square An Industrial Spy Divisible Subsequences Prime Path Prime Time Incognito
• Dynamic Programming (DP) / Memoization
  Aspen Avenue Collecting Beepers Interval Cover Drink Responsibly Safe Passage Outing Robots on a Grid Road Work Roller Coaster Fun Allergy Test Narrow Art Gallery Prince and Princess Floppy Music Good Coalition Hero Power Copying DNA Hiding Chickens The Citrus Intern Cent Savings Bribe Panda Chess Shoot-out Whac-a-Mole Hopper
• Geometry
  Logo Logo 2 Pesky Mosquitoes Cover Up Robert Hood Cleaning Pipes Keeping the Dogs Apart Goofey Geometry Target Practice Eco-driving Hole in One Imperfect GPS Hidden Camera Simple Polygon Galactic Warlords
• Binary Search
  Millionaire Madness Free Weights Careful Ascent Distributing Ballot Boxes Freight Train Getting Through Programming Tutors Eco-driving
• Graph problems
  
  • Exploration (DFS/BFS)
    Torn to Pieces Counting Stars Birthday Money Matters Amanda Lounges Where's My Internet?? Adjoin the Networks Build Dependencies Digi Comp II 10 Kinds of People Gold Weak Vertices Car Trouble Reversing Roads Mravi Kitten
  • Shortest paths (BFS/Dijkstra/Bellman-Ford/Floyd–Warshall)
    Big Truck Prime Path Cliff Walk Eco-driving Elevator Trouble Horror List Hotels Crowd Control Treasure Diving Hiding Places VisuAlgo Online Quiz Destination Unknown
  • Minimum spanning trees (Prim/Kruskal)
    Island Hopping Grid MST
  • Max flow/min cut (Ford Fulkerson/Edmonds-Karp)
    The King of the North Catering
• Bipartite matching (Hopcroft–Karp)
  Programming Tutors Book Club
• Prefix sums and segment trees
  Bird Rescue Pinball Ski
• Exhaustive search and pruning
  Card Hand Sorting A Towering Problem Basin City Surveillance Kitchen Combinatorics Treasure Diving Beacons Gokigen Naname Holey N-Queens (Batman) Coloring Graphs Indorienteering Key to Knowledge Map Colouring Set! Veci Natjecanje
• Ternary search
  Eucledian TSP Biking Duck
• Sliding window, sweep and walking dudes
  Radio Commercials Gotta Nuge 'Em All Prozor
• String algorithms
  What Does it Mean? Just a Quiz ls
• Union Find
  Virtual Friends Artwork Suma Association for Control over Minds Ladice
• Bits, masks and manipulation
  Bit by Bit Death Star Snapper Flip Five Envious Exponents

What techniques you will need in the next competition is hard to know beforehand, as the problem setters try their best to make the problems such that one can not simply apply an algorithm out of the box. A perfect problem is easy and intuitive to state, is tricky to solve conceptually, yet has a beautiful and easy-to-code solution once you see it. Of course, it should also have some novelty to it. Still, knowing which techniques are most common may be interesting. A rough categorization of the NWERC problems from 2010 to 2016 revealed that the following techniques were the most common:

• Greedy/simulation/ad hoc (22)
• Dynamic programming/memoization (17)
• Brute force (8)
• Geometry (8)
• Binary search (6)
• Max flow/bipartite matching (6)
• Shortest path in graphs (5)
• Number theory (3)
• Ternary search (2)
• Fenwick/counting/segment/interval trees (1)
• 2SAT (1)

Contact

Currently responsible for the competitive programming efforts at UiB are Pål Grønås Drange and Torstein Strømme. Please feel free to contact them at {pal.drange, torstein.stromme}@uib.no if you have any questions or remarks.