Topic outline

  • Week 2

    HOMEWORK BEFORE WEEK 2

    The tasks of week 2 we will be covering some of the most common techniques in competitive programming, namely sorting, binary search, BFS and DFS. Maybe you are familiar with some or all of these—now it is time to learn how and when to use them.

    Sorting

    Sorting algorithms are rarely implemented by hand during contests as virtually all languages’ standard libraries provide well-optimized and flexible implementations. Make sure you know how to sort by arbitrary conditions. For example, this C++ code creates an order based on arrays a and b:

    vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int l, int r){ return a[l]-b[l] > a[r]-b[r]; });

    Binary search

    Unlike sorting, this is something you should learn to do by hand. See pages 31–34 in the Competitive Programmer’s Handbook. While binary searching for an element in a sorted list is common, problems that require doing it are usually not considered “binary search problems.” Typically the core realization in a binary search task has the form:

    1. We need to find the largest possible X, but this is hard.
    2. Aha! Trying to constructing a solution for some fixed X is easy.
    3. And if there is a solution for some fixed X, there are solutions also for all smaller values.
    4. Use binary search to find the largest X that admits a solution.

    Substitute X for “time” in task “Entrepreneur” from Wednesday’s contests and see if you can solve it.

    Graph essentials

    Knowing how to represent graphs and how to traverse them are essential skills in competitive programming. Make sure you know how to implement Breadth First Search (BFS) and Depth First Search (DFS). See pages 113–120 in the Competitive Programmer’s Handbook.

    MONDAY CONTEST

    On Monday (September 12), we will have a solo contest.

    The contest will be available at cses.fi/404/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp. Please make sure you use your personal CSES user account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    WEDNESDAY CONTEST

    On Wednesday (September 14), we will have a team contest. We will assign students to teams at random at 16.15, so please be in the class room punctually!

    The contest will be available at cses.fi/405/list/. The contest will automatically open at 16.20 sharp, and it will end at 17.50 sharp.

    We will create one CSES account for each team. Please make sure all team members use the same team account to take part in the contest.

    Once the contest is over, please fill in the form below to record your score.

    HOMEWORK FOR WEEK 3

    Please see the section “Week 3” for more information on what to study before next week! We will announce the homework by Wednesday.

◄ Previous section
Week 1
Next section ►
Week 3